### TooDumbToWin's blog

By TooDumbToWin, 11 months ago, ,

Hello, Codeforces!

I would like to invite you all to the International Coding Marathon 2018, under the banner of Technex'18, IIT (BHU) Varanasi. It will take place on Thursday 15th February 2018, 20:05 IST. The contest will be held as a combined Div.1+Div.2 round which will be rated for participants from both divisions.

The problemset has been prepared by me (praran26), dark_n8, hitman623, dhirajfx3, karansiwach360 and enigma27. We would like to express our heartiest thanks to gritukan and KAN for their constant help in preparing the contest and MikeMirzayanov for the amazing Codeforces and Polygon platforms. We also thank AlexFetisov and winger for their invaluable help in testing the problems.

## Prizes

• Overall 1st place: INR 35,000
• Overall 2nd place: INR 25,000
• Overall 3rd place: INR 15,000
• 1st place in India: INR 10,000
• 2nd place in India: INR 8,000
• 3rd place in India: INR 6,000
• 1st place among IIT (BHU) Varanasi freshmen: INR 1,000

Participants will have 2 hours to solve 7 problems. The scoring distribution will be announced soon.

Good luck everyone! Hope to see you on the leaderboard.

Update: Scoring is 500 — 1000 — 1500 — 2000 — 2500 — 2500 — 3000

Update 2: Thanks to all participants and congratulations to all the winners. The winners, who are eligible for prizes, will soon be contacted regarding the same.

Overall top 10

Indian top 5

Some problem statements were not clear. We deeply regret the inconvenience caused.

The editorial has been posted here. This was first contest set by most of us, so please help us do better next time by filling this form.

•
• +261
•

 » 11 months ago, # |   +9 Is this like IIT BHU's contest — Manthan ?
•  » » 11 months ago, # ^ |   +29 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.
•  » » » 11 months ago, # ^ |   +26 Oh, I see .. so the same people are organising ?In Manthan, I enjoyed problem B - Marvolo's Gaunt Ring a lot — It had two beautiful solutions.I hope this contest is just as good as the previous ones !
•  » » » » 11 months ago, # ^ |   +15 Yes, the same people are organising it.
•  » » » » 11 months ago, # ^ |   +46 I hope it's better...
•  » » » » » 11 months ago, # ^ |   +1 If you wanna win prize you should be Legendary Grandmaster or Indian )))
 » 11 months ago, # |   -16 wow
 » 11 months ago, # |   +13 Here is the link to the previous ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)
 » 11 months ago, # |   +1 What is INR?
•  » » 11 months ago, # ^ |   0 Indian rupee.
•  » » 11 months ago, # ^ |   +2 1 USD = 63.99 INR 1 Euro = 79.53 INR
 » 11 months ago, # |   +2 2nd rated contest in 2 days, YaY
•  » » 11 months ago, # ^ |   +26 This is 2nd of 4 rated contests(for Div. 2) in 4 consecutive days.
•  » » » 11 months ago, # ^ |   0 nice
•  » » 11 months ago, # ^ |   0 And there is educational round (rated) tomorrow :)
 » 11 months ago, # | ← Rev. 2 →   -69 tourist will not participate i guess
 » 11 months ago, # |   -83 This contest it will be good because of Indian rupees :)
•  » » 11 months ago, # ^ |   -14 Money is good everywhere.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 OK no problem that was't great because of the Indian rupees :(
 » 11 months ago, # | ← Rev. 2 →   0 Can't guess prizing announcement is inspiring or despiring. Hope a thrilling cup contest as usual.
 » 11 months ago, # |   +12 Can I say that happy Lunar New Year ……
 » 11 months ago, # |   +14 Will it be a hackforces？
 » 11 months ago, # |   +33 After the disaster yesterday where I failed systest on two problems (the pretests are really too weak), I decided to skip the Chinese New Year celebration and try to get my rating back on this one. Good luck everyone.
 » 11 months ago, # |   +62 In my timezone, the contest will end at 23:35, so I could enjoy both of them :D.
 » 11 months ago, # | ← Rev. 2 →   -39 deleted
 » 11 months ago, # | ← Rev. 2 →   0 Atleast 2 hours 30 min contest would have been better since there are 7 questions to solve.
•  » » 11 months ago, # ^ |   +1 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.
 » 11 months ago, # |   +9 I have one question praran26. If Indian user get 1'st place at Overall, so it says that he(she) is 1'st plase in India. He(She) get INR 35,000 + INR 15,000?
•  » » 11 months ago, # ^ |   +41 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.
 » 11 months ago, # |   +7 I can't de-register myself from the contest. I get a pop-up saying that I've at least made one action in the contest. (I really don't know whats this suppose to mean). I just hope it's not rated for me!
•  » » 11 months ago, # ^ |   +8 Just don't submit in the contest and it won't be rated for you. :)
•  » » 11 months ago, # ^ |   +7 UPDATE- I'm able to de register now.
 » 11 months ago, # |   +60 Feels like tourist is coming, cause of Um_nik's danger *_*
 » 11 months ago, # |   -25 Is it rated?
 » 11 months ago, # |   +83
•  » » 11 months ago, # ^ |   0 Dude, accurate af :D
 » 11 months ago, # |   0 Auto comment: topic has been updated by praran26 (previous revision, new revision, compare).
 » 11 months ago, # |   -23 Contest prepared by Indians means, It's going to be Mathematical .
 » 11 months ago, # |   -11 True thatI will become a specialist after this contest
•  » » 11 months ago, # ^ |   0 Ha-ha
•  » » » 11 months ago, # ^ |   0 He is a specialist now.Not laughing anymore, are you?
 » 11 months ago, # |   -14 rating-=INF;
 » 11 months ago, # |   -36 Jai Hind!
 » 11 months ago, # |   +14 One of problemsetters is enigma27, contest will be with hacks (-_-)
•  » » 11 months ago, # ^ |   +4 @enigma27 see this :P
•  » » 11 months ago, # ^ | ← Rev. 2 →   +9 why do you think so?
•  » » » 11 months ago, # ^ |   +73 During the Second World War the Germans used the encryption machine Enigma, which was hacked :D
 » 11 months ago, # |   +1 rating predictor started working
 » 11 months ago, # | ← Rev. 2 →   +27
 » 11 months ago, # | ← Rev. 3 →   +76 A confirmed cheater — .Ali. and his clone Ali_Pi. Shame on you!UPD: Disqualified — only in 3 minutes. Thanks (anyone) for being so incredibly responsive.
•  » » 11 months ago, # ^ |   0 How did he manage to generate all those hackable solutions ?Respect
•  » » » 11 months ago, # ^ |   +9 maybe ... if (a==1&&b==2) print a wrong answer; 
•  » » » » 11 months ago, # ^ |   0 Never think about it. Thank for sharing :D
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +9 More importantly how he managed to be in the same room? isn't that random?edit: if you have many accounts, then its like the birthday paradox where you don't need too many accounts
•  » » 11 months ago, # ^ |   +8 How these two users can enter the same room？
•  » » » 11 months ago, # ^ |   +1 It's kind of luck. Perhaps there is a way to manipulate, but I have no heart to look up for it... ;)
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +34 Estimate the number of rooms using number of registrants. Let it be n. Create n + 1 fake accounts. It is guaranteed that there will be atleast one of his fake account in his room :P
•  » » » » » 11 months ago, # ^ |   +3 This is too much work invested on a rated contest :D
•  » » » » » 11 months ago, # ^ |   +29 no, it's not. multiple fake accounts can end up in the same room.
•  » » » » » » 11 months ago, # ^ |   +3 Oops! You are true.
•  » » » » » » » 11 months ago, # ^ |   +4 for exact number of accounts needed: https://en.wikipedia.org/wiki/Birthday_problem
•  » » » » » » 11 months ago, # ^ |   0 But at least two accounts will be in the same room, so you can write contest in this room on fake accounts
•  » » » » 11 months ago, # ^ |   0 I agree.
 » 11 months ago, # |   +3 How to solve E?
•  » » 11 months ago, # ^ |   +10 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!
•  » » » 11 months ago, # ^ |   +3 I also got it as sum(i=0 to n) (nCi)*i^k, for which I was using the formula given in this paper, https://pdfs.semanticscholar.org/0e88/7120ffcc7d17cea2bf4258a8fdd6d348a17a.pdf! Unfortunately, I couldn't code it.
•  » » » » 11 months ago, # ^ |   0 pdf link is not working , can you give it again??
•  » » » » » 11 months ago, # ^ |   0 Remove the '!' at the end of the link, and it should be working.
•  » » » » » 11 months ago, # ^ |   +1 yeah, sure here it is https://pdfs.semanticscholar.org/0e88/7120ffcc7d17cea2bf4258a8fdd6d348a17a.pdf
•  » » 11 months ago, # ^ |   0 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)
•  » » » 11 months ago, # ^ |   +5 where can i study this technique?
•  » » » » 11 months ago, # ^ |   0 I'm not sure about a source but on the wikipedia page for "Binomial Coefficient", this technique is mentioned for being used to calculate the answer for this problem for the particular case of K = 2.
 » 11 months ago, # | ← Rev. 2 →   +64 As I cannot participate, because I'm at school, I decided to write a short editorial to some of the problems (and also the current class is really boring and I don't have anything better to do).Lets begin with D. The main idea is that we will use binary lifting. Twice. Let's consider the following algorithm — for every vertex u (when inserted) find the closest vertex v above it with w[v] ≥ w[u]. Lets have an array nxt[], such that nxt[u] = v. Then the query will be done by simply jumping to the vertex in nxt[], until our sum becomes larger than X. Obviously this is = .To speed it up, we will have 2 binary liftings. The first on will be for finding the nxt[] and the second one will be for answering the queries. For the first one we will store the 2i-th parent and the maximum weight on the path and for the second one, we will store the 2i-th nxt[] vertex and the sum of the weights on the path. Well that's all and in such a way you can achieve .Now let's continue with F (idk why this problem is F...) .The main idea is to use CHT. Lets have dp[u] — answer for vertex u. Obviously dp[u] = min(dp[v] + a[u] * b[v]) for every . From here we get the straightforward solution. To get a normal solution, we simply notice that dp[v] + a[u] * b[v] is a linear function for a[u]. Well then we need to simply maintain a Convex hull trick, for every subtree. For this we will have DSU on tree. We can either use dynamic CHT or LiChao segment tree for maintaining the lines (LiChao will be much faster, as all X's on which we query are small integers). The overall complexity is .It also can be solved by doing DFS order, and then segment tree of CHTs in each node on it. The complexity again is . Well the round just ended I won't explain my idea for E, and it will be only F and D.PS: How to solve G?
•  » » 11 months ago, # ^ |   +8 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).
•  » » » 11 months ago, # ^ |   +10 I had the same initial observation, but I have no idea how to do the part with finding the number of palindromic partitions. I would really appreciate if someone explains it.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 11 months ago, # ^ |   +13 Yes, this was the solution when problem was made but intended solution uses binary lifting which is much easier.
•  » » » » 11 months ago, # ^ |   +5 Is it like spare table? I was confused because i believed that spare table can only be built with static data.
•  » » » » » 11 months ago, # ^ |   -13 It's not sparse table, because it's O(log N) per query.
•  » » 11 months ago, # ^ |   0 for D, query type 2: number of nodes weight[R] >= weight [ (R -> parent[R] -> parent[parent[R]] -> .... -> 1) ], did i understand correctly?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 D: why is it optimal to take closest v above with w[v] ≥ w[u], when there could be many more nodes xi above with lower weight w[v] > w[xi] ≥ w[u] that we can now not take anymore because of weight constraint?
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +5 It will be illegal because there mustn't be untaken node which is fatter than taken node (path from V0 to root)
•  » » » » 11 months ago, # ^ |   0 Ah right, thanks!
•  » » 7 months ago, # ^ | ← Rev. 2 →   -8 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?
 » 11 months ago, # |   0 How to solve D?
 » 11 months ago, # |   +38 E Observe answer is 2n - k·f(n) where f(n) is a polynomial of degree k. Calculate answer for small values of n and Lagrange interpolate. Is this expected solution?
•  » » 11 months ago, # ^ |   +24 No
•  » » 11 months ago, # ^ |   +16 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.
•  » » » 11 months ago, # ^ |   0 I came to this, too. Couldn't manage to implement it though.How would one go about doing the differentiation and storing the combination of polynomials and exponentials?
•  » » » » 11 months ago, # ^ |   +20 All the intermediate polynomials u will get can be expressed as xa(1 + x)b. One can use dynamic programming to calculate the answer.
•  » » » » » 11 months ago, # ^ |   0 Aaah ok, dp[a][b] stores the coefficient of xa(1 + x)b, and go from there.Was this the intended solution, or was the one with the Stirling numbers the intended solution (or both)? Either way, nice problem!
•  » » » » » » 11 months ago, # ^ |   +5 Yes, it was the intended solution.
•  » » » 11 months ago, # ^ |   +3 it'd be nice if you could share some links about these methods.
•  » » 11 months ago, # ^ |   +5 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.
•  » » 11 months ago, # ^ |   +4 It is possible to write ik as the sum of binomial coefficients for j ≤ k. (see here for explicit formula).Then, we just need to solve the problem for when ik is replaced by , which is doable with a simple combinatorial argument.
•  » » 11 months ago, # ^ |   +20 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.
•  » » 11 months ago, # ^ |   +38 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
•  » » » 11 months ago, # ^ |   +10 Can you please explain what does f[n][j] stand for in your code?
•  » » » » 11 months ago, # ^ |   +11 It is the number of ways to distribute n different marbles between j participants such that every participant gets at least one marble.
•  » » 11 months ago, # ^ |   0 The problem is to find: Break into two sums and use the binomial expansion of (r + 1)^(k - 1) to show that
•  » » 11 months ago, # ^ |   0 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. :)
 » 11 months ago, # |   +26 What is pretest 6 in F?
•  » » 11 months ago, # ^ |   +61 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.
 » 11 months ago, # |   0 Another math contest...
 » 11 months ago, # | ← Rev. 3 →   +37 I'm only 1min away from getting F correct. I found the mistake when there was only 42sec left. I'm so pissed now. I am trying really hard not to cuss.PS: I literally threw my mouse in rage.
•  » » 11 months ago, # ^ |   +8 I was clicking on submit on E with 2 seconds left. Tell me about it.
 » 11 months ago, # | ← Rev. 2 →   +16 I literally was submitting (probably) correct E at the last second ... and didn't make it!EDIT: Luckily I got TLE at test 19. Everything's fine.
 » 11 months ago, # |   +62 It took me 30 minutes and 3 clarification to understand D. Am I the only one who have trouble with statement of this problem?
•  » » 11 months ago, # ^ |   +3 no I've your problem too :(
•  » » 11 months ago, # ^ |   0 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.
•  » » 11 months ago, # ^ |   +7 Codeforces is now a place to practice our reading and googling skills.
 » 11 months ago, # |   -20 i don't like this contest at all ... feel stupid for participating in the round ...
 » 11 months ago, # |   +4 Any corner cases in C?
•  » » 11 months ago, # ^ |   0 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 :(
•  » » » 11 months ago, # ^ |   0 I was also stuck to find non-negative solution to ax+by=n.It was very late to realise that n is 1e6 and we can find it in O(n)
 » 11 months ago, # |   0 Someone please explain me problem C.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +4 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]
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 I solved it that way, and got a TLE in pretest 8.Is the usual way of outputting each integer one-by-one (by cout/printf) not fast enough?EDIT: If anyone still cares, turns out the problem with the code I submitted during the contest was quite subtle: there's an integer overflow I did not notice, i.e. probably not related to speed of output.
•  » » » » 11 months ago, # ^ |   +1 Printf should be fast enough.
•  » » » » 11 months ago, # ^ |   +1 I guess in c++ people usually two lines of code in starting of their main function. ios_base::sync_with_stdio(0); cin.tie(0); 
•  » » » 11 months ago, # ^ |   0 I was not able to implement this simple idea....:(
•  » » 11 months ago, # ^ |   0 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) = 3f(2, 2) = f(3, 1) = 4f(2, 3) = f(3, 2) = f(4, 1) = 5f(2, 4) = f(3, 3) = f(4, 2) = f(5, 1) = 1f(2, 5) = f(3, 4) = f(4, 3) = f(5, 2) = f(1, 1) = 2Similar 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).
•  » » » 11 months ago, # ^ |   0 i figured that out during the contest, but i didn't know how to check that N=x*A+y*B has a solution where x,y are non negative integers
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 At first, initialize x and y with the value of -1.You can run a loop of integer i from 0 to N div A:If N - i * A is divisible to B, then a solution is found. Set x = i and y = (N - i * A) / B and break the loop.After the loop, if no solution is found (x and y are still equals to -1, that means there is no solution), output "-1" and terminate the program.
•  » » » » » 11 months ago, # ^ |   0 yeah i'm so bad lol :D
•  » » 11 months ago, # ^ |   0 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.
•  » » » 11 months ago, # ^ |   0 It came to my mind during the contest, corrrect me please: I thought that the answer will be always P=[1 2 3 ... n] . Suppose x = min(A,B), so in x moves this permutation will always satisfy both function f and g.
•  » » » » 11 months ago, # ^ |   0 I didn't think about it that way but yes, I think you're right.
 » 11 months ago, # | ← Rev. 2 →   +21 Is G kind of similar to this problem: http://codeforces.com/contest/906/problem/E ? (Here, we want to count rather than find min).
•  » » 11 months ago, # ^ |   0 It's just a horrible nightmare ...
•  » » 11 months ago, # ^ |   +4 Yes, the inspiration is similar for both.
 » 11 months ago, # | ← Rev. 4 →   0 Anyone else got TLE in pretest 8 of problem C? How to solve it fast enough, and do we need an output method faster than outputting each integer one-by-one by cout/printf?EDIT: If anyone still cares, turns out the problem with the code I submitted during the contest was quite subtle: there's an integer overflow I did not notice, i.e. probably not related to speed of output.
•  » » 11 months ago, # ^ |   0 Hey man I saw your code and it looked fine. Maybe add the space and integer within a single printf? that might be faster.
•  » » 11 months ago, # ^ |   +3 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.
 » 11 months ago, # |   0 What the problem number C said,i didn't understand.Anyone please explain .
•  » » 11 months ago, # ^ |   0 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) = 3f(2, 2) = f(3, 1) = 4f(2, 3) = f(3, 2) = f(4, 1) = 5f(2, 4) = f(3, 3) = f(4, 2) = f(5, 1) = 1f(2, 5) = f(3, 4) = f(4, 3) = f(5, 2) = f(1, 1) = 2Similar 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).
 » 11 months ago, # |   +15 Unable to enter the Contest.Is any one facing the same problem
•  » » 11 months ago, # ^ |   +2 Strangely enough, the standings site works quite fine. All other sections of the contest site failed to load.
 » 11 months ago, # |   -6 nice contest and good problems:)
 » 11 months ago, # |   +5 I love clear and concise statements. Great contest!
•  » » 11 months ago, # ^ |   +2 We too:P
 » 11 months ago, # |   +34 Can E be solved in O(k*log^2(k)) with some FFTs?
•  » » 11 months ago, # ^ |   +4 Yes, in O(k log(k)) using FFT. The idea of stirling numbers is same as in this problem
•  » » » 11 months ago, # ^ |   0 But precision issues 109 + 7 ?
•  » » » » 11 months ago, # ^ |   +22 No, precision issues can be easily avoided. See idea in this blog. Polynomial multiplication which uses exactly 3 fft calls exists that can find answer modulo any number (not only primes) less than 230.
•  » » » » » 11 months ago, # ^ |   0 thank you
 » 11 months ago, # | ← Rev. 5 →   +19 I've seen lots of DP approaches for problem E (I didn't understand it yet). However I want to share my approach heavily based on math.It's not so hard to see that we want to calculate smth like: Let's start from well known formula:Now we know it's polynomial of x. Let's differentiate it:. Let's denote it as (1).Substituting x = 1 gives us:. Let's denote it as (2).Let's differentiate (1) one more time and set x = 1. We'll get:. Let's call this equality as (3).Summing (2) and (3) we'll get:and so on and so on. The only thing we are left with is to code :) Link to submission: linkP.S. I would be pleased if someone could explain DP approach.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +5 BTW, discussing this approach with Ancient_mage he gave another hint.We now know that our answer is in form 2n - 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.
•  » » 11 months ago, # ^ |   0 how did you get the idea of differentiating and substituting x = 1?
•  » » » 11 months ago, # ^ |   0 I feel like it's standard thing when you want to crack some combinatoric formulas :)
•  » » » » 11 months ago, # ^ |   0 do you know some other problems (not necessarily on an online judge) where i can study this technique? (polynomials and combinatorics stuff)
•  » » 11 months ago, # ^ | ← Rev. 3 →   +3 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 2n = B[0]n × 2n - 1 = B[1]n(n - 1) × 2n - 2 = B[2] ...so that B[i] = 2n - 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 :)
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Thank you, now I got dp approach:) You can use TeX format embracing text with dollar sign.
 » 11 months ago, # |   0 I am very curious about why did i_love_you_bangladesh’s attempts on F and G were ignored. P.S. I have seen during the contest that his G passed pretests
 » 11 months ago, # |   0 TFW in D I have an if for the case to output 0 and I do not update the last...
 » 11 months ago, # | ← Rev. 4 →   +85 All I did in Problem E was to google whether there exists some formula to compute the obvious summation. Within a couple of minutes I found this link and directly copied the Using Stirling Numbers summation mentioned in the second answer.It is sad to see that such (very easily) googlable problems are present as hard problems. I wonder how the testers did not think about checking whether such a thing is easily available online or not.
•  » » 11 months ago, # ^ |   +56 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.
•  » » » 11 months ago, # ^ |   -14 It takes a lot of hardwork to create problems, so we should praise their hardwork. That is what I think.
•  » » » » 11 months ago, # ^ |   +60 Yeah, it takes a lot of hardwork to create problems, but it doesn't take so much to copy them.
•  » » » 11 months ago, # ^ |   0 It seems that given if you were given more time, you could have completed the problemset. So from the next contest onwards, why don't you volunteer to write the editorials.
•  » » » 11 months ago, # ^ |   0 How is F problem obvious to you? You shouldn't have left the contest and tried the problems. So you could have solved them all other than D.
•  » » 11 months ago, # ^ |   +21 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.
•  » » 11 months ago, # ^ |   +8 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).
•  » » 11 months ago, # ^ |   +39 This problem was my idea and I agree I should have checked the problem on Google before adding it. Apologies.
 » 11 months ago, # |   +8 932E - Team Work So now I have to search over research papers for combinatoric summation formulas over the internet to solve a problem in CF ! I bet that 80% of the users solving this problem either knew this formula from before or found it searching over the internet during the contest and very few actually derived this formula in contest time. That's ridiculous ! Our programming skills should be tested in CF, not our googling skills !!!
•  » » 11 months ago, # ^ |   +10 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.
•  » » » 11 months ago, # ^ |   0 I derived it in the contest time also, got WA and sadly it took so much time that I couldn't debug :( And after the contest I noticed that I just forgot to add MOD in a line and in another line an index of an array was mistaken. Other than this, my code was OK and got AC. And there are so many people who knew the trick beforehand and got AC within moments. But again, knowing is a plus point here. I'm just sad that I was so close...
 » 11 months ago, # | ← Rev. 2 →   +78 finally !! i made it in the last moments =)))
 » 11 months ago, # | ← Rev. 2 →   0 Can anyone help me understand why that submission: http://codeforces.com/contest/932/submission/35308268 takes RTE ? Thank you !
•  » » 11 months ago, # ^ |   +1 What happens if A*i overflows an int?
•  » » » 11 months ago, # ^ |   +13 Yes, that was the error. Thank you for your time ! I am kind of sad now that I did that stupid mistake
 » 11 months ago, # |   -7 i guess the answer for problem E is: sum(n!/(n-i)! * S(k,i) * 2^(n-i) ) with 1<=i<=k and S(k,i) is the stirling number of the second kind if we have k integer(distinct integers) and n sets (with distinct index) so we have C(n,i) ways to choose i sets . Also we have i^k ways to puts k integers into these sets. But also there are always some ways are the same. So I think how to count the repeated ways. For chosen i sets, we have S(k,i) ways to puts k integers into these sets and there are no set without any elements. But the indexs of sets are distinct so we have i! permutations for these sets. For n-i remained sets. We have 2^(n-i) ways to choose the set of these set. This step make the repeated ways to put elements I said before. So the answer is sum(C(n,i)*i!*S(k,i)*2^(n-i) ). with 1<=i<=n. But S(n,k)=0 for any k>n so: result=sum(n!/(n-i)!*S(k,i)*2^(n-i) ) with 1<=i<=k
 » 11 months ago, # |   +13 sorry for my bad english. #Lovecommunity
 » 11 months ago, # |   0 Is there a (relatively) easy way to find outhow many div1 members took part in this contest?More exactly,how many (of the 4515 participating members) were div1 before the contest?
•  » » 11 months ago, # ^ |   0 ...and by being a div1 member I meantbeing disallowed to compete in div2 contests (except for out-of-competition participation).
 » 11 months ago, # | ← Rev. 2 →   0 I have a question. Why I'm not get point on this round?. Firstly I solved 6 problems and get 4th position then my gained point go to zero but why? I didn't understand enigma27,[user:paran26] , dark_n8?