Antoniuk's blog

By Antoniuk, 7 years ago, translation,

Hi everybody!

Codeforces round #247 for Div. 2 participants will take place on May 21 at 19:30 MSK. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me(Antoniuk) and Kirill Schetinin(KaiZeR). This is the first round prepared by us and we hope that you will enjoy the round.

We want to thank Gerald and Delinur for helping to prepare the round and MikeMirzayanov for Codeforces and Polygon.

UPD: Score distribution will be the next — 500-1500-1500-2000-2500.

UPD2: The contest is over, we hope you enjoy it)

UPD3: Editorial.

UPD4: Statistics.

Congratulations to winners!

Gl & hf)

• +138

 » 7 years ago, # |   +22 Ukrainian contests are always special , hope it will be a special one too
 » 7 years ago, # |   0 Wish luck for everyone :)
 » 7 years ago, # |   +44 Antoniuk , your chart is quite interesting after you become yellow you drooped to gray then you backed again to yellow , can you tell what is the reason behind this?
•  » » 7 years ago, # ^ |   +5 I think he just share the feelings with gray coders :)
•  » » » 7 years ago, # ^ |   +19 He's gray-friendly :D
•  » » 7 years ago, # ^ |   +11 He tried to draw a heart cardiogram.
•  » » 7 years ago, # ^ |   +5 He didn't drop to grey !?
•  » » » 7 years ago, # ^ |   +2 1200 Exactly Nice catch
•  » » 7 years ago, # ^ |   +1 just for fun = =
•  » » 7 years ago, # ^ |   0 Actually this is not rare :Dhttp://codeforces.com/profile/sillycross
 » 7 years ago, # | ← Rev. 2 →   0 Wow!! if Antoniuk was involved that will be definetly awesome.
 » 7 years ago, # | ← Rev. 2 →   +38 Last contest that Gerald participated was Codeforces Round #104 (Div. 1), Since then, He is preparing contests...
•  » » 7 years ago, # ^ |   +9 Thank you, Gerald!
 » 7 years ago, # |   +6 i am a little bit worried about the problem statement.
•  » » 7 years ago, # ^ |   0 I hope the problem setter will have explanation for the first example for problem A.
•  » » 7 years ago, # ^ |   0 Don't worry it's unrated for you :)
 » 7 years ago, # |   +20 Sereja also comes from Ukraine. He is always setting very attractive problemset. :)
 » 7 years ago, # |   +39 I don't know if it's only me, but the english translations are very bad. I was not able to comprehend problem E at all.
•  » » 7 years ago, # ^ |   +70 I can't understand russian version of problem's E statement, although Russian is my native language.
•  » » » 7 years ago, # ^ |   +23 It looks like this problem much easier to solve than to understand.
•  » » » 7 years ago, # ^ |   +3 I could not understand English statement, because it was not clear. After switching to Russian, failed to understand again. And I thought it is because I was not native Russian speaker. :(
•  » » 7 years ago, # ^ |   +10 I couldn't understand the statement of E.
•  » » 7 years ago, # ^ |   +18 It's not only you. For problems A-D the english translations were alright. For problem E, WTF?? I still don't understand what the problem wants us to do.
 » 7 years ago, # |   0 Problem D. There is no answer if m = 0 and d = 1
•  » » 7 years ago, # ^ |   +5 The statement says there is guaranteed to be a solution for given m, k. Which means that a test with m=0, k=1 will not appear.
•  » » » 7 years ago, # ^ |   +1 what was the solution for problem D?
•  » » » » 7 years ago, # ^ |   +13 i think binary search + dp
•  » » » » 7 years ago, # ^ |   +3 If you try to find the formula for a given n, you will end up with something like (sum of binomials) = m. It can be solved greedily.
 » 7 years ago, # |   +7 I think problem B should be 1000 instead of 1500 !?
 » 7 years ago, # |   +10 Again, like other contests, a lot of newly registered participants (within 10 hours of the contest); but the worst of all is that the first person in standing, containing both div 1 and div 2, is one of those!
 » 7 years ago, # | ← Rev. 2 →   +9 What is that mythical Test #9 in problem D? I can't pass it =\It seems that D and E are way harder than normal for these contests. I solved E because I had code for R-B trees handy, which probably wasn't the expected solution.
•  » » 7 years ago, # ^ |   0 Maybe your program writes "0"
•  » » » 7 years ago, # ^ |   0 That was indeed the case, but I wasn't using binsearch so my solution naturally got the zero. I don't understand the point of this, the goal is to solve the problem and not look for every possible corner case that has very little relation to the actual solution.
•  » » 7 years ago, # ^ |   0 0 2
•  » » » 7 years ago, # ^ |   0 what about editorials?
•  » » » » 7 years ago, # ^ |   +3 Will be published soon after system testing.
 » 7 years ago, # |   +1 What was the approach to solve problem C?
•  » » 7 years ago, # ^ |   0 I used Dynamic Programming
•  » » 7 years ago, # ^ |   0 Compute the total number of ways to break number n into summands which are <= k. Let it be S. Then number of ways to break n into summands which are <= d-1. Let it be R, these ways to break the number are "bad" and should not be counted in the final answer. Thus, the final answer is S-R.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 No , I don't think that will give the correct answer in case when we take modulus along the way.mod = 1000 ; Suppose final S = 1234 and final R = 999 ;but when we will take modulo S%mod — R%mod <= 0 Which will give the wrong answer.
•  » » » » 7 years ago, # ^ |   +6 I gave just the general idea, modulus is the detail of implementation.
 » 7 years ago, # |   -23 This is my first contest :) Hope I will get a high rating :)
•  » » 7 years ago, # ^ |   +21 I do not believe you.
 » 7 years ago, # | ← Rev. 2 →   0 Why did this solution pass systest?Interesting part: REP(i,strlen(s)){ kq+=a[s[i]-'0']; } 
•  » » 7 years ago, # ^ |   0 Interesting!
•  » » 7 years ago, # ^ |   0 if s[i]=='4' then A[s[i]-'0'] is A[4]
•  » » » 7 years ago, # ^ |   +22 strlen(s) works in O(n) time!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 scanf("%d %d %d %d\n",a+1,a+2,a+3,a+4);
 » 7 years ago, # |   +5 Any ideas on how to solve B for a much bigger N? First time i read the problem i thought n <= 10^5
•  » » 7 years ago, # ^ | ← Rev. 2 →   +4 I have solved it in O(N^2) using DP. I think it can't be solved faster. So, n could be somewhere around 2000.
•  » » » 7 years ago, # ^ |   0 What is the runtime (in seconds) for n=2000?
•  » » 7 years ago, # ^ |   0 Same here! Wasted 5 minutes and then solved C before realizing n is always 5.
 » 7 years ago, # |   +6 how this solution AC ?!!! http://codeforces.com/contest/431/submission/6671729
•  » » 7 years ago, # ^ |   +1 48 here same as '0'. Read this http://www.asciitable.com/
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +7 i don't mean that , i mean he made an array of size 4 and used index 4 !
•  » » » » 7 years ago, # ^ |   +7 Doing this results in undefined behavior. So, I guess he just got lucky.
 » 7 years ago, # |   0 Same solution for problem D got AC in MS C++ and WA in GNU C++.66760196676015Why? :(
•  » » 7 years ago, # ^ | ← Rev. 4 →   +6 As for your code, the behavior of X >> i is undefined when i = 64, for the behavior of op1 << op2 and op1 >> op2 is undefined if the op2 is negative, or greater than or equal to the length in bits of the op1. So, you can get AC in both MS C++ and GNU C++ by replacing X >> i with i < 64 ? X >> i : 0 for example.
•  » » » 7 years ago, # ^ |   0 Thank you, I got AC by calling the function with i=63 instead of 64.I found that it's undefined even in MS C++...
 » 7 years ago, # |   -13 Problem C should tell that the number must be positive or something like that. For example 17 mod 5 = 2 = -3. When you say print 17 module 5 I can print -3 too unless you specified that the answer must be positive. After 1:24 I got hacked and immediately submit another. which is now accepted but I lost a lot of point -50 and ~ -450 or -500 for timing.
•  » » 7 years ago, # ^ |   0 the problem asked you to print the number of paths , how it can be negative ?
•  » » » 7 years ago, # ^ |   0 No, the problem asked me to print number of paths module 10^9 + 7.
•  » » » » 7 years ago, # ^ |   +17 http://en.wikipedia.org/wiki/Modulo_operation"The range of numbers for an integer modulo of n is 0 to n − 1."
•  » » » » » 7 years ago, # ^ |   +5 Fair enough! My fault.
•  » » 7 years ago, # ^ |   0 You can blame broken % operator in C++. But don't blame contest authors ;)
•  » » » 7 years ago, # ^ |   0 No! % operator works ok. I write my code in a way which the number could be negative.I corrected it by replacing cout << ...; by cout << (... + 10..7) % 10..7;
•  » » » » 7 years ago, # ^ |   0 That's what I did. I used long long and ( + 10....007) % 10...007 staff. If % operator was mathematically correct in C, there would be no need in jumping through hoops like this.
 » 7 years ago, # |   +7 Wasn't problem A too easy to become a contest problem?!
 » 7 years ago, # |   +7 Nice problems.... :)Nice contest for me... :)Hope to see you again... :)
 » 7 years ago, # |   +1 Can someone please explain the statement of problem E ?
•  » » 7 years ago, # ^ |   +13 The subproblem can be formulated as this: You have an area of land, with h[i] being the height of the i-th section. You want to pour V liters of "rain" on this land (so that the water level is the same for each section that isn't dry). Find the resulting water level.Now you have the initial heights, and a bunch of queries that either change the height of one section, or ask you to solve the subproblem for a given V.
 » 7 years ago, # |   +3 When will the editorial be available??
•  » » 7 years ago, # ^ |   +9
•  » » » 7 years ago, # ^ |   0 Can u explain Random task, bit more clearly.Not able to understand.
 » 7 years ago, # |   0 Is there a way to download the test cases, other than trying to "brute force" it by sending fake solutions? My solution to E fails on one single query on test #28, and all other queries are correct. Very suspicious...
•  » » 7 years ago, # ^ |   0 Try writing big random test generator and brute checker function, and test your solution with it.It seems far more productive that brute forcing tests.
•  » » » 7 years ago, # ^ |   0 Considering it works on all test cases except for one single query, I don't think I would be able to replicate that easily. Besides, I already did that last time I used the same data structure.
 » 7 years ago, # |   +6 http://codeforces.com/contest/431/submission/6672763http://codeforces.com/contest/431/submission/6672950aren't these two solutions same ?
 » 7 years ago, # |   0 can someone explain me why this solution gets WA :6676798 my answer is : (all the paths using edges with weight k or lower) — ( all the paths using edges d-1 or lower)
•  » » 7 years ago, # ^ |   0 Changed 6676977
•  » » » 7 years ago, # ^ |   0 i feel so stupid :| thanks
 » 7 years ago, # |   +6 I like div-2-only contest because I have to compete with the second (or nth) account of the first-division people. No, it is a joke, lol. I don't like div-2-only because that.
 » 7 years ago, # |   0
 » 7 years ago, # |   0 The question A is like this game : Don't tap the white
 » 7 years ago, # |   0 good luck everyone...hope to seee some interesting problems :)