The only difference is Manthan is an event of Codefest, the annual coding festival of Computer Science and Eng. Dept. of IIT BHU while ICM is an event of Technex, the annual techno-management fest of our Institute.

Indian rupee.

1 USD = 63.99 INR 1 Euro = 79.53 INR

This is 2nd of 4 rated contests(for Div. 2) in 4 consecutive days.

On the bright side, if you get stuck on a question, there will be another one of roughly the same difficulty.

If you take a look at last year's contest, it was 7 problems in 130 minutes. I did a virtual of it and it seemed pretty appropriate.

Every winner will get only one prize. If he's first overall and first in India, he will get the first overall prize and the second place in India will get the first and so on.

http://infametr.datameter.ru/infa/3263801/

Just don't submit in the contest and it won't be rated for you. :)

UPDATE- I'm able to de register now.

Dude, accurate af :D

@enigma27 see this :P

why do you think so?

How did he manage to generate all those hackable solutions ?

Respect

How these two users can enter the same room？

i used stirling number of second kind. Let's denote S[i, j] as the stirling number of second kind. And make array B, so that B[i]=(2^(n-i))*n*(n-1)*...*(n-i+1) So, for example, B[0]=2^n, B[1]=n*(2^(n-1)), etc... Now, the answer we are finding is sum(i=0 to n) (nCi)*i^k, which is equal to sum (i=0 to k) (B[i]*S[k][i]). (Because of mathematical reason!) You can calculate this in proper time limit.

Sorry for my bad english... have a nice day!

A very nice solution is you can calculate (1 + x) ^ n with Newton's Binomial, differentiate both sides (with respect to x) k times and then consider x = 1 to get the answer for k. (Write it down on paper for k = 1 and k = 2 and you'll see how it works)

I didn't solve it but I think the idea is let and calculate the number of ways to partition s into even-length palindromes, and then use some propogation on palindromic tree (which unfortunately I'm not familiar with).

Problem D i did a solution using persitents + dynamic segment tree (one tree for calculating sum, another for calculating maximum). Mine seem correct although i didn't finish it in time

for D, query type 2: number of nodes weight[R] >= weight [ (R -> parent[R] -> parent[parent[R]] -> .... -> 1) ], did i understand correctly?

D: why is it optimal to take closest v above with w[v] ≥ w[u], when there could be many more nodes x_i above with lower weight w[v] > w[x_i] ≥ w[u] that we can now not take anymore because of weight constraint?

Let weights of nodes be [5,4,3,7,2] So nxt[5] = 4 because node 4 is closest to 5 and w[4] > w[5](7>2) but isn't the optimal ans is sequence {5,3,2,1} so shouldn't nxt[5] = 3?

No

I think u just need to differentiate and multiply by x the generating function (1 + x)^N K times, and then just evaluate at x = 1.

For example, for K = 2, we differentiate , then multiply by x, then differentiate again and then multiply by x again.

I think if ur a math guy, this problem is really basic.

Well, as it said in oeis.org: "The closed form comes from starting with (1+x)^n and repeatedly differentiating and multiplying by x", And finally replace x by 1. I could't finished the implementation in time.

It is possible to write i^k as the sum of binomial coefficients for j ≤ k. (see here for explicit formula).

Then, we just need to solve the problem for when i^k is replaced by , which is doable with a simple combinatorial argument.

The other solutions seem too ugly for such an obvious problem so I'll share mine as well. The answer is number of ways to choose some subset of {1, .., n} and write a string of length k with elements of it. Let's first choose a string of length k and then choose some subset containing all characters of it.

I have another approach and I think it's beautiful!

The answer is . It's the number of ways to choose a non-empty team out of n participants, and then distribute k different marbles between the team members.

This could be done in another order: First, choose the participants who get marble and add them to the team, then distribute the marbles between them and then choose an arbitrary subset of other participants and add them to the team. Counting the number of ways to do that in this order is easy, you can find the details in my submission: 35312404

The problem is to find:

Break into two sums and use the binomial expansion of (r + 1)^(k - 1) to show that

I solved it using a recurrence which is:

f(n,k)=n*(f(n,k-1)-f(n-1,k-1))

Its pretty easy to derive this. :)

There is an overflow issue in your code. B * M would overflow long long and you should convert to double for comparison. This is in the standard Dynamic CHT implementation.

I was clicking on submit on E with 2 seconds left. Tell me about it.

no

I've your problem too :(

Same bro. After the second public clarification, I gave up all hopes of solving D. Started to look for E, but not enough Math knowledge to break it.

Codeforces is now a place to practice our reading and googling skills.

i was checking whether gcd of a,b divides n.. if it does answer always exist.. this is where i was wrong.. in ax+by=n x and y can be negative but they cannot be here.. costed me 6 wrong submissions :(

In c we have to first check if any non negative integral solution exists to the equation ax+by=n;
if not then print -1;
else lets say a*x1+b*y1=n;
you have to x1 cycles of length a and y1 cycles of length b.That's all i think.
In the cycle edges will be between i to p[i]

You can make a small draft on the 1st pretest based on what the problem gave you. You will figure out: if g(i) = A, the i-th number of the permutation is within a loop of A element(s).

Like, in the permutation [2, 3, 4, 5, 1], surely g(i) = 5 for all members, as:

f(2, 1) = 3

f(2, 2) = f(3, 1) = 4

f(2, 3) = f(3, 2) = f(4, 1) = 5

f(2, 4) = f(3, 3) = f(4, 2) = f(5, 1) = 1

f(2, 5) = f(3, 4) = f(4, 3) = f(5, 2) = f(1, 1) = 2

Similar to all other numbers.

So, all N members must be divided in a way that there are x cycles of size A, and y cycles of size B (x and y are non-negative integers, and x*A + y*B must equals exactly N).

Think about it like this. The problem asks you to choose a permutation P so that if you do i=P[i] A/B times i gets its initial value. For instance if A is 3, and P={2,3,1} if you apply the operation 3 times for i=1, it becomes 1 again. If you think about it, if you apply that operation on i A/B times and it becomes i in the end, then so will applying the operation A/B times on P[i], or P[P[i]]. You can think of it as a graph, with an edge from i to P[i]. So in the end you have to make cycles of length either A or B.

It's just a horrible nightmare ...

Yes, the inspiration is similar for both.

Hey man I saw your code and it looked fine. Maybe add the space and integer within a single printf? that might be faster.

I think it might due to the gcd, but I don't know why.

I use the same method and get RE on pretest 8.

Finally, I found that it doesn't need to use gcd to solve something like ax+by=gcd(a, b), we could just enumerate x, then I got AC.

You can make a small draft on the 1st pretest based on what the problem gave you. You will figure out: if g(i) = A, the i-th number of the permutation is within a loop of A element(s).

Like, in the permutation [2, 3, 4, 5, 1], surely g(i) = 5 for all members, as:

f(2, 1) = 3

f(2, 2) = f(3, 1) = 4

f(2, 3) = f(3, 2) = f(4, 1) = 5

f(2, 4) = f(3, 3) = f(4, 2) = f(5, 1) = 1

f(2, 5) = f(3, 4) = f(4, 3) = f(5, 2) = f(1, 1) = 2

Similar to all other numbers.

So, all N members must be divided in a way that there are x cycles of size A, and y cycles of size B (x and y are non-negative integers, and x*A + y*B must equals exactly N).

Strangely enough, the standings site works quite fine. All other sections of the contest site failed to load.

We too:P

Yes, in O(k log(k)) using FFT. The idea of stirling numbers is same as in this problem

BTW, discussing this approach with Ancient_mage he gave another hint.

We now know that our answer is in form 2^n - k * P(x) where deg of P(x) is exactly k. So we can easily interpolate it in runtime calculating values of P(x) at k points straightforward.

how did you get the idea of differentiating and substituting x = 1?

mentioned above, but my comment seems to be helpful for you.

I'm not good at coding this part : 'and so on and so on'

So I used more mathematical technique.

Let's denote 2ⁿ = B[0]

n × 2^n - 1 = B[1]

n(n - 1) × 2^n - 2 = B[2]

...

so that B[i] = 2^n - i × n × (n - 1) × ... × (n - i + 1)

Now, i calculated stirling numbers using dp, since it has the recurrence relation : S(n + 1, k) = k × S(n, k) + S(n, k - 1)

And then, to calculate , we just need to calculate , because of famous formula of stirling number (of course second kind).

I hope my comment helped you. Sorry for my bad english. Have a nice day!

UPD: thanks for your help! Now I get to know how to type cleaner :)

How to make a contest?

Leave first 3 problems.

Make an ok D problem, but make it harder by twisting the statements so that it is difficult to parse.

Copy problem E.

Make an obvious problem F.

Again copy idea of problem G from Div1 E (atleast you accepted it above).

Best part give less time to participants for the problem so that it looks less people were able to solve your harder problems and your contest looks good. Huh!, when will you make good contest? I generally give up seeing contest like this.

I also was amazed after seeing that because kevinsogo discussed it in the IPC camp. And with two setters in the camp,then I thought may be it was intendedly made around the concept of that formula.

F just combining convex-hull-trick and smaller to large (very innovative idea) and G some observation from another problem and its reduction to a discussed problem several times (also very innovative).

This problem was my idea and I agree I should have checked the problem on Google before adding it. Apologies.

I thought the problem was really good, and deriving the formula was not that tough(Though I could not get AC in contest time due to a silly mistake :P) but it is disheartening to see so many AC's, courtesy of google. Nevertheless, interesting problem.

What happens if A*i overflows an int?