### vovuh's blog

By vovuh, history, 7 months ago, translation,

<almost-copy-pasted-part>

Hello! Codeforces Round #624 (Div. 3) will start at Feb/24/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

Thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for help with testing the round!

UPD: It turned out that in the problem C, such a test exists that the answer overflows 32-bit integer type (int). Since such a test was not in the test set, many participants made such a mistake. We decided to forbid such tests, additionally guaranteeing that the answer fits in int.

UPD2: Editorial is published!

• +116

 » 7 months ago, # | ← Rev. 2 →   -26 [DELETED]
•  » » 7 months ago, # ^ |   0 hahahah!!!!!!!
 » 7 months ago, # |   -18 finally... I am excited
 » 7 months ago, # |   0 Finally a good freaking round
 » 7 months ago, # |   -12 newbies will rock it
 » 7 months ago, # |   -13 Can anyone help me how to hack a solution ? With detail's . Thanks in advance.
•  » » 7 months ago, # ^ |   +6 On the dashboard, click the padlock icon for locking a problem (Note, that you can not send your solution for a problem after locking it). Then go to room results, where you can see roommates codes for the problems you've already locked (you can see a certain solution by double clicking on it in the room results table). After you've opened someone's solution, you can consider it and then hack it. When hacking a code, you're entering some testcase on which that code is most likely going to fail (it may be wrong answer, or running out of time/memory limit). When you want to enter a large testcase, you can send test generator instead of typing it. Test generator must be your program which produces a file with a testcase in it. After hacking a code, you can see hacking results. There are two possible outcomes: "Successful hack" — it means the code failed, and you're rewarded with 100 points for that. Otherwise, it's "Unsuccessful hack" (the code did not fail) and you get minus 50 points for that.
•  » » 7 months ago, # ^ |   +6 In div.3/educational contests, you can not hack any solutions during the coding phase. In the hacking phase which follows the coding phase and lasts for 12 hours, you can hack any solution. Just double-click somebody to view his/her submissions and then click "hack it!" button.there will be no points for successful hacking attempts and no penalties for unsuccessful ones in div3/educational rounds.
•  » » » 7 months ago, # ^ |   -10 So in div3/edu contest. If I failed to hack someone's code, I wont get minus 50 points right ?
•  » » » » 7 months ago, # ^ |   0 No penalties,just hack for fun :)
 » 7 months ago, # |   +15 3 rounds in 2 days is very cool!
 » 7 months ago, # | ← Rev. 2 →   +2 .
 » 7 months ago, # |   0 Hope to solve 4 or more question in this contest
 » 7 months ago, # | ← Rev. 7 →   -8 .
•  » » 7 months ago, # ^ | ← Rev. 2 →   -14 [DELETED]
 » 7 months ago, # |   -9 Div3 gives confidence
•  » » 7 months ago, # ^ |   -17 Yeah have the confidence that i will never be a specialist ever :'(
•  » » » 7 months ago, # ^ |   0 Never say never
•  » » » 7 months ago, # ^ |   -10 you have just read algorithms and solve lots of high rate problems from it and you will become specialist at least :)
•  » » » » 7 months ago, # ^ |   -11 thanks for your suggestion.i'll try my best.
•  » » » » » 7 months ago, # ^ |   -7 if you need help i will help you :)
•  » » » » » 7 months ago, # ^ |   +8 Keep practising & forget about the rating changes.
•  » » » » » » 7 months ago, # ^ |   0 a really good advice for a noon like me. appreciate.
 » 7 months ago, # |   0 ///786///Div 3 is good for newbie like me :D
 » 7 months ago, # |   -6 Is it rated?
•  » » 7 months ago, # ^ |   0 It's rated for Newbies, Pupils and Specialists. It is also rated for Experts who have taken part in at least two rated rounds (and solve at least one problem in each of them).
•  » » » 7 months ago, # ^ |   0 It is not rated for Blues.
•  » » » 7 months ago, # ^ |   +1 That's good.I'll take off in this contest.
 » 7 months ago, # |   0 I don't like only Div.3 contest. Actually most people is more than 1600.
•  » » 7 months ago, # ^ |   +9 But in last div-3 contest there was 9000+ participants!
•  » » 7 months ago, # ^ |   +10 But they can take part out of the competition. It won't decrease the happiness of doing a contest. So Div.3 is very nice since it's easier and more people can have fun!
 » 7 months ago, # |   +11 If you want more contests so please donate the codeforces 1000$or more •  » » 7 months ago, # ^ | 0 Yes Ibrohim_Salohitdinov you are right •  » » 7 months ago, # ^ | +14 But I don't have enough money to donate.Actually I am hungry, for I don't have money to eat rice.  » 7 months ago, # | 0 If i register the contest but will not submit in the contest, will my rating change? •  » » 7 months ago, # ^ | 0 No. •  » » 7 months ago, # ^ | +4 Since you are above 1600 your rating will not change by Div3 rounds like this one.  » 7 months ago, # | 0 Exiting to join the contest <3 Hope that I can solve A-B-C and dont get any stupid mistakes <3  » 7 months ago, # | 0 Let's Hope Everyone gets a positive change in their ratings :)  » 7 months ago, # | +54  » 7 months ago, # | -7 Sorry I am a newbie,I wanted to ask what does it mean "The penalty is 10 minutes".Is it literal that 10 minutes will be deducted from our time,if we have a wrong submission or is it something else? •  » » 7 months ago, # ^ | 0 if you submit a wrong solution and then submit the right solution afterwards, the accepted time of submission will be +10 minutes of that. more wrong answers mean more +10 minutes.. •  » » » 7 months ago, # ^ | -8 Ok Thanks for clearing that. Just a question suppose I submit a wrong solution and then submit a right solution at just the end of a contest what will the accepted time of submission will be, is it going to be more than 2 hours in this case? •  » » 7 months ago, # ^ | 0 Short answer:No it doesn't, it just is basically something that makes your score for that problem worse.Long answer:Basically in Div3 (and Educational Rounds or any other rounds that follow ACM-ICPC format), your score is calculated a bit differently from normal CF rounds. Participants are first ranked by the number of problems they solved. After that ties are broken by a so called "penalty". This penalty has two parts to it: The sum of times of your submissions. The wrong answer penalty times the number of wrong answers on problems that you solved afterwards. (that is if you get a wrong answer on a problem and don't get accepted till the end you wont be penalized for those wrong submissions) A person with a lower penalty is ranked higher.Consider for example the following contest with 3 participants — A, B and C and a wrong submission penalty of 10 minutes: A solves 2 problems, the first at 5 minutes and the second at 30 minutes, with no wrong submissions on either. B solves 2 problems, the first at 5 minutes and the second at 25 minutes, but makes a wrong submission on the second problem before submitting the correct solution. C solves 3 problems, the first at 10 minutes, the second at 40 minutes and the third at 1 hour 20 minutes. So A has solved 2 and has a time penalty of 5 + 30 = 35 minutes,B has solved 2 and has a time penalty of 5 + 25 + 10 = 40 minutes, andC has solved 3 and has a time penalty of 10 + 40 + 80 = 130 minutes.As we sort them first by number of problems solved then by penalty, so the final standings will be: C (3, 130) A (2, 35) B (2, 40) •  » » » 7 months ago, # ^ | 0 nicely explained!!  » 7 months ago, # | 0 It would be great if more div 3 contest held because new competitive programmers can better start. Div 2 contests are quite tough for beginners. Thanks for this contest. •  » » 7 months ago, # ^ | -17 Every week there should be atleast 1 div3  » 7 months ago, # | 0 Schrodinger's Problem Number  » 7 months ago, # | -30 F***K MY LUCK!!! on problem c, my code has diffrent output on CF system than my own!!! And of course it's wrong on CF  » 7 months ago, # | -9 OMG first time I solve D <3  » 7 months ago, # | +21  » 7 months ago, # | +4 How to Solve D? I tried thinking of it in multiple ways, but all my approaches seem to fail. •  » » 7 months ago, # ^ | +9 Fix B.Find A and C greedily. •  » » » 7 months ago, # ^ | 0 Does there exist a proof that this approach will always work? •  » » » » 7 months ago, # ^ | +1 You can simply try all possible solutions in time. code •  » » » » » 7 months ago, # ^ | 0 That's So Cool! I never thought that brute force would pass. •  » » » » » » 7 months ago, # ^ | 0 Well, it was hacked. So don't be too sure yet. •  » » » » » » » 7 months ago, # ^ | 0 How does the hack work? •  » » » » » » » » 7 months ago, # ^ | 0 I'm guessing that it's because you're only going upto $10^4$ instead of $2*10^4$ •  » » » » » » » » » 7 months ago, # ^ | ← Rev. 2 → +1 Ah, I see, the input is limited to 1e4, but not the solution space. Sic shit.So, 10000 100000000 1000000000000 could be a valid answer for some input.Edit: It turns out that a,b,c should be all below 2*1e4, because if not there is a better solution. So, this code uses same algo but works better. •  » » » » » » » » » 7 months ago, # ^ | ← Rev. 2 → 0 What should be the output for : 1 481 777 10000? •  » » » » » » » » » 7 months ago, # ^ | +1 How did you decide the size of solution space ? Why 2e4 ? •  » » » » » » » » » 7 months ago, # ^ | +9 113 385 770 10010  •  » » » » » » » » » 7 months ago, # ^ | 0 One possible sol is allways 10000 10000 10000 for any input where max(a,b,c)==10000.The max diff is 9999*2. So the max value for b and c cannot be more than 20000, whatever a is.Not sure if this counts as a prof ;) •  » » » » » » » » » 7 months ago, # ^ | 0 Why only 2e4 ? How did you come up with that upper bound? •  » » » » » » » » » 7 months ago, # ^ | 0 We only have to show that a goes to A, b goes to B and c goes to C (you can prove this by considering all cases in the number line). Then you can show that B must be less than c+a. This can be proven by contradiction. So actually you only need to test it for 1<=B<=c+a •  » » » » » » » » 7 months ago, # ^ | 0 You need to check values up to 10k + epsilon for test such as73 73 10000 •  » » » » » » » » » 7 months ago, # ^ | 0 How to decide that epsilon value? •  » » » » » » » » » 7 months ago, # ^ | 0 20k should be more then enough (since if go up to 20k we can achieve all values in [0, 10k] with a smaller cost) •  » » » » » » » » » 7 months ago, # ^ | 0 10.5k is enough. not 20k. •  » » » » » » » » » 7 months ago, # ^ | 0 10^4 + 32 is enough. And no less because of: 1 176 3344 10000  •  » » » » » » » » » 7 months ago, # ^ | 0 I_love_chickpea can you please explain, how did you concluded +32 would be enough? •  » » » » » » » » » 7 months ago, # ^ | 0 We can slightly modify the model solution to pick out of answers with minimum distance the one with minimal value C.Now for a fixed triple $A_0, B_0, C_0$ such that $B_0$ is divisible by $A_0$, $C_0$ is divisible by $B_0$ and $C_0 > 10^4$ if there is a testcase for which this triple will be the only valid answer, then one of them will be testcase $min(A_0, 10^4), min(B_0, 10^4), min(C_0, 10^4)$. We can just run the modified solution on this test, if it says the minimum value of $C$ is $C_0$ it means that there is a test, which requires checking values of $C$ up to $C_0$.Now just run it for larger and larger values of $C$. Code#include using namespace std; using pii = pair ; const int nax = 2e4, inf = 1e9; pii get_dist(int a, int b, int c) { pii ans = {inf, inf}; for (int a0 = 1; a0 <= nax; ++a0) for (int b0 = a0; b0 <= nax; b0 += a0) { int c0 = c / b0 * b0; if (abs(c - c0) > abs(c - c0 - b0)) c0 += b0; int cost = abs(a - a0) + abs(b - b0) + abs(c - c0); ans = min(ans, pii(cost, c0)); } return ans; } int main() { const int N = 10000; for (int c = N + 1; ; ++c) { for (int a = 1; a <= c; ++a) if (c % a == 0) for (int b = a; b <= c; b += a) if (c % b == 0) { int an = min(a, N), bn = min(b, N), cn = min(c, N); pii G = get_dist(an, bn, cn); if (G.second == c) printf("Reach (%d, %d, %d) from (%d, %d, %d) in %d moves\n", a, b, c, an, bn, cn, G.first); } printf("done %d\n", c); } } I ran it for $C <= 20000$ and found nothing larger than $10^4 + 32$. •  » » » » » 7 months ago, # ^ | 0 Your solution for D has been hacked but it's still showing in standings •  » » » 7 months ago, # ^ | 0 I fixed A and then find B as A*j and then find C as A*j*f. •  » » 7 months ago, # ^ | ← Rev. 2 → +1 you find all pair of a and b from 0 to 10^4(maybe more for safety) for every pair of a and b you find suitable third number nearest to original c. it probably cost you about n*log(n) for every test case. •  » » » 7 months ago, # ^ | 0 So it will be O(10^8)*100 = O(10^10) operations right ? How did it pass the time limit? •  » » » » 7 months ago, # ^ | 0 No of course. let's call first number is a,second is b. we want a is a divisor of b. so we just start from a then go to 2a,3a,4a.to find every pair of a and b.it's only cost you about nlog(n) •  » » » » » 7 months ago, # ^ | 0 it's just like erastothenes sieve without prime number •  » » » » » 7 months ago, # ^ | 0 No, I am not sure about this. This is n^2. •  » » » » » » 7 months ago, # ^ | 0 errrrr it's running in n+n/2+n/3+n/4+...+1 which is prove less than nlog(n) •  » » » » » » 7 months ago, # ^ | ← Rev. 2 → 0 I'm not sure if i'll get hack xD but i believe in my solution •  » » » » » » » 7 months ago, # ^ | 0 I got your solution, you are right. I just upsolved it now. Sad :( •  » » » » » 7 months ago, # ^ | 0 i think this is (n^2)/2 •  » » » » » » 7 months ago, # ^ | 0 it's n+n/2+n/3+n/4+...+1.not 1+2+3+4+...+n. dont be mistaken •  » » » » » » 7 months ago, # ^ | ← Rev. 3 → 0 Take (1+ 1/2 + 1/3 ......+1/n) as integrating (1/x)dx with limits from 1 to n......you will get log(n) as an answer for the summation for that series.You have ∫1xdx=ln|x|+C (Note that the "constant" C might take different values for positive or negative x. It is really a locally constant function.) •  » » » » » » » 7 months ago, # ^ | +1 Thank you so much. I understood. •  » » » 7 months ago, # ^ | 0 How can this algorithm cost n*log(n)? •  » » 7 months ago, # ^ | 0 Make all the possible combinations (A, B, C) with for-loops and compare them with the given (a, b, c)s.The key is that neither of these three should exceed 10^4. (If they did, they would in itself be not the efficient solution) I have found just a bit fewer than 5X10^5 cases which satisfies (A, B, C). Thus, given that the test cases are 100, 5X10^7 seems like a good deal.Brute force, if applied properly, can be a very powerful tool. •  » » » 7 months ago, # ^ | ← Rev. 2 → 0 Since it is a hackCorrected:- just a small change that neither of three exceed 2*10^4 instead of 10^4 only  » 7 months ago, # | -12 speedforces  » 7 months ago, # | +1 I want an editorial ASAP :(  » 7 months ago, # | ← Rev. 2 → 0 why is my code not correct in test2 about problem b?https://codeforces.com/contest/1311/submission/71794691 •  » » 7 months ago, # ^ | 0 You are running the outer loop 4 times,your solution will fail,If more than 4 swaps will exist for a test case. https://codeforces.com/contest/1311/submission/71814830 Here I just changed your solution a little bit and it got accepted. •  » » » 7 months ago, # ^ | 0 thanks so much ^_^  » 7 months ago, # | ← Rev. 3 → 0 How does one solve F with a complexity lesser that O(n^2) ? We at least need to consider all the pair of points for the minimum distance between them. •  » » 7 months ago, # ^ | 0 I'm also want to know it :( •  » » 7 months ago, # ^ | +2 The non-integer part is really helpful here — distance between points i and j will be either 0 (if they overlap), or starting distance (if they diverge). You can easily see, that for i < j if vj < vi then distance is 0. So, for each i we can find sum of xj such that vj >= vi (I scaled speeds to fit in a segment tree) in logarithmic time, then we can calculate everything in O(n log n). •  » » 7 months ago, # ^ | +2 Hint: Here's how you would find the sum of the differences between all pairs.Sort the array. Set sum = 0. Note that for every number, it will be subtracted from the sum a (number of numbers greater that it) of times, and added to the sum a (number of numbers lower than it) of times, so you can solve the problem in O(NlogN). •  » » » 7 months ago, # ^ | 0 Can you please elaborate? I don't understand your solution fully. •  » » » » 7 months ago, # ^ | ← Rev. 2 → +1 He didn't describe his actual solution yet, just an $O(N)$ way to calculate (xj-xi) for ALL pairs ivi). •  » » » » » 7 months ago, # ^ | 0 Still slower than most solutions •  » » » » » » 7 months ago, # ^ | 0 2-D Segment tree approach can be very fast in this problem •  » » » » » 7 months ago, # ^ | ← Rev. 2 → +9 I think I get the solution now after 2 hours of thinking. Maybe this example can help someone else. Say $x=[100,50,75,25]$, and the corresponding sorted $v=[1,2,3,4]$. First we sort $x=[25,50,75,100]$. Then look at the ways 75 gets added initially according to @golions comment: $+75, +75, -75$(from 75-50, 75-25, and 100-75)Now let's iterate through$x$in sorted $v$ order: when we get to the third element 75, we see that we should only have a single $+75$term due to the $75>50$. Coincidentally this equals the net sum of the three terms above. The reason is that if$75$has the same rank in both the sorted $x$ and the sorted $v$ versions, then there is a symmetry in how $[25,50,75,100]$ mutates into $[100,50,75,25]$: we can let other elements "jump over" 75 to anywhere on the other side, and the symmetry is that the number of jumps going right over 75 equals the number of jumps going left: 100 jumped left, but then 25 jumped right. So the rank of 75 is equal in both cases, and we don't need to correct the $+75,+75,-75$ in our final answer.Another case is $25$, which is rank 1 with respect to $x$, but rank 4 with respect to $v$: Initially we had $-25, -25, -25$due to 50-25, 75-25, and 100-25. But because the rank changed from 1 (w.r.t $x$) to 4 (w.r.t $v$), we must have had 3 jumping overs to the left: and every such jumping over means we shouldn't have included a $-25$, so we correct with $+25$ 3 times, and end up with $0\cdot 25$ in the final answer. •  » » » » 7 months ago, # ^ | +1 Say you have the numbers 1,2,3,4.The sum of differences is 2-1 + 3-1 + 4-1 + 3-2 + 4-2 + 4-3. Note that it's also equal to 1*(-3+0) + 2*(-2+1) + 3*(-1+2) + 4*(0+3). First number in parenthesis (that you subtract by) is the number of numbers that is greater than that number, and the second number in parenthesis (that you add) is the number of numbers that is less than that number.This is not the solution to the entire problem, just part of it. •  » » 7 months ago, # ^ | 0 I think NlogN can be achieved with PBDS or compression with segment or fenwick tree, just use contribution technique.  » 7 months ago, # | ← Rev. 2 → 0 Is this comment (https://codeforces.com/blog/entry/11310?#comment-162921) the right strategy for F?I reduced the problem as follows: first sort by x[i]. Then for every i, sum (x[i]-x[j]) over j •  » » 7 months ago, # ^ | 0 If for every i, you consider all j •  » » » 7 months ago, # ^ | ← Rev. 2 → 0 Yes via brute force, but if you do the sqrt decomposition, you could sort by x[i], then put all pairs into a $\sqrt{N}\times \sqrt{N}$ grid, and sort each row by v[j]. Then given $i$, you can compute the number of $j$ which have both $x_j  » 7 months ago, # | +2 i think d will be hacked most...  » 7 months ago, # | 0 Perhaps it is psycholigal problem...but again I did not solve B :/At least somebody tell me what is wrong with this code •  » » 7 months ago, # ^ | 0 Was able to locate the problem, this code works better.  » 7 months ago, # | 0 I am in a great trouble..I don't know when will be the end of newbie era from my life..Really I am depressed..So,what can I do??? •  » » 7 months ago, # ^ | 0 uplsolve div3 contest problems upto E. https://codeforces.com/blog/entry/66859 you will notice significant improvement after sometime •  » » » 7 months ago, # ^ | 0 Thank you very much..I will try my best to solve the contests..I am really grateful to you. •  » » 7 months ago, # ^ | 0 nothing, stay in the shit you live in, nobody cares of you •  » » 7 months ago, # ^ | 0 Seek some damn therapy instead of asking random internet strangers.  » 7 months ago, # | +1 I'm getting Unexpected verdict while trying to hack a solution for problem C.  » 7 months ago, # | 0 hey im new in everything, is there a post afterwards with the solutions? if not how to solve problem c? i got runtime error all the time. •  » » 7 months ago, # ^ | 0 Yes there are. it's called editorial •  » » 7 months ago, # ^ | 0 I also got a runtime error once. Mine was because the array size I declared was 10e5 (not sufficient). I changed the array size to 2*10e5 + 5 (according to the constraints), and it got accepted.  » 7 months ago, # | +5 What is the hack of D?  » 7 months ago, # | 0 Noooo vovuhhh nooooo  » 7 months ago, # | +3 in D I used 4*10000 that gives TLE but 2*10000 was ok. is there any other approach for solving D.  » 7 months ago, # | +23 Very strong tests in problem D! Your WA1 73 10000 10000  Answer is2 73 10001 10001  To hack, use this test100 73 10000 10000 6 10000 10000 7 10000 10000 82 10000 10000 87 10000 10000 2 10000 10000 1 10000 10000 72 10000 10000 1 10000 10000 91 10000 10000 71 10000 10000 4 10000 10000 31 10000 10000 6 10000 10000 5 10000 10000 32 10000 10000 63 10000 10000 2 10000 10000 43 10000 10000 60 10000 10000 11 10000 10000 2 10000 10000 39 10000 10000 56 10000 10000 25 10000 10000 18 10000 10000 37 10000 10000 92 10000 10000 3 10000 10000 85 10000 10000 7 10000 10000 88 10000 10000 79 10000 10000 58 10000 10000 45 10000 10000 52 10000 10000 1 10000 10000 42 10000 10000 1 10000 10000 40 10000 10000 3 10000 10000 2 10000 10000 83 10000 10000 93 10000 10000 49 10000 10000 2 10000 10000 51 10000 10000 64 10000 10000 13 10000 10000 75 10000 10000 23 10000 10000 28 10000 10000 9 10000 10000 22 10000 10000 5 10000 10000 24 10000 10000 89 10000 10000 94 10000 10000 21 10000 10000 20 10000 10000 1 10000 10000 86 10000 10000 29 10000 10000 74 10000 10000 61 10000 10000 14 10000 10000 1 10000 10000 12 10000 10000 1 10000 10000 95 10000 10000 27 10000 10000 8 10000 10000 7 10000 10000 73 10000 10000 65 10000 10000 44 10000 10000 3 10000 10000 2 10000 10000 1 10000 10000 96 10000 10000 17 10000 10000 71 10000 10000 3 10000 10000 4 10000 10000 5 10000 10000 82 10000 10000 77 10000 10000 97 10000 10000 59 10000 10000 10 10000 10000 1 10000 10000 87 10000 10000 1 10000 10000 98 10000 10000 15 10000 10000 16 10000 10000 23 10000 10000 99 10000 10000 1 10000 10000 100 10000 10000  •  » » 7 months ago, # ^ | ← Rev. 2 → -8 Very strong tests in problem C! (see announcement) •  » » 7 months ago, # ^ | 0 probem D. I went over B from 1 to 1e4, and of course I was hacked. who hates this feeling..  » 7 months ago, # | +1 hey ? No hacking phase? •  » » 7 months ago, # ^ | 0 According to codeforces... Hacks will be open in ~10 minutes.  » 7 months ago, # | 0 My solution for E : First arrange nodes so as to achieve max depth sum (mis concluded this part for like 20 mins), ie, a linear chain.Now consider the node at the bottom and move it up greedily as much as possible so that the change in answer is less than equal to current answer — required depth sum.(Initial answer is sum of depths of all nodes in the linear chain).If we cannot move a node anymore upward and we do not have the required answer, then it is not possible to form such a tree, otherwise it is.Could anyone confirm this? •  » » 7 months ago, # ^ | +10 I made the opposite: first construct a balanced binary tree (parent of x is x/2), then on each iteration take two deepest leafs v1 and v2, and attach v2 to v1. On the last iteration, maybe, you should attach v2 not to v1, but to some its parent.Each vertex is moved at most once, so it is N^2. Looks like it is possible to do it in NlogN, but we don't have to do it.It passed stress test for n, d <= 50, I think it is correct. •  » » » 7 months ago, # ^ | 0 Actually thanks for the idea of stress testing, i forgot the input is only n and d so it can be confirmed for all values of d in range vmin to vmax that answer is found by the code or not.  » 7 months ago, # | 0 Where is hacking phase? Just hacked someone's code and it crashed...  » 7 months ago, # | 0 Sad to see this submission :(https://codeforces.com/contest/1311/submission/71777964 •  » » 7 months ago, # ^ | -15 What the fuck is that though? Why -1 •  » » » 7 months ago, # ^ | +2 I assume, he hacked himself from another account  » 7 months ago, # | +10 How to solve E guys ? •  » » 7 months ago, # ^ | -8 I don't have proof(maybe someone can hack it), and use a random method(pretty fast).first prep lower_bound&upper_bound of n. it's easy to note$ub[n] = n*(n-1)/2$. while$lb[n]$can be find recursively, each time you divide$n$almost half. i.e.$lb[n] = n-1 + lb[x]+lb[n-1-x]$, where$x=n/2$.then try divide&conquer, for random$x$and valid$n_x$, and so other son should valid. Since in intuition there should be many valid partition. •  » » » 7 months ago, # ^ | 0 Sorry, I am just begin to learn Graph (5 dáys). Can you go in more detail. Thanks <3  » 7 months ago, # | 0 Auto comment: topic has been updated by vovuh (previous revision, new revision, compare).  » 7 months ago, # | 0 why it-my[tst].begin(); isn't giving the expected value that was so weird wasted 1 hour trying to figure it outhere's my submission  » 7 months ago, # | +12 Is anyone facing issue of illegal contest id while hacking?? •  » » 7 months ago, # ^ | 0 Yes •  » » 7 months ago, # ^ | 0 It works from the submission page. It can be opened by clicking on '#' in solution preview •  » » 7 months ago, # ^ | 0 Me , What does it mean ??  » 7 months ago, # | +2 •  » » 7 months ago, # ^ | +1 if you use vector instead of set it is O(n) •  » » 7 months ago, # ^ | 0  for(int i=0;i •  » » » 7 months ago, # ^ | 0 B is easily O(n) using dp[i] sum from 1 to i-1 ( sum of how many each element occurs in range 1 to i-1) Also B can be done using segment tree in nlogn Solution above isnt nlogn, it is something like n*logn*logn •  » » 7 months ago, # ^ | 0 how to prove it ? •  » » » 7 months ago, # ^ | 0 Trace it. •  » » » 7 months ago, # ^ | 0 I dont good at proving complexity, I dont mean anything, sorry •  » » 7 months ago, # ^ | 0 This isnt nlogn, it is nlog^2n •  » » » 7 months ago, # ^ | 0 For every segment of length L, sorting will take LlogL, sum of all L is at max N. How is it nlog2n ? •  » » » » 7 months ago, # ^ | 0 But you sort it in cycle, shouldn't the complexity be n*(LlogL) which can be n*log^2n  » 7 months ago, # | +1 vovuh Some people are hacked but their submission still apear in scoreboard (such as https://codeforces.com/contest/1311/submission/71798202). Is it what the contest want? •  » » 7 months ago, # ^ | ← Rev. 2 → +2 I think that is because of at some moment hacks were disallowed but uphacking was allowed. So, it seems like you hacked this solution during the uphacking phase and it is considered as correct (but uphacked) solution.And I don't know what I have to do with it. •  » » » 7 months ago, # ^ | 0 My bad :(  » 7 months ago, # | +4 Why was case of overflow not considered. :rage: . So what if many people fail.Will u add test cases manually everywhere where people fail. Totally unfair.  » 7 months ago, # | 0 Why is 71783447 accepted, not hacked? •  » » 7 months ago, # ^ | +6 Probably because they changed the accepted condition •  » » » 7 months ago, # ^ | 0 I made a mistake, they changed condition on C. But the mistake seems fair, why did they do it? •  » » 7 months ago, # ^ | 0 Wow, this is new to me too  » 7 months ago, # | 0 Can anyone hack my B and D? I have written bad codes and think they can be hacked  » 7 months ago, # | +3 Codeforces Hack Round #624 (Div. 3) •  » » 7 months ago, # ^ | ← Rev. 2 → 0 haha :D  » 7 months ago, # | 0 Problem D should have such test case instead of getting hacked for almost the whole contest •  » » 7 months ago, # ^ | +1 Most people considered A,B,C <=1e4 including me which lead to hacking :( •  » » » 7 months ago, # ^ | 0 the fix is super easy it is really stupid test case  » 7 months ago, # | ← Rev. 2 → +7 This contest is too unfair. You fixed the test case for C while you didn't do anything for problem D. It was a fair mistake done by contestants in problem C. Why did you do this unfair thing? •  » » 7 months ago, # ^ | +7 Face reality, the whole universe is not a fair thing. It is a competition.  » 7 months ago, # | -7 vovuh Why did you change C? If the change in C was fair then you should change D too. Or undo the changes.  » 7 months ago, # | ← Rev. 2 → 0 Very bad round. One of the most unfairest rounds in Codeforces. Half of the people got hacked in D and you didn't do anything there. But you changed the condition of C.  » 7 months ago, # | +4 Very good round but unfortunately too weak test cases. I fell from 500 to 2500 after hack. It is unfair that you ignored hacks on C but not for D.  » 7 months ago, # | 0 The test data of question C in this competition does not exceed the 32-bit integer range, so do you calculate the rating this time?  » 7 months ago, # | ← Rev. 2 → -29 Why are you ignoring us vovuh? What if high rated guys protested? Would you be so silent like you are now? •  » » 7 months ago, # ^ | +1 please stfu, like you didnt even participate in the contest, what is your problem? •  » » 7 months ago, # ^ | +1 cyan revolution is only a matter of time..  » 7 months ago, # | 0 SPEEDFORCES!!!  » 7 months ago, # | ← Rev. 2 → 0 In fact, both C and D has poor test case and that's not problem. but why you change only C? •  » » 7 months ago, # ^ | ← Rev. 2 → +49 We changed only C because we had a bug in author's solution. I didn't have overflow tests (both mistakes in C and D are mine and I'm very sorry about that) and only one of three solutions considered overflow with #define int long long. So we considered to change the constraints in such a way that this issue will not affect participants because I had a problem in my solution.The problem D issue is that it has very bad tests and I wonder how I don't have at least one test case (of hundreds test cases) with$C > 10^4$. It was really surprising for me and I don't even know how to generate such tests in advice (the only way I understand is to write such a wrong solution and stress it).Anyway, this is just an excuse and I blame myself for these mistakes. Sorry everyone who was affected by my poor brain work. UPD: And for all who think that I'm silent and don't want to accept my mistakes or describe you the situation. I'm so silent because now I just trying to do all I can: write the editorial as soon as possible and I trying to do that right now. •  » » » 7 months ago, # ^ | 0 You can easily modify the model solution to minimize first: number of moves, then minimize C. Now iterate through all valid triples$A, B, C$such that C lies in range$(10^4, 10^4 + 20]$, run modified solution for triplet$\min(A, 10^4), \min(B, 10^4), \min(C, 10^4)$and if it says, that optimal solution has$C > 10^4$we just found a countertest.In the same manner you can defeat a solution, that assumes too tight upper bound on$B$like 71800958 •  » » » » 7 months ago, # ^ | 0 Okay, I see. Thank you for explanation! But I didn't even think that the issue "$C > 10^4$in the answer" will affect and break such amount of solutions. •  » » » » » 7 months ago, # ^ | 0 So just to confirm, submissions that display as Accepted, but are actually hacked, that depend on$A,B,C<=10^4$will be judged as WA/Hacked?For me the difference is between +149 and -5, so I'm a bit on edge :D •  » » » » » » 7 months ago, # ^ | +1 As you saw, the actual bound on$C$is a bit larger than$10^4$, so I think that all solutions that only consider$C \le 10^4$will be rejected.  » 7 months ago, # | 0 what is approach for E and F? •  » » 7 months ago, # ^ | 0 Can u explain D •  » » » 7 months ago, # ^ | ← Rev. 3 → 0 iterate over value of c(1 to 3*1e4) and for every c make a tuple {a,b,c} which holds property (c%b==0 && b%a==0) where a and b which are factors of c. So, now one of this tuple is answer. •  » » » 7 months ago, # ^ | ← Rev. 2 → 0 just fix A and B then check that C which lie very close to c and satisfy the condition that$A$divides$B$and$B$divides$C$ . Now for fixing A and B you can iterate A from 1 to say 10000 and B as a multiple of A from 1 to say 11000 simply like in seive algorithm .NOW after fixing A,B and nearby C you have to calculate that this A,B and C deviates how much from original a,b and c . Iterate in the above described value and calculate the minimum value. Simply Cool Algorithm.
 » 7 months ago, # |   +2 What is the largest possible answer in problem D? The largest I found is: Input: 6500 8000 10000 Output: 3500 5000 10000 10000 
•  » » 7 months ago, # ^ |   -9 Input :73 10000 10000 Output: 2 73 10001 10001
•  » » » 7 months ago, # ^ |   0 I meant the largest possible number of moves
•  » » » » 7 months ago, # ^ |   -14 Check numbers that divide primes close to 10000.
•  » » » » » 7 months ago, # ^ |   +15 There are not that much numbers dividing a prime.
 » 7 months ago, # |   0 How long does it take to update my rating after contest??
•  » » 7 months ago, # ^ |   0 its after hacking phase ends
 » 7 months ago, # |   0 Nice contest !! Problem statements were clear and easy.
 » 7 months ago, # |   +1 Help me with how you approach Problem D
•  » » 7 months ago, # ^ |   0 Just do three loops for three variables, and check for minimum answer Something like this: for(int i=1;i<=10300;i++) for(int j=i;j<=10300;j+=i) for(int k=j;k<=10300;k+=j) if(abs(a-i)+abs(b-j)+abs(c-k)
•  » » » 7 months ago, # ^ |   +1 This will give TLE I think, can you help me with optimized solution.
•  » » » 7 months ago, # ^ |   +5 ok I got it, It is some what like nested loops in Sieve for finding primes. Thanks for the help.
 » 7 months ago, # |   0 So I'm pretty sure this is cheating, right? Submission
•  » » 7 months ago, # ^ |   0 Why say that?
•  » » » 7 months ago, # ^ |   0 Seems like they're purposely making the code obfuscated.You can check in the Official rules that that is prohibited.
•  » » » » 7 months ago, # ^ |   0 Wow, that's not cool at all.I didn't see the code thoroughly.
•  » » » » » 7 months ago, # ^ |   0 Yup, also they're in 2nd place!
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 You are right. The function name 'zao123jia' is the pinyin of Chinese word '造假', which means 'cheat' or 'fake' in English.
•  » » » 7 months ago, # ^ |   0 LMAO. I mean, if you're gonna fake something, at least don't leave the word FAKE in it xDDDD
•  » » » » 7 months ago, # ^ |   0 It's time to call vovuh.
•  » » 7 months ago, # ^ |   0 This is obvious a rules violation, it is stated explicitly that you cannot obfuscate your code.Calling vovuh
 » 7 months ago, # |   +4 Is this a hackforces ?
 » 7 months ago, # |   0 I wanna hack someone's code but it told me "Illegal contest ID", and so I could not hack anyone's code.Could someone help me?
•  » » 7 months ago, # ^ |   0 Try opening the submission page by clicking the "#" button. Then try to hack from there. It worked for me.
•  » » » 7 months ago, # ^ |   0 It worked! Thank U!
 » 7 months ago, # |   0 I'm a rookie. I took part in the game last night, but why didn't my rating change?
 » 7 months ago, # |   0 Why hasn't the rating changed even after the end of hacking phase ?
•  » » 7 months ago, # ^ |   0 Same
 » 7 months ago, # |   0 Hi! I don't see any rating changes for me. Can I understand why? I seem to be fitting all the criteria mentioned above
•  » » 7 months ago, # ^ |   0 I'm just the same as you.
 » 7 months ago, # |   0 I'm a new user. I want to participate in contest. How I can? anybody help plz
•  » » 7 months ago, # ^ |   0 Press the contest bottom and find the conteset which you want to take part in. Then press the red bottom Register to finish your registration.
•  » » » 7 months ago, # ^ |   0 Thanks.
 » 7 months ago, # |   0 This was my first ever try to competitive coding.Had a nice experience.It was an eyeopener for me.But,Im really motivated to kickstart this journey!! Wish me luck guys!!!
•  » » 7 months ago, # ^ |   0 good luck
•  » » » 7 months ago, # ^ |   0 Thank you so much!
 » 7 months ago, # |   0 Where is the educational round?
 » 7 months ago, # |   0 I mistakenly thought that in problem F the sum of minimum distances over all pairs of points means that I should determine a moment when each point move to a certain coordinate so that the sum of distances is minimum during all times...
 » 7 months ago, # |   0 Good luck everyone!
 » 7 months ago, # |   0 thanks for this round