### gridnevvvit's blog

By gridnevvvit, 5 years ago, translation, ,

Hello Codeforces!

Soon you are lucky to participate in Codeforces Round #302, and I am writer of this contest.

I want to thank Max Akhmedov (Zlobober), Alexander Ignatyev (dudkamaster), Danil Sagunov (dans) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring will be next:

1. Div1: 500 — 1000 — 1750 — 1750 — 2500
2. Div2: 500 — 1000 — 1500 — 2000 — 2750

Contest finished, congratulations to winners:

Div1:

Div2:

Editorial

• +268

 » 5 years ago, # |   +42 "you are lucky to participate in Codeforces Round #302" I think I am lucky to participate all Round :D
 » 5 years ago, # |   -36 I hope senpai will notice me :)
 » 5 years ago, # |   -27 That's strange! Contests are starting later and later in my country (first 8:00 pm, then 8:30 and now 9:00!), but the time in Codeforces' contests page is the same! Do the time modes in countries change so frequently?!
•  » » 5 years ago, # ^ |   +51 Seems that it's your country where time zones are changed frequently :)
•  » » » 5 years ago, # ^ |   +37 Dress Colour Is Blue-Black
•  » » » » 5 years ago, # ^ |   0 Colour is not important. There is more important things ;-)
•  » » 5 years ago, # ^ |   +4 It seems Chinese students are lucky because we always do it in 00:30am.LoL~~~
 » 5 years ago, # |   +9 Where are these coders ?! Just 2555 registrants for now ?!
•  » » 5 years ago, # ^ |   -21 Because this contest is Div.1 and Div.2 so Div.1 contesters can not give Div.2 contest with their other accounts :\
•  » » 5 years ago, # ^ |   +33 I re-checked my email right now, I didn't received notification about this round. I am visiting CF quite often, so I knew about contest anyway; but some people may actually miss round becuase of missing notification.
•  » » » 5 years ago, # ^ |   0 Yeah I didn't get one too.
 » 5 years ago, # |   0 One more time. A good round on codeforces good luck and have fun everyone!!!!! who do you think will win this round? someone in special ??
•  » » 5 years ago, # ^ |   -8 In div2 I will try :)
 » 5 years ago, # | ← Rev. 2 →   -7 I hope a nice contest with interesting problems for all the participants.
 » 5 years ago, # |   -10 hope problem A isn't going to be HACKY! :D
•  » » 5 years ago, # ^ |   -7 why minuses??
 » 5 years ago, # |   -47 Hoping to become gray/newbie
 » 5 years ago, # |   +9 Hoping good results and high ratings... and a lot of hacks!!!
•  » » 5 years ago, # ^ |   +18 Happy New Year!
 » 5 years ago, # | ← Rev. 3 →   -21 god take me to hell, i got 6 rejections coz i forgot else 'no' statement -_- in AWhat a great night, 5 wrong submissions in B -_- .. ended up with lower score than those who solved only A
 » 5 years ago, # | ← Rev. 5 →   +44 I only say I must give up
 » 5 years ago, # |   0 Are all samples included in the pretests or just the first one?
•  » » 5 years ago, # ^ | ← Rev. 4 →   -9 Edit: my comment is wrong.
•  » » » 5 years ago, # ^ |   +8 You are wrong, it is our strict rule to always put samples as the prefix of pretests following in the same order.
•  » » » » 5 years ago, # ^ |   0 Sorry... Don't know what made me understand samples as "All test cases"
 » 5 years ago, # |   +3 Problem B confusing statement cause me a wrong submission. Should codeforces neglect the wrong submission before the announcement ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 oh if we maximize also it gets accepted.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 yeah, it is extremely rare that a problem description (in this case div2 B) is changed multiple times during the contest.
•  » » » 5 years ago, # ^ | ← Rev. 4 →   +5 The description that you posted was absolutely correct and unambiguous, you should not have clarified or changed anything. The current description is wrong://start descriptionWe will call a set of sand cells to be island if it is possible to get from each of them to each of them by moving only through sand cells and by moving from a cell only to a side-adjacent cell. The cells are called to be side-adjacent if they share a vertical or horizontal side. It is easy to see that islands do not share cells (otherwise they together form a bigger island).//end descriptionNothing in that description says that a proper subset of an island isn't be an island. Not only is it not "easy to see" that islands don't share cells, it's wrong: if they share cells, they form a bigger island, but they're still islands anyway.
•  » » » » 5 years ago, # ^ |   +10 That's what I mean by less formal. Of course you are right but the saddest part is that tens of questions per minute almost immediately disappeared when we rewritten the statement in such informal manner.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -8 I don't understand. Is this an island? SSS SLS SSS It does not satisfy rule 3, you can still add some cells to the set. (Please correct me if I am wrong)I understand that you just wanted to say "a smaller subset of cells of an island is not an island". But the definition is problematic here, because, unlike the usual graphs with nodes and edges, you have "sea cells" and "land cells" here.The first clarification doesn't help too (it even reinforced the feeling that you have to add as many cell as possible.) The island is the maximal set of sand cells on existing picture (meaning that you can add no new cell from the existing picture withoutAlso an alternative way to clarify things is to add an extra sample that contradicts the belief.
•  » » » » 5 years ago, # ^ |   0 You cannot add anything because adding an 'S' will not extend the set because it is not covered with sand.
•  » » » » » 5 years ago, # ^ |   0 I see. Thanks.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 PlayTheGame is telling everything correctly above. Regarding the alternative way to clarify things: in this case I don't see how adding another sample could have saved the situation since the main confusion already happened because of the first sample test.
•  » » » » » 5 years ago, # ^ |   0 Thanks, I agree. I got confused too.I think next time better avoid the terms set and connected component in Div 2 A, B as there are many contestants from middle school who never learned about sets, and some contestants are not familiar with graphs (in a problem which does not require knowledge in graphs). They are grey, green and blue after all.Thanks for the hard work and explaining to me.
 » 5 years ago, # |   +24 What is the hack test of problem D in div1?? I think my solution is correct :(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 You can let your code run this case:2000001 2 2 2 ... 2 2 2
•  » » » 5 years ago, # ^ |   +8 My output for your test is : 543973825 87947641 543973825 543973825 543973825 ... Is this correct?
•  » » 5 years ago, # ^ |   +34 A hack against division via multiplicative inverse: (ideone)How to construct it: factor 1000000006: 2 500000003 factor 500000002: 2 41 41 148721 factor 148720: 2 2 2 2 5 11 13 13 So, to get a subtree with answer 148720, we have to unite eight chains of lengths (2-1) (4 times), (5-1), (11-1) and (13-1) (2 times). After that, the subtree contributes a multiplier of 148721 to its parent. Proceed with constructing 500000002 from three short chains and the 148720 subtree... and so on.
•  » » » 5 years ago, # ^ |   +29 I constructed such test using binary representation of MOD: divide it by 2 while possible and add subtree with one node. when it becomes odd, subtract 1 and build new subtree with it
•  » » » » 5 years ago, # ^ |   +5 Thanks for the tip, that's a lot cleaner :) .
•  » » » 5 years ago, # ^ |   +8 There is an easier way of getting it, as you can easily add +1, by adding one more edge. 1000000006=6+10^9=6+(1+3*3)^9
 » 5 years ago, # |   +37 I am one of those, who was registered, but didn't participate, because.. there were no any strong ideas in any problem.. Imho, there should be at least one easy enough problem in Div.1 in order to have a more honest rating.
•  » » 5 years ago, # ^ |   +35 Problem Div.1A is a typical dp problem, isn't it?
•  » » » 5 years ago, # ^ |   +9 I don't think so: the naive solution, which I could generate, was O(n^4) and after optimization worked 5 secs at max test. I could not invent any O(n^3) approach during the whole round :)
•  » » » » 5 years ago, # ^ |   +16 So, you still think that you didn't participate because the problems were boing or because you get scared by the first problem, which, as far as I can see, you weren't able to do? N ^ 3 was the typical dp, and I heard that there is a solution in N ^ 2 too.
•  » » » » » 5 years ago, # ^ |   0 Because I could only solve A in N^4 and have not enough time to finish D.
•  » » » » » » 5 years ago, # ^ |   +8 D could be solve writing a very short code.You said in the above coment that the problems didn't have any strong ideas.I think that they were preety cool E seems awesome even tought I didn't solve it.I couldn't solve C and B was very interesting(In my opinion).You insulted the contest just because you couldn't solve A...
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 No, you get me wrong: the problems were interesting, but I could not find any solution of them, which i sure enough to code or submit.
•  » » » 5 years ago, # ^ |   0 Its a variant of knapsack with repetitions allowed.
 » 5 years ago, # |   +59 you are lucky to participate in Codeforces Round #302 he saidGood luck and have fun he said:(
 » 5 years ago, # |   +8 Did better than usual, fun problems! Maybe I'll become Green again!
 » 5 years ago, # |   0 How to solve Div2 C Writing Code?
•  » » 5 years ago, # ^ |   0 it must be dynamic programming.. my code keep getting WA on pretest 6 anyway :(
•  » » 5 years ago, # ^ |   0 f[j][k] — count of plans with j lines and k bugs. f[j][k] = (f[j][k] + f[j-1][k-a[i]]) % mod
•  » » 5 years ago, # ^ |   +1  MEM(dp,0); dp[0][0]=1; FOR(i,n){ FOR(j,m){ for(int k=0;k<=b-a[i];k++) dp[j+1][k+a[i]]= (dp[j+1][k+a[i]]+dp[j][k])%v; //dp[i][j] where i represents the number of lines and j represents the number of bugs. } } ll ans = 0; for(int i=0;i<=b;i++) ans = (ans + dp[m][i])%v; I got WA 6 because I was running the k loop upto b (instead of b-a[i]) which was causing WA.
 » 5 years ago, # |   -27 Problem B was quite confusing. Also the announcement just changed the problem. I think this round should not be rated
 » 5 years ago, # |   +19 I guess almost all solutions will fail on testcase when divisibility by 109 + 7 was involved. I thought that my code handled it correctly, but unfortunately not and I was hacked probably using such testcase.
•  » » 5 years ago, # ^ |   0 I was hacked also by such a testcase. How can we deal the problem when the number is divisible by 1000000007?
•  » » » 5 years ago, # ^ |   +11 One way of doing it is keeping then number in form a·(109 + 7)b. When it is necessary to divide by 109 + 7 reduce b, otherwise multiply a by modular inverse.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +16 You can't do this in this manner.Of course we can't keep a explicitly, because it will grow too large. We also can't keep just the reminder a%109 + 7, because if you have some number x in this representation then you don't know representation of x + 1.
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   +8 We can actually do it in this particular case. When we pass this value to a child of a vertex, all what we need to know is whether it is zero or not(modulo 10^9 + 7). If it is not zero(that is, b = 0), a mod 10^9 + 7 is obviously a correct value. If it zero(that is, b > 0), it is, again, correct, because it is 0 regardless of a. Put it another way, we never need to add one to a number in this representation.
•  » » » » » 5 years ago, # ^ |   0 How to do it, if is not possible to represent x + 1 using the x value of that representation?
 » 5 years ago, # | ← Rev. 2 →   0 Anybody else who got WA #11 on Div2 C?
 » 5 years ago, # | ← Rev. 3 →   +26 I wrote (almost) correct algorithm for B and D, expecting it to pass. Then I tried to solve C for like 20mins and still have no idea how to solve it. So I decided to code whatever greedy & dp comes to mind (I first code some DP, which got WA5, so I added some greedy).Now I failed B & D, but my C is correct.So surprised...
•  » » 5 years ago, # ^ |   0 What sort of greedy? I just used set cover.
•  » » » 5 years ago, # ^ |   0 Uhm, it's very complicated to describe in words, but I'll try.So first, about the DP solution: Let's call f(i, S) = minimum cost after we used first i characters, to make the set of strings S good. For each (i, S), I tried each character c. Let S2 be the set of strings where the (i+1)-th character is c --> I use f(i,S) to update f(i+1, S | S2) Note that I always use whole set S2, which is obviously wrong. So I updated my DP, allowing adding single character at a time, using min(cost to change this character, cost to change all same characters),which I think must still be wrong, and I think the correct thing to do here must be considering all subsets of S2.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 If I'm reading your code right, when your DP updates mask | TWO(x) using a single character, mask | TWO(x) hasn't been processed yet, so it can add another single character when you get to that mask. So your code actually is considering all subsets, and it is actually the correct solution (iterating over all subsets would clearly TLE).
•  » » » » » 5 years ago, # ^ |   0 But how can adding single element at a time like this be correct? In case I add 2 strings x and y with the same character c (at position i), the cost that I'm adding equal: min(a(x,i), sum(a(z,i) where s(z,i)==s(x,i)) + min(a(y,i), sum(a(z,i) where s(z,i)==s(y,i)) In case sum(a(z,i)) is smaller, I added a(y,i) twice.
•  » » » » » » 5 years ago, # ^ |   +8 In case sum(a(z,i)) is smaller, that means update(f[i][mask | maskSet[i][c]], t + costSet[i][c]); is strictly better than your single character update, so that doesn't matter.
•  » » » » » » » 5 years ago, # ^ |   0 Thanks. I'm happy to see that my code is actually correct =)
 » 5 years ago, # | ← Rev. 2 →   +131 i cant be happy anymin
•  » » 5 years ago, # ^ | ← Rev. 5 →   -8 I was in similar situation, but a bit luckier :D
 » 5 years ago, # |   +2 You should not maximize the sizes of islands.That was after a lot of WAs. -_-
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 I think case 1 itself was self-explanatory that it is not necessary to maximize the sizes of islands. If we had to maximize the size of islands, one of the possible answer could have been: YESLLLLLLLLLLSSSSSLLLLLLLLLL
•  » » » 5 years ago, # ^ |   0 This is exactly what I asked as a question just before the first announcement.
 » 5 years ago, # |   +10 O(NMB) is too slow for A Div1? I got TLE.
•  » » 5 years ago, # ^ |   +5 My O(NMB) solution works 500ms on fpc. What language are you use?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 I changed your solution, now its get AC 11034034
•  » » » » 5 years ago, # ^ |   +10 long long -> int OK, fine, thanks...
•  » » » » » 5 years ago, # ^ |   0 Using mod2 can save you the copying part like http://codeforces.com/contest/544/submission/11036246
•  » » 5 years ago, # ^ |   +5 Same here. Can't understand why the time limit is set so strictly time and again.
•  » » 5 years ago, # ^ |   0 What was the approach to solve it?
•  » » » 5 years ago, # ^ |   0 dp[i][j][k] = No of ways for first i persons to write j lines and causing k bugsdp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k-a[i]]
•  » » » » 5 years ago, # ^ |   0 I got a memory limit exceeded with that approach. Allocated an array of 500 * 500 * 500.
•  » » » » » 5 years ago, # ^ |   +1 Notice that dp[i] depends on only dp[i-1]. Hence you can do the dp with just M*B memory. See my accepted solution for more details.
•  » » » » » » 5 years ago, # ^ |   0 Yeah, that's the catch! Thanks :)
•  » » » » » » 5 years ago, # ^ |   0 can you explain more about "Notice that dp[i] depends on only dp[i-1]" please?
•  » » » » » » » 5 years ago, # ^ |   0 Well if we are in state (i, j, k) we can either transition to (i + 1, j, k) or (i, j + 1, k + a[i]). So the calculation of a state (x + 1) only depends on x and nothing else.
•  » » » » » » » » 5 years ago, # ^ |   0 Thank you
 » 5 years ago, # | ← Rev. 2 →   +22 The time limit for A is way too tight.I suppose there was a 500 500 500 case in the pretest. Branch predictor and memory causes it to TLE in system tests. When I resubmit the same code, case 7's time increased from 25xx ms to 29xx ms.UPD: gridnevvvit has replied that using long long instead of int causes solution to TLE. I strongly believe that the jury should NOT test for such differences.
•  » » 5 years ago, # ^ |   +7 Yeah, I have similar issue as I see.
•  » » 5 years ago, # ^ |   +34 What is the reason to make array size as a power of 2? It leads to problems with cache.For example, you can increase 512 to 520 and got Accepted: 11026552 and 11034250.
•  » » » 5 years ago, # ^ |   +8 Thanks for the idea. Next time I won't make it power of 2.I never thought that I could get TLE due to branch predictor behavior / cache collision.
•  » » » 5 years ago, # ^ |   +36 Why exactly does this happen?
•  » » » » 5 years ago, # ^ |   +24 Because cache internally uses a hash function based on several least significant bits of memory block address. When the second dimension is a power of two, accessing a[i+1][j] will most likely result in a hash collision that will slow down everything.More info here: http://danluu.com/3c-conflict/
 » 5 years ago, # |   0 How is Div2 D / Div1 B supposed to be solved?
 » 5 years ago, # |   +5 Rule 3 : Ignore rule 3 XD
 » 5 years ago, # |   +2 Does anyone know when the ratings will be updated?
 » 5 years ago, # |   0 Worst feeling of missing Rank-1 just because you kept the array size in Problem A one less than what is required. Silly mistakes!! :\ :(
•  » » 5 years ago, # ^ | ← Rev. 3 →   +32 Hey, dude, I just saw that your code in Problem A so perfectly repeats my. I'm not saying that you are cheater, but tell me: "How?"UPD: If someone wants to see that:
 » 5 years ago, # |   0 I wonder if BFS was an overkill for DIV 2 Probelm B? Also tricky testcase. Watch out for number of island =0! eg-> 1 0. I messed up due to this. COrrected it now to get AC :/
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 BFS was certainly an overkill for this problem. You just have to create islands skipping one cell after each island. A simple traversal of O(n*n) does the job.
•  » » » 5 years ago, # ^ |   0 Yeah. Applying BFS in the grid just seemed so intuitive. Once you had set required islands to 'L' just break out. Anyways yeah a simple traversal is much better. Setting an odd-even counter for each row for no clashing islands above or below. Thanks (y)
 » 5 years ago, # |   0 543D - Road Improvement reminds me the 3rd problem of APIO 2014.
 » 5 years ago, # |   0 Problem — AWhy my Solution skipped? — 11027863
•  » » 5 years ago, # ^ |   0 because your solution like another solution :D
 » 5 years ago, # |   +13 What is the complexity of this solution 11033699 for Div.1D ?
•  » » 5 years ago, # ^ |   +5 O(n2).In case 39, the calls calc(0, false), calc(1, true), calc(2, true), ..., do O(n) operations each.
•  » » » 5 years ago, # ^ |   +15 It looks that case 39 is my hack :-)
•  » » 5 years ago, # ^ |   +5 Well, I think it's sigma(deg(i)^2), which can be O(N^2) in worst case.
 » 5 years ago, # | ← Rev. 4 →   -13 Is it written anywhere that today's contests are unrated? seems something is missing in the highlighted area which exists in other rated contests! UPD: Actually I wanted to tell about rating changes, but some reason the picture had not shown. However, Ratings are updated and all confusion went out of the air!
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 Highlighted area like?
•  » » » 5 years ago, # ^ |   0 Hello mihir, Sorry, for some reason, the attached picture was not shown. The picture link is here. But now it is showing and all things are going like other usual rounds. Thanks. :)
 » 5 years ago, # |   +10 I wish I had fixed my hacked B 30 seconds earlier......
 » 5 years ago, # |   +16 What was the official solution of E. My O(S(32 + N / 32)) passed with 3.7 seconds and 54MB.
•  » » 5 years ago, # ^ |   +21 My solution works in and uses linear amount of memory
•  » » » 5 years ago, # ^ |   -8 Then why 7 seconds time limit? Is there a huge constant or something?
•  » » » » 5 years ago, # ^ |   +8 My java solution works in about 4 or 5 seconds
•  » » 5 years ago, # ^ |   +6 where is editorial??
 » 5 years ago, # |   +3 Can someone explain why my Solution on Div2 B got a TimeLimit in the first Testcase? On my Computer i got an solution instantly and uploaded it twice in the contesthttp://codeforces.com/contest/544/submission/11031166I noticed that i have an WA as well, but there wasn't enough time to fix both...
 » 5 years ago, # | ← Rev. 2 →   +5 /**/
 » 5 years ago, # |   -36 What an awful contest?!
•  » » 5 years ago, # ^ |   -13 Why do you think so?
 » 5 years ago, # |   +8 I didn't receive email notification for this round :(
 » 5 years ago, # |   -8 My code (for Div1 D) is getting WA. I couldn't find it. What do you think is my mistake?Submission: 11058128
•  » » 5 years ago, # ^ |   0 0 has no mod inverse.
•  » » » 5 years ago, # ^ |   0 So, it's not possible to do it by dividing, I can't fix it, right?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 I think so. In my solution, I do extra preprocessing during build to get the result by only multiplication. Edit: You can use mod inverse to solve this problem too, but you should treat the cases containing "dividing 0" specially. This can be done by recording more data in your "build" function.
 » 5 years ago, # | ← Rev. 2 →   -43 Codechef's snackdown is here.Prizes:1) For Non-Indians:1st : Prize: Macbook Pro for team members2nd: Prize: Drone Quadcopters for team members3rd: Prize: Go Pro Cameras for team members2) For Indians1st: Prize: 3 Lakhs + Job offer with directi + Goodies2nd: Prize: 2 Lakhs + Job offer with directi + Goodies3rd : Prize: 1 Lakhs + Job offer with directi + Goodies
 » 4 years ago, # |   0 Why the memory limit is 64MB, not 256MB, in Div.1 E?