By GreenGrape, 2 years ago, translation, ,

Hello.

On Aug/19/2018 16:35 (Moscow time), Codeforces Round #505 takes place. This is a paired round to #504.

Some problems are taken from VK Cup 2018 Finals (ashmelev, Errichto, lewin) and some are proposed by me. I'd like to thank my fellows — Dima (_kun_) who is actually coordinating this round, Kolya (KAN) who brought me here, and also Grisha (gritukan) and Ildar (300iq) just for being nice.

I'd also like to express my gratitude to MikeMirzayanov for multiple bug fixes and awesome Codeforces!

There will be seven problems will the following scoring:
500 — 1000 — 1500 — 1750 — 2250 — 2750 — 3500

UPD. The system testing is over. Editorial (with problem E now)

Congratz to the winners!

1. Swistakk (after all these years, yay)
2. CongLingDanPaiShang3k5
3. Kostroma
4. Benq
5. AwD
6. xumingkuan
7. mcfx
8. fjzzq2002
9. Egor
10. kriii

As in the previous round, thanks to VK social network, GP30 scores will be distributed among the best participants.

Participants are sorted by sum of points for both rounds (if the participant did not participate in one of the rounds, the points scored for it are assumed to be equal to zero), with the maximum time for both rounds from the beginning of the round to the last submission that passed the pretests as tie-break.

Let me remind you that top 10 participants with respect to GP30 score will receive a plush Persik.

Hope you enjoy. Good luck and have fun!

• +91

 » 2 years ago, # |   +429
•  » » 2 years ago, # ^ | ← Rev. 3 →   -14 yes
 » 2 years ago, # | ← Rev. 3 →   0 Div 1+ Div 2 combined?
 » 2 years ago, # |   +19 palindromic round :D
 » 2 years ago, # |   -30 Ok so greengrape, another shitty maths contest.
•  » » 2 years ago, # ^ |   -12 Lol what? His last round was great (especially D) and had only one math-related problem. He writes hard rounds but it doesn't mean they're bad contests.
 » 2 years ago, # |   -34 hi,i am back ..
 » 2 years ago, # |   +21 How many problems, duration, scoring?
 » 2 years ago, # | ← Rev. 2 →   +51 some strong pretests please GreenGrape :D
•  » » 2 years ago, # ^ |   +63 lol
 » 2 years ago, # |   -7 Happy Hacking&&High Rating
 » 2 years ago, # | ← Rev. 2 →   +397 I feel like it will eventually become like this.. *Fine, I found that CF#505 really seems to be the most sad for me as the pic....
•  » » 2 years ago, # ^ |   -6 :ROFL
 » 2 years ago, # |   +14 How many problems and what will the scoring be like?
 » 2 years ago, # |   +50 I think I know who is the author of problem B from the official final round...
•  » » 2 years ago, # ^ |   -6 You missed just a bit. Mine was A :)
 » 2 years ago, # | ← Rev. 2 →   0 Please contest don't have problems that solve with a lot of IF and ELSE! (Iranian people say this problems "Kharkari's problems")
 » 2 years ago, # |   +1 I think the last few games are very difficult.
 » 2 years ago, # |   -8 I think the problems will be very interesting.
 » 2 years ago, # |   +4 What does these "Points GP30" do?
•  » » 2 years ago, # ^ |   +68 for you nothing
•  » » » 2 years ago, # ^ |   +15 but for others?
•  » » » » 2 years ago, # ^ |   +4 Points for top30
•  » » » » » 2 years ago, # ^ |   -35 Thank you for your insightful, useful and informative comment.
 » 2 years ago, # |   +12 three contest in a row......interesting
•  » » 2 years ago, # ^ |   +7 What do you mean? At least 554 contests in a row!
•  » » » 2 years ago, # ^ |   0 God
 » 2 years ago, # |   -7 Can codeforces hold more contest in a row??? I need more!!! I don't need sleep!!!
•  » » 2 years ago, # ^ |   -8 But codeforces need some calculation !
•  » » 2 years ago, # ^ |   -8 after this there will be most probably a div.3 round
 » 2 years ago, # | ← Rev. 3 →   -10 Hope the tutorials will be provided soon for this and the former round #504. :)
 » 2 years ago, # | ← Rev. 2 →   -21 can someone please provide a test case where this solution will fail http://codeforces.com/contest/1023/submission/41825727
•  » » 2 years ago, # ^ | ← Rev. 3 →   -13 Your segment tree works wrong. In your code: int q2=query(node*2+1,mid+1,end,l,r); Correct: int q2=query(node*2+2,mid+1,end,l,r);
•  » » » 2 years ago, # ^ |   -8 i have corrected it but it is still failing http://codeforces.com/contest/1023/submission/41826504
•  » » » » 2 years ago, # ^ |   +5 1 2 1 You print YES but the answer is NO.
 » 2 years ago, # |   -23 "Some problems are taken from VK Cup 2018 Finals" is that mean that some problems are already known to some contestants??
•  » » 2 years ago, # ^ | ← Rev. 2 →   -11 No.At least, in the VK Cup series, no contestants today know about those problems (as those who do know has participated before in the official round).For other series (like parallel Olympiad or something), disciplines are kept through words. Not a really effective way in theory, but it's worked times before.For example in the announcements of Codeforces Round #500 (based on EJOI — European Junior Olympiad in Informatics):We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of EJOI (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.
 » 2 years ago, # |   -16 Will it be harder than 504 or not?
 » 2 years ago, # |   +3 Are the editorials going to appear?.. (for this and the previous rounds)
 » 2 years ago, # | ← Rev. 3 →   +127 Mike Mirzayanov slaps codeforces roof this boy can hold so many contests without crashing
•  » » 2 years ago, # ^ |   +117 @Mahmoud..Adel
 » 2 years ago, # |   +3 I wish to turn blue!
 » 2 years ago, # |   -10 Hope I will become expert after this round
 » 2 years ago, # |   +100 U want strong pretests? Hehe. Hehehehehe. AHAHAHHAHAHAHAHHAHAHAH!
•  » » 2 years ago, # ^ |   +20
•  » » » 2 years ago, # ^ |   +5 HAHA, you have a good sense of humor. I can not solve B too. Maybe I should say goodbye to programming ...
 » 2 years ago, # |   +207
 » 2 years ago, # |   -38 GreenGrape is available for live contest discussion in 5 mins at http://discord.gg/algorithms/
 » 2 years ago, # |   0
 » 2 years ago, # |   0 Pretty nervous having sense of getting WA on systest D. :o
 » 2 years ago, # |   +15 How to solve D? I couldn't get my DP to be faster than n^3
•  » » 2 years ago, # ^ |   0 I could not get it faster than n**5. Can you share your insight for n**3, because i think that should pass the time limit.
•  » » » 2 years ago, # ^ |   +6 My dp was like dp[l][r][t] — is it possible to construct binary tree from l to r and root of this tree is left child of r + 1 if t = 0 and right child of l — 1 if t = 1, but it gives tle.
•  » » » » 2 years ago, # ^ |   0 same
•  » » » 2 years ago, # ^ |   0 Dp[Left/Right][L][R] is true if you can express the range [L,R] of the array as a left or right child of the binary tree. Then you brute force the root of this subtree (it's somewhere in this [L, R] range and if it's gcd with the root (the root will either be R+1, or L-1 depending on what kind of child it is) is > 1, then you try to solve the ranges [L, i-1] and [i+1, R].I thought it might be the solution but I found a case that makes me run in a little more than a second.
•  » » » » 2 years ago, # ^ |   +3 Ahh, I missed a key observation. If i am finding for a sequence i to j, then the only possibility of root is i-1 or j + 1. This would have made my solution run in O(n^3).
•  » » 2 years ago, # ^ |   +10 I think n^3 with some early break optimization might be fast enough.
•  » » » 2 years ago, # ^ |   0 That's what I did but I generated some random case that made me run in a little more than a second (might be because I'm in Java though).
•  » » » » 2 years ago, # ^ |   0 My solution (c++) runs in 46 ms with some break conditions: 41869813
•  » » » » » 2 years ago, # ^ |   0 Yeah turns out I missed some break conditions (like not running the recursion for the right subtree if the left one fails) :(
•  » » » 2 years ago, # ^ |   +3 Early break made it AC in Java for me, after contest :)
•  » » 2 years ago, # ^ |   0 maybe need some optimization, my O(n ^ 3) solution got TLE
•  » » 2 years ago, # ^ |   +18 n^3 / 64 fits in the time limit. Can you imagine a solution with bitsets?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 My N^3 passed the pretests: 41846474. I think I tested it with the worst possible input (no interval is possible), and it used 0.085 seconds of time.My solution was the same as explained by Len.EDIT: AC. Another factor that maybe impacts this is that I precalculated the GCD's.
•  » » 2 years ago, # ^ |   +11 Using STL bitset, the O(n 3) DP can be optimized to .http://codeforces.com/contest/1025/submission/41844612
 » 2 years ago, # |   0 Is problem D solvable with backtracking ?
 » 2 years ago, # |   +31 i began to feel like stupid. How did so many ppl solved D ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Brute... With some optimizations. Consider the array to be inorder traversal of BST. Construct tree using recursion. If there is atleast one valid tree, then "Yes". Also... Use Top Down DP.
•  » » » 2 years ago, # ^ |   0 you are saying an optimized version of back tracking. how does it pass ?
•  » » » » 2 years ago, # ^ |   0 The worst case complexity can be reduced to 2*n^2 with DP. dp[l][r][rootPos] where pos is 1<=l,r<=n and rootPos can be left or right since parent of any subarray must be the left one or the right one in inorder traversal.
•  » » » » » 2 years ago, # ^ |   0 can you explain a bit more abt rootpos
•  » » » » » » 2 years ago, # ^ |   0 Given inorder traversal (a1 a2 a3 a4 a5 a6), if we taske a3 to be the root, then the inorder of left subtree is (a1 a2 a3) whose parent is to the right of it (a3) similarily (a4 a5 a6) constitute right subtree whose parent is to the left. For any subarray (l,r), it's parent can be the left one or the right one.
•  » » » » » » » 2 years ago, # ^ |   0 cool. and optimization means for a given range l, r you will check for the nodes for which the gcd with the l-1th node is > 1 and stop as soon as you find one and similarly for r+1. if yes, wont this get tle ?
•  » » » » » » » » 2 years ago, # ^ |   0 I might have to agree with you... Got a TLE :/
 » 2 years ago, # |   +5 what was pretest 6 for problem B?
 » 2 years ago, # |   +4 How to solve problem B?
 » 2 years ago, # |   +2 How to solve B and C?
•  » » 2 years ago, # ^ |   +6 Just find all prime factors of a[1] and b[1], and check if some of them can divide everything.
•  » » » 2 years ago, # ^ |   +12 The other way is to combine pairs of numbers into a single number c[i] = a[i] * b[i] and use gcd() on it.
•  » » » » 2 years ago, # ^ |   +5 Afterwards though, you will have to take care of a test like: 1 999999893 999999937 You can't output their product, and so have to find one of these primes somehow.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 My bad, this will time out.
•  » » » » » » 2 years ago, # ^ |   +8 All right, but if ans = 999999893 * 999999937 in the first place, the loop will time out (which it did).
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +2 After calculating the gcd, you need to find the smallest prime factor of gcd. You don't need to iterate over prime factors of ans for finding the prime.Just iterate over prime factors of the numbers in one of the pair.
•  » » » » » 2 years ago, # ^ |   +13 (I had similar solution, and I tied it up like so:)Let's say you have answer g from process egor.okhterov described.Then you can run over the array again, and replace g with . We can show by induction that at each iteration g > 1.
•  » » » » » 2 years ago, # ^ |   +1 You can do greedy for it. Iterate over pairs and if gcd(ans,a[i])>1, you can assign that value to ans, otherwise assign gcd(ans,b[i]).
•  » » » 2 years ago, # ^ |   +1 Great :). It was so simple. Nice solution !!
 » 2 years ago, # |   +172 Me while coding div2C:
 » 2 years ago, # |   0 Can somebody explain how to solve problem D? Is it requires DP or something else?
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 I solved it using dp with state of 3 variables l, r, i (l and r are the interval limts I am working on from the sorted array, and i is the chosen root of the sub-tree represented by this interval).Not sure if it will pass system tests though.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 If you have that 3 state dp, doesn't each state need linear recursive calls to be calculated? I believe that leads to n^4.One observation you can make is that for a subtree on [l, r], it's root will only be a child of r+1 or l-1. With this, you can optimize the solution by keeping 3 state dp l, r, k where k is 0 or 1 and dp[l][r][k] tells you whether the subtree on [l, r] can be made as a child of l-1 (if k=0) or r+1 (if k=1). Then, you have n^2 state and linear recursive calls, so you'll have n^3. You can break out of your recursive calls early if you find that dp[l][r][0] and dp[l][r][1] are both possible.
•  » » » » 2 years ago, # ^ |   +3 Yes, it is O(n^4) so it didn't pass :D
•  » » » 2 years ago, # ^ |   0 Won't it be O(n^3)?
•  » » 2 years ago, # ^ |   0 I tried to use flows, but I think it won't pass too. There are cases where my program will fail.
•  » » » 2 years ago, # ^ |   0 How did you solve D using flow?
•  » » » » 2 years ago, # ^ |   +85 Incorrectly.
 » 2 years ago, # |   +66
 » 2 years ago, # |   0 What is the hack for Problem B? Got hacked continuously XD
•  » » 2 years ago, # ^ |   +4 1 1000000007 1000000007
•  » » » 2 years ago, # ^ |   +1 Well f**k...
•  » » » 2 years ago, # ^ |   0 Isn't the correct answer 1000000007 itself?
•  » » » » 2 years ago, # ^ |   0 Yes but many solutions are printing 1000000007*1000000007
•  » » » » » 2 years ago, # ^ |   0 Ohh Okay... That isn't the case for me then. Pretests seem too weak.
•  » » » » » » 2 years ago, # ^ |   0 Try 2 1000000007 1000000007 1000000007 1000000007 Maybe you have n = 1 precalculated.
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Not Yet XD... Code Just too curious on what it might be.
•  » » 2 years ago, # ^ |   0 I hacked succesfully with 2 17 18 3 3 ANS = 3 and 3 1890 1890 5 7 5 5 ANS = 5 
•  » » » 2 years ago, # ^ |   0 How to solve B?
•  » » 2 years ago, # ^ |   0 2 1000000007 1234567891 1234567891 1000000007
•  » » 2 years ago, # ^ |   0 150000 pairs of 1999999973 and 1999999973. It gives TLE because people take gcd of all a*b instead of lcm(a,b)
•  » » » 2 years ago, # ^ |   0 Yeah... I did take GCD of all LCMs.
•  » » » 2 years ago, # ^ |   0 How to solve B?
•  » » » 2 years ago, # ^ |   0 And? a*b couldn't be more than 4*10^18. So the algorithm would work in O(n*log4*10^18) And if n = 150000 n*log4*10^18 = 62*150000 = 9300000. That's pretty fast.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Some people did an o(sqrt(4*10^18)) check in the end. Note that 1999999973 is a prime number.
•  » » » » » 2 years ago, # ^ |   0 I had an array with all prime numbers in range (1;sqrt (1e9)) and then checked a1 and b1 for prime divisors in range (sqrt (1e9); 1e9) , considering the fact if any prime number doesn't divide a1 or b1, it wouldn't be in global gcd as a divider. I did it in O(sqrt (a) + sqrt (b)) and added in an array. And still my solution crashed on test 68.
•  » » 2 years ago, # ^ |   0 you may try this: 2 2000006 3000099 5000015 7000231answer should be either 1000003 or 1000033
 » 2 years ago, # |   +65 Me vs. problem C
 » 2 years ago, # |   0 how to solve C?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +11 My assumption was that it doesn't make sense to do more than one time the operation. Hence, check the length of the pattern from beginning as l1 and length of pattern from end as l2 such that s[0] and s[n-1] are not equal then answer will be max(answer without any operation, l1+l2)
•  » » » 2 years ago, # ^ | ← Rev. 4 →   +3 It can be proved actually. Just try rotating it in your head. Find the longest zebra prefix and the longest zebra suffix. Rotate the string the way these two zebras will be together but make the left rotating part as small as you can (that means, the left part is zebra prefix itself). Beginning of the new max zebra prefix will be the end of the old zebra prefix rotated and the new sufix will be a substring that went AFTER the old max zebra prefix (also rotated). So there is no way first and last symbols would be different in a new string because in that case (substring that went AFTER the old max zebra prefix) substring will be the part of the old prefix. Hope you understood something.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 I don't know how, but this solution didn't pass.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 split it in max len correct zebras. mark from 1 to n. whenever you split it between any two zebras, the neighbours stay the same, except for the first and last zebras — the could become neighbours so the answer is either the longest correct zebra or the sum of 1st and last zebra if it's possible
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +7 I need a video from 3Blue1Brown in order for me to understand that :)Or at least an article from BetterExplained ;)
•  » » » » 2 years ago, # ^ |   +16 You don't know how many times I wished 3Blue1Blown did competitive programming videos xD
•  » » » » » 2 years ago, # ^ |   0 *3Blue1Brown
 » 2 years ago, # | ← Rev. 3 →   +28 Pretests of D are very weak.Even checking that any tree can be made from the input (not essentially BST) with every 2 adjacent nodes having GCD > 1 passes pretests.
 » 2 years ago, # |   0 1114 passed pretest on D. I would bet a lot even at 1/10 odds that no more than 650 will pass full tests — or at least close to that ammount.
 » 2 years ago, # |   +64
 » 2 years ago, # |   +30 Is ans for C just max for all cyclic shifts?
•  » » 2 years ago, # ^ |   +16 Yes.
•  » » 2 years ago, # ^ |   +3 I did that but i dont have any aidea why that works haha
•  » » » 2 years ago, # ^ |   +10 Consider all the zebras in a circle. Now verify that any operation on them simply rotates this circle and reverses it.
•  » » » 2 years ago, # ^ |   +3 Note that after each operation, the order of the characters in the string taken cyclically is reversed. But for the zebras the order being reversed doesn't matter, so it suffices to consider the cyclic string.
 » 2 years ago, # |   0 My idea for problem E:Find m cells such that they aren't an end point, and move the cubes to them.Next, move the cubes from this cells to their end points.Am I missing something???Link to my submission, I had two bugs in it, But am just saying about the idea :\ [submission:http://codeforces.com/contest/1025/submission/41865118]
•  » » 2 years ago, # ^ |   +3 I tried the same but I tried that the free cells were on the border... I think I have a bug in my implementation though
 » 2 years ago, # |   +62 This was the worst contest I've ever participated in.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +31 The problems A-D were pretty nice, the issues in my opinion were really bad pretests, horrible E and silly bounds in D (straight n^3 passes with precalculated gcd's).So in summary, bad round but not as bad as for example Codeforces Round #497 (Div. 1) where 4/5'ths of div1 participants only solved Div1A (and Div1A was really easy).
 » 2 years ago, # |   +3 In C, is "w" or "b" or "bbb" has a length of 1? but I think that one color can not make a zebra. A real zebra should have at least two alternating color,one color can not make a zebra.so the answer should be at least 2. Can someone explain this?
•  » » 2 years ago, # ^ |   0 That's a heavy assumption to make (that zebra cannot have length 1), and should have been something you asked during the contest. It doesn't say anywhere that minimum length should be 2, so you should assume that the minimum length is 1.
•  » » » 2 years ago, # ^ |   0 the question has mentioned that "pieces of alternating colors to create a zebra",so we should think that the answer should have "alternating colors" but not just one color
•  » » » » 2 years ago, # ^ |   0 I suppose that makes sense, but regardless, precision of language is not one of the strengths of CF problems, so it's best to just ask a question during the contest.
•  » » » » » 2 years ago, # ^ |   0 should I ask the author directly or ask here? I haven't do that before. Anyway,thanks for your advice:)
•  » » » » » » 2 years ago, # ^ |   +5 There is a way to do it during the contest. I believe under the "Problems" tab you should see an option that says "Ask a question"
 » 2 years ago, # |   0 anyone used articulation bridge to solve D like me?
•  » » 2 years ago, # ^ |   0 Can you explain?
 » 2 years ago, # |   +10 How to solve F?Also, to anyone who solved D by dp[l][r] means whether it is possible to build a BST using number from position l to position r
•  » » 2 years ago, # ^ | ← Rev. 2 →   +12 F is similar to the JOI problem: solution
•  » » » 2 years ago, # ^ |   0 can someone briefly explain it, most of us don't know know japanese?
•  » » 2 years ago, # ^ |   +36 Think of every pair of non-intersecting triangles (they have points a[0], a[1], a[2] and b[0], b[1], b[2]).Now note that there are only two lines passing through points a[x] and b[y] for each 0 <= x, y < 3, such that all the points of one triangle will lie to the left of the line (one point will line on the line), and all the points of the other triangle lie to the right of the line (one point will lie on the line).How can we solve the problem? We can draw a line from point p[i] to point p[j] for each pair of points. Points p[i] and p[j] become vertices of different triangles. Now we should find the rest of the points of our triangles. For the first triangle, we choose any two points to left of the line, for the second triangle, we choose any two points to the right of the line.The statement above helps us to understand that, using this algorithm, we add each valid pair of triangles exactly two times.Now we should find a way to find the number of points to the left of each line. First, sort all the lines by their angle. Suppose we now consider the line l[i] = A[i]*x + B[i]*y + C[i]. Denote pp(i, j) = A[i]*p[j].x + B[i]*p[j].y + C. For each line l[i], we should keep the points sorted by its pp(i, j) (p[a] must be earlier than p[b] if pp(i, a) < pp(i, b). If we can maintain this, we can say number of points which are to the left of l[i]: it's all the points p[j] which have pp(i, j) < 0. Don't forget that the points are sorted by pp(i, j), so, to answer this, we can find the position of first point pp(i, j) >= 0 using binary search and so we find the answer.Now we should learn to maintain the array of points in the sorted order when we move to another line. Notice that, when line changes, only some two points swap (those two that lied on this line). It's possible beacuse the lines are sorted by angle.So, we get O(N^2 * logN) solution.
•  » » » 2 years ago, # ^ |   0 Thanks for the clear explanation.
 » 2 years ago, # |   +19 I have to say, for a 1000-point-level, B today was quite insane.Hmm, or B, C and even D are all insane, in terms of both ideas and corner cases?
•  » » 2 years ago, # ^ |   0 How to solve B?
•  » » » 2 years ago, # ^ |   +1 If existed, the WCD of a list can always be a prime.Therefore, for the first pair, I'll find all prime factors of the two numbers in that pair (i.e. any prime factor of at least one of two numbers). This process has a maximum time complexity of .From there, we will check that if any of those prime factors can divide at least one number in each of all remaining pairs. This process has a time complexity of O(n * log(2e9)) (The number of prime divisors relates with that number itself by a logarithmic function).
•  » » » » 2 years ago, # ^ |   +3 Thanks.
•  » » 2 years ago, # ^ |   0 Did C have any corner cases? (except maybe that the answer is at most n)
•  » » » 2 years ago, # ^ |   0 As I found, there are (at least) 3: bwbw (most common) www w Two latter ones seemed mostly participants' implementation failure though.
 » 2 years ago, # |   0 In C, is "w" or "b" or "bbb" has a length of 1? but I think that one color can not make a zebra. A real zebra should have at least two alternating color,one color can not make a zebra.so the answer should be at least 2. Can someone explain this?GreenGrape
 » 2 years ago, # | ← Rev. 4 →   +114 These are the worst pretests ever. The pretests don't test logic, or time limit, or anything. What was the point of them even being there? Might as well make it TopCoder style with blind AC after submission.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +48 These authors, they played with us man i am telling you.Btw, Nice work on D. Define the constraints such that the unoptimised obvious solution won't pass. Make weak pretests such that unproven incorrect solution passes. I mean, this is some fun game. I like it, you sleazy mofos
 » 2 years ago, # |   +29 typical contest from GreenGrape
•  » » 2 years ago, # ^ |   0 I think GreenGrape has become a PURPLE one.
 » 2 years ago, # |   +23 that moment when u realize the pretests on D are the samples and ur solution is wrong
 » 2 years ago, # |   +10 Hack for D : 5 2 3 5 7 210 Answer : NO
 » 2 years ago, # |   0 Is there any way to cause TLE when hacking? I saw several solutions for B that could have been hacked by using highly composite numbers. I generated a case using the following code: int n = 150000; cout << n << endl; REP(i, n) cout << "72072000 58378320" << endl; Which I believe would have caught some solutions in my room for TLE, but the file was too large. The case had to have n ~ 13000 to fit the input limit, which wouldn't cause TLE. Is there any way around this?
•  » » 2 years ago, # ^ |   +3 You can send script that generates test.
•  » » 2 years ago, # ^ |   +18 You can submit the generator itself instead of input.
 » 2 years ago, # |   +33 Whose idea was to put a problem like E into the contest? Worst problem I've seen in a while. I wish I'd just have spent my time hacking. I think my idea works but debugging this would be just crazy. 41865146. Move every cube to a unique y-coordinate (n*n moves) Move every cube to the correct column (n*n moves) At least one column is empty or this is trivial (n*n) moves (and step 4 doesn't happen) Using the empty one, solve its left side, then solve its right side (2*n*(n+1) moves)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Maybe solving F would be a better choice.
•  » » » 2 years ago, # ^ |   -10 I hate geometry so no :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 That is close to what I did: Move every cube to a unique row (n * n moves) Move every cube to a unique column s.t. they are sorted by their final columns (n * n moves) Move every cube to the correct row (n * n moves) Move every cube to the correct column (n * n moves) I actually think that the solution is really nice, although many people used randomized solutions, which makes me even more sad that I couldn't code it up in time. Anyway, here is my code that passes, and I would like to believe that it is pretty readable:link
 » 2 years ago, # |   +171 F*** your pretests again.
 » 2 years ago, # |   -9 Well, back to pupil again...But...What can div2B pretest 6 look like?
 » 2 years ago, # |   +33 What was the mapping of problems from VK Cup to problem from #504 and #505?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +23 My guessing:A — 505 problem CB — 505 problem DC — 504 problem ED — 504 problem FE — 505 problem FF — 505 problem GG — 504 problem G
•  » » » 2 years ago, # ^ |   0 You're almost right, except B was 505 E.
•  » » » » 2 years ago, # ^ |   0 Lol, so today's E was worth 1250 on VK cup, and today's F 2250 xD?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +17 504 EFG = VK Cup CDG505 CEFG = VK Cup ABEF
 » 2 years ago, # |   +85 Constaints in D were pretty weird. n<=700 and first promising solution that comes to mind is lightweight n^3. I coded it, but got TL, which is reasonable if TL=1s, n=700 (inb4, precomputed gcd of course). So I switched to bitsets and did this successfully with time of execution 109ms. But it seems many people passed it with simple n^3. What is the reason for such weird choice of constraints and TL?
•  » » 2 years ago, # ^ |   +8 Probably wanted to exclude O(n 4).
•  » » 2 years ago, # ^ |   0 I got AC with precalculated GCD, so you're correct :Dd 41846474
•  » » 2 years ago, # ^ |   0 My n^3 passed (recursive dp). I used all boolean arrays (except for one long long vector to take the inputs).So, is 1 second enough for a complexity of 5e8 or even 1e9 in CF? (D was a little more than 3e8 and my submission took only 62 ms)
 » 2 years ago, # |   +12 Was this the WEAKEST pretests in Codeforces history!!!Now looking at my solution for problem C, I can't believe it how it passed them !!!
•  » » 2 years ago, # ^ |   -8 No, there has been weaker.
 » 2 years ago, # | ← Rev. 2 →   +8 I have a simple and short solution about pB let ans = gcd(a[1]*b[1],a[2]*b[2],.....,a[n]*b[n]) if ans != 1 then you can greedy to find the answer by the code below  for(int i = 0; i < n ; i++){ if(__gcd(ans,a[i]) == 1){ ans = __gcd(ans,b[i]); }else { ans = __gcd(ans,a[i]); } } 
•  » » 2 years ago, # ^ |   +3 Are you sure this is optimal? For example, what if a[i], b[i] were both valid options and it was optimal to choose b[i] but you instead choose a[i]. Or is there never a case where at the start ans > 1 but becomes 1 during the process.Because this was my idea when reading the problem (woke up too late to participate) but I had a slight worry that you can hit ans = 1 at some point in the process so there would be more to the problem than just checking choosing the valid one (because both might be valid).
•  » » » 2 years ago, # ^ |   0 SorryQQ I don’t understandthis the sentence “what if a[i], b[i] were both valid options and it was optimal to choose b[i] but you instead choose a[i].” While you are choosing the answer , it’s impossible that both gcd(ans,a[1]) gcd(ans,b[1] equal 1 because ans is a[i]*b[i]’s divisor.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Sentence doesn't make sense because it was under the assumption you could reach 1.Also I am still unsure how that proves you never hit 1. (I saw another comment mentioning proof by induction, but no one elaborated)
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 The initial gcd calculated gives us a value which divides either a[i] or b[i] for every i, and so does all of the factors of that gcd, therefore, we know that in the above code, atleast one of gcd(ans,a[i]) or gcd(ans,b[i]) will be greater than one.Once you reach a prime number in the above loop, you can be sure that it divides atleast one of a[i] or b[i], which means it the final answer will stay that prime number only.Hope that cleared up your doubt!
 » 2 years ago, # |   +20 Holy sh**, the weakest pretests I've ever seen. Goodbye rating, I'll miss you
 » 2 years ago, # |   +5 Weak pretests for B.
 » 2 years ago, # |   0 big fat L
 » 2 years ago, # |   +1 These are the contests when you feel grateful for Hacks.
 » 2 years ago, # |   +91 System test failed !!!
 » 2 years ago, # |   +73 GreenGrape and weak pretests ,still better love story than twilight .
 » 2 years ago, # |   +9 Waiting for a standard 5 problem contest
 » 2 years ago, # |   0 Hackforces as usual :(
 » 2 years ago, # |   +27 if pretests were sample tests they would be stronger than this pretests
 » 2 years ago, # |   0 F*** your pretests!
 » 2 years ago, # | ← Rev. 2 →   +3 GreenGrape, what's pretest 14 on problem E? My solution seems to pass my validator for all random tests.
 » 2 years ago, # |   +4 Downvoting the blog right away for the pathetic pretests.
 » 2 years ago, # |   +11 Good problems(except C) but terrible pretests !
•  » » 2 years ago, # ^ |   +29 Doesn't problem C has a nice solution? (Just double the string and find the longest alternating substring that has length shorter than n?)
•  » » » 2 years ago, # ^ |   +14 Why do we double the string? I feel like it should be something obvious but cannot parse the meaning from looking at code submissions.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 It's not a bad problem. The solution is really nice!! But for me, I solved it by just guessing that doing more than 1 operation might not help increasing the answer. I was unable to prove it during the contest time, but still got AC. I think few participants like me also did the same thing.
•  » » 2 years ago, # ^ |   +3 I felt like C was a "Lucky" problem. For some it was a lucky and for rest not so. When I was seeing a lot of people were getting AC, I just did the double string approach but I have no proof.D was a good problem. But N <= 700 was not a good constraint. I think I could have solved it quicker if it N <= 500. I had to check carefully whether it will pass. And then having no other way, I just did the n^3 dp and it got accepted. Problem B was nice. I liked the solution.
 » 2 years ago, # |   +3 no feedback contest
 » 2 years ago, # |   +60
•  » » 2 years ago, # ^ |   +3 Oh great GreenGrape. I need to hide my submissions away.
•  » » 2 years ago, # ^ |   0 My eyes are literally burning. g++ -E command to make this sensible as i remember
•  » » 2 years ago, # ^ |   +18 How did this actually got hacked
•  » » » 2 years ago, # ^ |   +55 Since I was suffered from he's code, I really wanted to hack this. So I arrange his code and find a vulnerability XD
•  » » » » 2 years ago, # ^ |   +3 O_O that was really good job, congrats
•  » » 2 years ago, # ^ |   +77 That's against codeforces rules, he should be disqualified.
•  » » 2 years ago, # ^ |   0 Hacked.
»
2 years ago, # |
-34

# But Is It Rated?

•  » » 2 years ago, # ^ |   +11 why not? But somehow CF predictor is not working for me
•  » » » 2 years ago, # ^ |   +55 If cf predictor doesn't work for 15 minutes we are legally allowed to be unrated
 » 2 years ago, # |   +190 YYYYYYAAAAASSSSSSSS!!!!!!!!!!!I can stop whining about my growing record of second places :>>>>>>>>> Waited for this so long, so happy :D
 » 2 years ago, # |   +167 Congrats to Swistakk for finally winning something!
 » 2 years ago, # | ← Rev. 3 →   -16 Downvoted. Thanks for the weak pretests which made my solutions for both B and C failed system test.May I call this FSTforces?
 » 2 years ago, # |   +20 system testing is a massacre for us noobs
 » 2 years ago, # |   +89 Contrary to the opinion which seems to prevail in the comments so far, I quite like it when the pretests and the system tests are not of the same effect. It gives more value to local testing, which is definitely a useful skill on contests outside Codeforces.So, just wanted to chime in with it, otherwise the discussion looked pretty one-sided.
•  » » 2 years ago, # ^ | ← Rev. 3 →   -38 I think that it should've been announced before the contest, not after it during the full tests. I believe that programming contest site is not a place for such surprises.
•  » » 2 years ago, # ^ |   +29 I can understand disliking the system or being disappointed that your solution fails.But one thing that really bothers me is the attitude that it is somehow the authors' fault if your solution fails system tests. It's still your faulty code. Please accept that.
•  » » » 2 years ago, # ^ |   +16 Well said.Related, from personal experience: once I transferred from the mindset like "my programs are awesome and so CAN'T fail" to the more realistic "my programs are still awesome but WILL have bugs", soon enough, my programs had less bugs. Still nowhere near zero though.
•  » » » 2 years ago, # ^ |   +26 If the purpose of pretests is to act like the real tests, but to reduce the load on the servers during the contest, then technically every time a submission fails to system tests it is the author's fault.Of course if your solution fails, it's your fault for writing buggy / incorrect code, but why does that discredit saying that the pretests being weak are a problem?
•  » » » » 2 years ago, # ^ |   0 If the purpose of pretests is to act like the real tests, but to reduce the load on the servers during the contest, ... Alright, it's the first time I see it formulated like this. So, unlikely that this is what the platform authors envisioned.Or maybe I just didn't follow.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +16 The purpose of pretests is to make the most unreasonable solutions fail.Quoting this blog from MikeMirzayanov And now comes the time when you solved the problem and submitted it. It will be checked only on preliminary testset (also we call such tests "pretests"). It is known that pretests do not check solution completely. Usually there are 2-10 pretests, and the fact that the solution passed pretests says only that it is quite reasonable. Typically pretests not contain the maximal tests, corner cases, etc.
•  » » » » » » 2 years ago, # ^ |   0 Most importantly: Typically pretests not contain the maximal tests, corner cases, etc.
•  » » » » » » 2 years ago, # ^ |   0 I think nowadays on Codeforces pretests are supposed to contain at least tests with maximum size of input, maximal value of n, etc. However the coverage of corner cases does vary a lot.
•  » » » » » » 2 years ago, # ^ |   0 8 years agoI think the idea of pretests was distorted (sorry for my english), so these tests have changed into a reduced variant of systests. The fact that your solution can be tested precisely during the contest seems casual but common and, in my view, more practically-oriented. Anyway, contesters got used to it, so all these protests and downvotes things can be understood. 3 of my 4 solutions failed on systests, so I as a submit-see-green-proceed person was upset and could understand them.
•  » » 2 years ago, # ^ |   +40 Then what's the point of pretests? It's pretty unfair if some special cases are covered in pretests and some are not. Should the pretests just cover the samples?Also, if pretests are weak, the hacking system is incredibly broken: How much you score becomes very dependent on the room you are in (how many people had easy bugs to find), The score you get highly depends on whether you get hacked or not, since getting hacked saves you from failing to systests, and, say two people in the same room find some corner case, now they are competing in speed at noticing that someone submitted to a problem, and hacking that person.Of course you write a brute-tester when programming in the real world, but even if the pretests are very weak, it is not necessarily correct to write one. You just have to make the decision to risk failing to system tests, or wasting time writing a brutetester. I find it much better that you don't have to guess whether your solution has a bug or not before writing a brutetester. With strong pretests, you still have to find what the problem in your code is, which I think is the main part of debugging anyways (not finding out that a bug exists in your code).
•  » » » 2 years ago, # ^ |   -12 Conversely, if passing the pretests should always mean passing the systests, then what is the point of systests?
•  » » » » 2 years ago, # ^ |   +12 Reducing the load on the servers during the contest, and preventing reverse-engineering the test data.Additionally, all successful hacks are added to the system tests, but there is no way to add hacks into pretests.
•  » » » » » 2 years ago, # ^ |   +2 The first point is moot assuming you want no solution that passes the pretests to fail the systests, excluding hacks.
•  » » » 2 years ago, # ^ |   +13 OK, not arguing your points for now, but asking a question instead.What, in your opinion, would be the best difference between pretests and system tests? Your comment sounds much like you'd want them to act the same. Well, we have plenty of other contest platforms which have exactly that: no pretests.For a platform where pretests and system tests are two distinct entities, it makes perfect sense that they have observably distinct effects.
•  » » » » 2 years ago, # ^ |   +32 Topcoder has very nice hacking system. All pretests are open, so you can see for yourself, how strong they are. Almost every contest a lot of solutions get hacked or fail systests, but noone complains that pretests are weak.On Codeforces, you have no idea how strong pretests are, which often feels frustrating.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +11 On TopCoder, people also complain when pretests are weak :) .And yeah, the pretests system on Codeforces is far from perfect because of its quirks with uncertainty. Hey, if there was no uncertainty, there won't be vastly different expectations for pretests, and there won't be this thread!Still, it is possible to utilize the imperfect system, and it is possible to effectively shut down the pretests-and-hacking part of the contest. Both happen, in different rounds. I just like the former option better, is all: we have plenty other platforms for the latter.
 » 2 years ago, # | ← Rev. 2 →   +18 If I hypothetically (but not really) found a test case that breaks my solution (and possibly other people's solutions) to a problem, even though it passed system testing, am I obligated to release that test case? (Or maybe a better question is do I want to.)
•  » » 2 years ago, # ^ |   0 People have done it before. I remember one time in particular recently the case mentioned broke like 4 out of the top 5 contestants' solutions or something like that. I imagine it only helps, because it lets the authors know that their tests could have been stronger.
•  » » 2 years ago, # ^ |   0 This test won't influence the standings for this round, but we can add it to the tests for upsolving.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +7 My test case for problem D: 7 7 38 690 717 11165 75361 104117 It is specifically designed to break my code, so I don't imagine it would affect rating changes that much anyway besides for me.
•  » » » » 2 years ago, # ^ |   0 Expected output?
•  » » » » » 2 years ago, # ^ |   +3 Yes
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Another Testcase:32 3 6A couple of accepted solutions fail this, one such example: http://codeforces.com/contest/1025/submission/41858091
 » 2 years ago, # | ← Rev. 4 →   +29 Wrote a script to determine the prize winners (sorry for the ugly code): link Benq (score = 110) fjzzq2002 (score = 107) ko_osaga (score = 100) Swistakk (score = 100) Egor (score = 79) CongLingDanPaiShang3k5 (score = 75) ksun48 (score = 60) Kostroma (score = 60) natsugiri (score = 45) AwD (score = 45) I am 11th in this list :(UPD: System testing is over, nothing changed.
 » 2 years ago, # |   +161
 » 2 years ago, # |   +39 why cf predictor is not showing anything ?
•  » » 2 years ago, # ^ |   +28 Looks like CfPredictor failed the System tests..
•  » » » 2 years ago, # ^ |   +8 Good One!!!
 » 2 years ago, # |   0 Could someone tell me the reason why changing '&' with '&&' between two booleans give TLE. Solution with '&'Solution with '&&'
•  » » 2 years ago, # ^ |   +8 The & is a bitwise operation.The && is a logical operation, and has the benefit of short-circuit boolean evaluation: if the first argument is false, the second one is not calculated.Perhaps this meant a lot in your particular case, when both arguments are recursive calls.
•  » » » 2 years ago, # ^ |   +10 Thanks. I think the time limit was too strict in D, that's why it failed sys test. They should give n = 500 for O(n 3) solution
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Or they could have increased TL to 2 sec. O(n^4) wouldn't have passed in 2 sec anyway. I was using ll unnecessarily instead of int which gave me TLE.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Because & is bitwise AND and && is logical AND. Logical AND is short-circuiting, which means if the first operand determines the result, it will not evaluate the other.EDIT: Oops, someone beat me to it :P
 » 2 years ago, # | ← Rev. 2 →   +23 Solved: 4 out of 7 ->Solved: 3 out of 7 -> Solved: 2 out of 7 ->Solved: 1 out of 7 (no reverse)
 » 2 years ago, # |   +99 The announcement has failed system test too.
 » 2 years ago, # |   0 How to solve D ?
 » 2 years ago, # |   +42 It seems that a number of submissions with time complexity O(d(a 1, b 1)·n) passed problem B, where d(a 1, b 1) denotes the number of divisors of at least one of a 1 and b 1.However, there are only tests with large d(a 1) (number of divisors of a 1) and d(b 1), but not large d(a 1, b 1): there may be many duplicate divisors of a 1 and b 1. For example, 1396755360 and 1102701600 are integers having the most divisors (1536 and 1440) below 2·109, but there are only 2208 different divisors of at least one of them.I generated a pair of integers for a 1 and b 1 below 2·109 with the most d(a 1, b 1): 1889727840 and 1715313600. They have totally 2760 different divisors. I think it would be better to add something like the following case to the practice version of the problem: 150000 1889727840 1715313600 1889727840 1715313600 1889727840 1715313600 ... 1889727840 1715313600 1889727840 1715313600 1999999973 1999999943 
•  » » 2 years ago, # ^ |   +26 Out of curiosity, how did you generate these numbers? I couldn't figure out a way to do it that would run in a reasonable time and I also couldn't find the numbers online.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +2 I searched the prime factors p = 2, 3, 5, 7, 11, ..., and multiplied them to a 1 and b 1, that is, multiply a 1 by p 0, p 1, p 2, ... and multiply b 1 by p 0, p 1, p 2, ... each time. Of course we do not want to waste a small prime and use a big prime, so we should avoid multiplying p 0 to both a 1 and b 1.It seems kind of brute force searching with some pruning, but it runs only 72 seconds on my computer. I couldn't analyze its accurate complexity. ( x, y denote a 1, b 1, and xrem, yrem denote 2·109 / a 1, 2·109 / b 1 in the following code) Code#include #include #include #include #include using namespace std; const int MAXN = 1010; int prime[MAXN], primenum = 0; int minprime[MAXN]; void init(int n = MAXN - 1) { memset(minprime, 0, sizeof(minprime)); for(int i = 2; i <= n; i++) { if(!minprime[i]) prime[++primenum] = i; for(int j = 1; i * prime[j] <= n; j++) { minprime[i * prime[j]] = prime[j]; if(i % prime[j] == 0) break; } } } int ans = 0, ansx, ansy; void search(int p, int x, int y, int xnum, int ynum, int bnum, int xrem, int yrem) { if(xnum + ynum - bnum > ans) { ans = xnum + ynum - bnum; ansx = x; ansy = y; printf("%d %d %d\n", ans, ansx, ansy); } if(xrem == 1 && yrem == 1) return; int xcnt = 1; while(xrem) { int nowy = y, nowyrem = yrem, ycnt = 1; while(nowyrem) { if(xcnt + ycnt > 2) search(p + 1, x, nowy, xnum * xcnt, ynum * ycnt, bnum * min(xcnt, ycnt), xrem, nowyrem); nowyrem /= prime[p]; nowy *= prime[p]; ycnt++; } xrem /= prime[p]; x *= prime[p]; xcnt++; } } int main() { init(); int n = 2000000000; search(1, 1, 1, 1, 1, 1, n, n); printf("%d %d %d\n", ans, ansx, ansy); //2760 1889727840 1715313600 return 0; } I think it can even be a nice (and hard) problem in some round (given n, find a 1 and b 1 below n with max d(a 1, b 1)) if someone figures out some optimizations to make it run in several seconds :)
•  » » 2 years ago, # ^ |   +18 Added, thank you.
•  » » 2 years ago, # ^ |   +10 Thanks God this test was not in original system tests! My solution 41848942 got accepted in 1185 ms but now it gets TLE on the test #99.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +9 My code still passed this test in practice in 1465ms.Link
 » 2 years ago, # |   0 We love you so much, GreenGrape... Wish you are already preparing next contest.
•  » » 2 years ago, # ^ |   +22 With no pretests at all. Only 2-3 examples.
 » 2 years ago, # | ← Rev. 2 →   +5 When I click on Editorial, it says "You are not allowed to view the requested page". Please fix it. Edit: Fixed.
 » 2 years ago, # |   0 Is it rated ? Cause i don't see anywhere about rated or unrated announcement.
•  » » 2 years ago, # ^ |   +1 Rated.
 » 2 years ago, # |   0 can someone please help me in debugging my code. I've no idea why it failed on test 45.code link. My dp state is dp[i][j] -> if the root is ith index vertex and we have to assign tree upto jth index (actually I skip a dimension. instead of having l, r I have single j as we know if j is less than current root then (l, r) == (j, i-1) else (l, r) == (i+1, j)).
•  » » 2 years ago, # ^ |   +5 Your solution is correct but you were forgetting to set your ans variable in a couple cases, so the second time you visited those states you returned an invalid memoized result.Fixing that gets you AC: http://codeforces.com/contest/1025/submission/41869888
•  » » » 2 years ago, # ^ |   0 thanks for the reply. But can you tell me one thing that why it matters? because at first I've already reset my dp table to zero and hence if 'ans' is not set then will it not safe to assume that it will be unset?
•  » » » » 2 years ago, # ^ |   0 The lines with return ans = 0; are unnecessary like you said (I only added them for completeness), but return ans = poss[i][root]; might be true so that's when your previous code failed.
•  » » » » » 2 years ago, # ^ |   0 Sorry I actually missed that line. After trying for 1 and half hour I'm thinking that the entire solution is wrong. Thanks a lot again :)
 » 2 years ago, # |   +54 I see that this contest was received kinda badly as this blog post has -27 votes. It seems that only thing people complain about are weak pretests. There were no other issues (ok, maybe I can add dubious constraints for D), problems were fine, statements were clear, no CF hardware issues lowering overall experience etc. I think that these downvotes are way too harsh
•  » » 2 years ago, # ^ |   +20 With all due respect, I doubt if you'd feel so if you lost your rank 1 because of some systest-failed B or C or D.
•  » » 2 years ago, # ^ |   -9 the thing that was too clear, was the fact that authors didn't spend time on making strong pretests, bc that was not a thing that they can not do it. also i have a bad feeling about all rating changes, some wrong solutions that get accepted (on the first contest's D), but i believe that for first contest's A, even though the pretest were weak, every participant could take the tricky test cases from the problem statement itself (it means it was written good) i couldn't take part in second contest (even though i liked to), so i can't say anything about it. at the end, i believe contest weren't very bad, but our expectations were so high (Why, our expectations so high — eminem )
•  » » » 2 years ago, # ^ |   +1 "the fact that authors didn't spend time on making strong pretests"disagree. It's just author want participant get FST XD.pretest is always a trap, that's why we calls it pretest : )
•  » » » » 2 years ago, # ^ |   +3 its ok to catch some solutions in that trap, but half of them??? i don't know
•  » » » » » 2 years ago, # ^ |   0 Spoilerin fact I think the only bad thing with weak pretest is that lucky participant may get more hacks. but for weak pretest it self, I think it's ok.We should judge our sulution by it's logic but not it passed tests or not.especially it's pretest.when you get weak pretest, everyone else get weak pretest too.As the result ,it's you choosed to believe in the pretestMy B also got FST because I checked all factors but not prime factor.max number of factor(in 2e9) is about 2000 numbers(as I culculated at local)And prime factor is about log(x),but I expected this 20min laterI think codeforces is fast and choosed not to resubmit to avoid lose 200 pointsAnd as the result I losed 840 points XDthere is nothing wrong, nobody forced me not to resubmit : /
•  » » » » » » 2 years ago, # ^ |   0 ok, that was just my opinion, but i agree with your opinion, also, you are more experienced than me, i know that participants should mind tricky testcases their selves and don't just depend on pretests...
•  » » 2 years ago, # ^ |   -8 Because pretest is an issue that causes tons of lower level contestants to fail things that they would otherwise have passed. And it is more significant than bad statements. Hardware issues are not the domain of authors.
•  » » 2 years ago, # ^ |   -13 Maybe these downvotes are due to some bots? As happened on Announcement page of Round 502.
 » 2 years ago, # |   -21 Any one else thinks random pretests are stronger??
 » 2 years ago, # |   +13 when you considering : " come on, codeforces super fast and I get PP with 120ms "
 » 2 years ago, # | ← Rev. 2 →   +53 If you guys knew that the pretests were going to be weak because of the author or whatever, why didn't you just take the extra 5-10 minutes to do local testing/try to prove your solution is correct?
 » 2 years ago, # |   0 In such contests, I indeed feel very fortunate that I got my C hacked during contest, and then I got a chance to get it accepted :)
 » 2 years ago, # |   +16 End of the coding weekend! Thank you Mike and CF.
 » 2 years ago, # |   0 In prob D, I approached it with DP with the parameters left, right and rootSo, I guessed the Time complexity will be about O(N^3) but when i made a random test case of 700 it took so longThen I changed the DP table, and I got MLE...http://codeforces.com/contest/1025/submission/41864181Can anyone tell me where I am wrong?? And, what is the right sol?
•  » » 2 years ago, # ^ |   0 700^3 is 343000000 ~ 3e8, no surprise you get MLE.std::vector packs the booleans, but I don't think raw arrays do, so if you want to just decrease memory usage, you can use vectors over raw arrays.
 » 2 years ago, # |   0 Pretests too weak, Hackforces?
 » 2 years ago, # |   0 These submissions are identical, but my solution got tle in system testing :(.http://codeforces.com/contest/1025/submission/41880498http://codeforces.com/contest/1025/submission/41858978
•  » » 2 years ago, # ^ |   0 Different machine stability. If u ac,it is lucky. Else it will be TLE.
•  » » 2 years ago, # ^ |   0 too strictly time limit
 » 2 years ago, # |   0 I have a solution and got Accepted but I find a test case can hack the solution:Solution:41885803Test case: 3 6 6 2 2 3 3 Expected -1 but this solution got 3. Hacked myself :-)
 » 2 years ago, # |   0 Why is my solution to Problem B giving TLE
 » 2 years ago, # |   +7
 » 2 years ago, # |   0 Your text to link here... Why is this B right?
 » 2 years ago, # | ← Rev. 2 →   +45 GreenGrape My solution 41866649 was accepted .But i hacked it . 5 6 9 10 49 70 It should be output "YES". But my solution output "NO".
 » 2 years ago, # |   +64
•  » » 2 years ago, # ^ |   +32 Lol, ACM was my life for 5 years, but thanks to you I realized just now what its logo is meant to show.
•  » » » 2 years ago, # ^ |   +13 I still don't get it, can you explain?
•  » » » » 2 years ago, # ^ |   +13 thinking thinking continiously then suddenly an idea strikes you or the aaahhh moment and AC(ballons as you get after solving a problem).
•  » » » » » 2 years ago, # ^ |   +21 ohhhh, balloons for AC is clever
•  » » » » 2 years ago, # ^ |   +14
 » 2 years ago, # |   0 why this solution can ac http://codeforces.com/contest/1025/submission/41902787 but this will tle http://codeforces.com/contest/1025/submission/41905132 only change "dfs(l,i-1,i)&&dfs(i+1,r,i) " to " dfs(i+1,r,i)&&dfs(l,i-1,i) "
•  » »