CSEQ - Editorial

editorial
, , , , , , ,
13

A non Lucas way of getting AC … Runs in 0.14s and 10.7M … A bit complicated but faster (and the precomputation is the same).
http://www.codechef.com/viewplaintext/6776710

14

Can Anyone help me!!!?
Why is the last subtask wrong?
I only used extended_euclid. Is Lucas’s algorithm different from it?

http://www.codechef.com/viewsolution/6776631

Please tell me my mistake.

15

Hi @Adury Surya Kiran/Editors,

I wanna thank you for putting up such a nice Editorial. You have explained everything in detail and I believe it must have taken you a long time to make this editorial. You have turned something complicated and ugly looking into a simple and beautiful solution. :slight_smile:

Thanks again. :slight_smile:

Rohit

1 Like
16

Hi All,
I am just a newbie here.

I worked on this problem for quite a lot of time. Alas, no result!

Then I observed after the solutions were out, that most of the solvers of this problem had used Lucas theorem.

The theorem I had not heard of, until seeing this editorial and a couple of solutions.

After knowing that this problem needs something that I am missing, the only way I worked was calculating the outputs of some test cases manually and trying to figure some kind of relationship between the inputs and output which came in a form of some series. Though i found a relationship, it was too complex.

Of course, I being a newbie, I could not even think like those experts who solved this.

My question is how can one develop the “instinct” to solve such problems, the “instinct” to apply Lucas Theorem ?

I know its from practice, but unless I know what Lucas theorem is,I cannot imagine how to solve such problem.

And its not the problem with Lucas theorem. Today it was Lucas theorem, tomorrow it maybe another one.

So I am asking about the way how can one approach such problems.

Please can you guide on what all to know before going deeper into competitive programming ,where can I get information on such things(such as approaches/theorems etc) ?

17

My code TLE C++ on 4.3.2 and AC on C++ 4.9.2. Why is it so?

18

I am getting a “SIGSEGV” error in the last sub- task. Can anyone please help ?

My solution is :My Solution

19

I can’t believe I reached the final answer myself!!

But had to take help to calculate choose(n,r) from tester’s solution, for third subtask(Lucas theorem).

If modulus was 10^9+7 instead of 10^6+3 , then what is the method to calculate choose(n,r) where 1<=n,r<=10^9 ?

20

If anyone is not clear with the formula, check this -:Stars and Bars (and bagels) - Numberphile - YouTube

2 Likes
21

“Distributing <=K things, to N people, is same as distributing exactly K things, to (N+1) people”.

Why is this so? Can you let know the analysis?

22

Your solution is O(N) which is bad.

23

^ As he said, the extra person is a dummy. That is to say, the first n people will get some c (say) <= k things, the remaining (k - c) will go to the last person. There will be a case where the last guy gets everything, so we do -1 to get the right answer.

4 Likes
24

c might get negative and c%MOD will still be negative.
if you do (c+MOD)%MOD, it’ll give positive.

25

Thank you… Didn’t thought about this case. In whole contest , I was busy in optimizing my code.

26

lol :smiley: :smiley: :smiley:

27

@alexvaleanu
Thanks!!

A small mistake costed 50 pts. ;(

28

I was doing tge same mistake earlier. But then i realised it for good

29

Your solution is O(N). It should get TLE for the last subtask.

30

You don’t use Lucas’ theorem. O(N) is not optimal

31

@yashv, well predicted,a similar question was asked in May Lunch time.Link:

1 Like
32

I am getting SIGSEGV in the last sub-task. I have used lucas theorem, still. Not sure what’s going wrong. Can anyone help?
Here’s the code -

https://www.codechef.com/viewsolution/38637100