Codeforces Round #505
By GreenGrape, 6 years ago, translation, In English

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 (cdkrot) who is actually coordinating this round, Kolya (KAN) who brought me here, and also Grisha (vintage_Vlad_Makeev) 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. DearMargaret
  3. Kostroma
  4. Benq
  5. AwD
  6. xumingkuan
  7. webmaster
  8. TLE
  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!

  • Vote: I like it
  • +91
  • Vote: I do not like it

Comments Comments (298)
| Write comment?
»
6 years ago, # |
  Vote: I like it +429 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

palindromic round :D

→ Reply
»
6 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Ok so greengrape, another shitty maths contest.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

How many problems, duration, scoring?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +51 Vote: I do not like it

some strong pretests please GreenGrape :D

→ Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Happy Hacking&&High Rating

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +397 Vote: I do not like it

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....

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

How many problems and what will the scoring be like?

→ Reply
»
6 years ago, # |
  Vote: I like it +50 Vote: I do not like it

I think I know who is the author of problem B from the official final round...

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Please contest don't have problems that solve with a lot of IF and ELSE! (Iranian people say this problems "Kharkari's problems")

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think the last few games are very difficult.

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I think the problems will be very interesting.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

.

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

three contest in a row......interesting

→ Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Can codeforces hold more contest in a row??? I need more!!! I don't need sleep!!!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    after this there will be most probably a div.3 round

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

can someone please provide a test case where this solution will fail http://mirror.codeforces.com/contest/1023/submission/41825727

→ Reply
»
6 years ago, # |
  Vote: I like it -23 Vote: I do not like it

"Some problems are taken from VK Cup 2018 Finals" is that mean that some problems are already known to some contestants??

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it -11 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Will it be harder than 504 or not?

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Are the editorials going to appear?.. (for this and the previous rounds)

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +127 Vote: I do not like it

Mike Mirzayanov slaps codeforces roof

  • this boy can hold so many contests without crashing
→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I wish to turn blue!

→ Reply
»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Hope I will become expert after this round

→ Reply
»
6 years ago, # |
  Vote: I like it +100 Vote: I do not like it

U want strong pretests? Hehe. Hehehehehe. AHAHAHHAHAHAHAHHAHAHAH!

→ Reply
»
6 years ago, # |
  Vote: I like it +207 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty nervous having sense of getting WA on systest D. :o

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve D? I couldn't get my DP to be faster than n^3

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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).

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I think n^3 with some early break optimization might be fast enough.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My solution (c++) runs in 46 ms with some break conditions: 41869813

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah turns out I missed some break conditions (like not running the recursion for the right subtree if the left one fails) :(

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Early break made it AC in Java for me, after contest :)

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe need some optimization, my O(n ^ 3) solution got TLE

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    n^3 / 64 fits in the time limit. Can you imagine a solution with bitsets?

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Using STL bitset, the O(n3) DP can be optimized to .

    http://mirror.codeforces.com/contest/1025/submission/41844612

    → Reply
»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

i began to feel like stupid. How did so many ppl solved D ?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you are saying an optimized version of back tracking. how does it pass ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you explain a bit more abt rootpos

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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 ?

              → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

what was pretest 6 for problem B?

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve problem B?

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve B and C?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Just find all prime factors of a[1] and b[1], and check if some of them can divide everything.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      The other way is to combine pairs of numbers into a single number c[i] = a[i] * b[i] and use gcd() on it.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          My bad, this will time out.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            All right, but if ans = 999999893 * 999999937 in the first place, the loop will time out (which it did).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 2   Vote: I like it +2 Vote: I do not like it

              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.

              → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          (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.

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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]).

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Great :). It was so simple. Nice solution !!

      → Reply
»
6 years ago, # |
  Vote: I like it +172 Vote: I do not like it

Me while coding div2C:

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain how to solve problem D? Is it requires DP or something else?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to use flows, but I think it won't pass too. There are cases where my program will fail.

    → Reply
»
6 years ago, # |
  Vote: I like it +66 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hack for Problem B? Got hacked continuously XD

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    1 1000000007 1000000007

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hacked succesfully with

    2
17 18
3 3
ANS = 3

    and

    3
1890 1890
5 7
5 5
ANS = 5
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2 1000000007 1234567891 1234567891 1000000007

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    150000 pairs of 1999999973 and 1999999973. It gives TLE because people take gcd of all a*b instead of lcm(a,b)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah... I did take GCD of all LCMs.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to solve B?

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Some people did an o(sqrt(4*10^18)) check in the end. Note that 1999999973 is a prime number.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you may try this: 2 2000006 3000099 5000015 7000231

    answer should be either 1000003 or 1000033

    → Reply
»
6 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Me vs. problem C

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I don't know how, but this solution didn't pass.

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +28 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +64 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Is ans for C just max for all cyclic shifts?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Yes.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I did that but i dont have any aidea why that works haha

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Consider all the zebras in a circle. Now verify that any operation on them simply rotates this circle and reverses it.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/1025/submission/41865118]

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it +62 Vote: I do not like it

This was the worst contest I've ever participated in.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +31 Vote: I do not like it

    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).

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          should I ask the author directly or ask here? I haven't do that before. Anyway,thanks for your advice:)

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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"

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone used articulation bridge to solve D like me?

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    F is similar to the JOI problem: solution

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can someone briefly explain it, most of us don't know know japanese?

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve B?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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).

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did C have any corner cases? (except maybe that the answer is at most n)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As I found, there are (at least) 3:

      • bwbw (most common)
      • www
      • w

      Two latter ones seemed mostly participants' implementation failure though.

      → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +114 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +48 Vote: I do not like it

    These authors, they played with us man i am telling you.

    Btw, Nice work on D.

    1. Define the constraints such that the unoptimised obvious solution won't pass.

    2. Make weak pretests such that unproven incorrect solution passes.

    I mean, this is some fun game. I like it, you sleazy mofos

    → Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

typical contest from GreenGrape

→ Reply
»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

that moment when u realize the pretests on D are the samples and ur solution is wrong

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hack for D : 5 2 3 5 7 210 Answer : NO

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can send script that generates test.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    You can submit the generator itself instead of input.

    → Reply
»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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.

  1. Move every cube to a unique y-coordinate (n*n moves)
  2. Move every cube to the correct column (n*n moves)
  3. At least one column is empty or this is trivial (n*n) moves (and step 4 doesn't happen)
  4. Using the empty one, solve its left side, then solve its right side (2*n*(n+1) moves)
→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Maybe solving F would be a better choice.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    That is close to what I did:

    1. Move every cube to a unique row (n * n moves)
    2. Move every cube to a unique column s.t. they are sorted by their final columns (n * n moves)
    3. Move every cube to the correct row (n * n moves)
    4. 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

    → Reply
»
6 years ago, # |
  Vote: I like it +171 Vote: I do not like it

F*** your pretests again.

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Well, back to pupil again...But...What can div2B pretest 6 look like?

→ Reply
»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

What was the mapping of problems from VK Cup to problem from #504 and #505?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +23 Vote: I do not like it

    My guessing:

    A — 505 problem C

    B — 505 problem D

    C — 504 problem E

    D — 504 problem F

    E — 505 problem F

    F — 505 problem G

    G — 504 problem G

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're almost right, except B was 505 E.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Lol, so today's E was worth 1250 on VK cup, and today's F 2250 xD?

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +17 Vote: I do not like it

    504 EFG = VK Cup CDG

    505 CEFG = VK Cup ABEF

    → Reply
»
6 years ago, # |
  Vote: I like it +85 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Probably wanted to exclude O(n4).

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got AC with precalculated GCD, so you're correct :Dd 41846474

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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 !!!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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]);
		}
	}
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Holy sh**, the weakest pretests I've ever seen. Goodbye rating, I'll miss you

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Weak pretests for B.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

big fat L

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

These are the contests when you feel grateful for Hacks.

→ Reply
»
6 years ago, # |
  Vote: I like it +91 Vote: I do not like it

System test failed !!!

→ Reply
»
6 years ago, # |
  Vote: I like it +73 Vote: I do not like it

GreenGrape and weak pretests ,still better love story than twilight .

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Waiting for a standard 5 problem contest

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hackforces as usual :(

→ Reply
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

if pretests were sample tests they would be stronger than this pretests

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

F*** your pretests!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

GreenGrape, what's pretest 14 on problem E? My solution seems to pass my validator for all random tests.

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Downvoting the blog right away for the pathetic pretests.

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Good problems(except C) but terrible pretests !

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Doesn't problem C has a nice solution? (Just double the string and find the longest alternating substring that has length shorter than n?)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Why do we double the string? I feel like it should be something obvious but cannot parse the meaning from looking at code submissions.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

no feedback contest

→ Reply
»
6 years ago, # |
  Vote: I like it +60 Vote: I do not like it

He is crazy

http://mirror.codeforces.com/contest/1025/submission/41853226

→ Reply
»
6 years ago, # |
  Vote: I like it -34 Vote: I do not like it

But Is It Rated?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    why not? But somehow CF predictor is not working for me

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +55 Vote: I do not like it

      If cf predictor doesn't work for 15 minutes we are legally allowed to be unrated

      → Reply
»
6 years ago, # |
  Vote: I like it +190 Vote: I do not like it

YYYYYYAAAAASSSSSSSS!!!!!!!!!!!

I can stop whining about my growing record of second places :>>>>>>>>> Waited for this so long, so happy :D

→ Reply
»
6 years ago, # |
  Vote: I like it +167 Vote: I do not like it

Congrats to Swistakk for finally winning something!

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -16 Vote: I do not like it

Downvoted. Thanks for the weak pretests which made my solutions for both B and C failed system test.

May I call this FSTforces?

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

system testing is a massacre for us noobs

→ Reply
»
6 years ago, # |
  Vote: I like it +89 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it -38 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +16 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Most importantly:

            Typically pretests not contain the maximal tests, corner cases, etc.

            → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            8 years ago

            I 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.

            → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Conversely, if passing the pretests should always mean passing the systests, then what is the point of systests?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          The first point is moot assuming you want no solution that passes the pretests to fail the systests, excluding hacks.

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +11 Vote: I do not like it

          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.

          → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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.)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This test won't influence the standings for this round, but we can add it to the tests for upsolving.

    → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +29 Vote: I do not like it

Wrote a script to determine the prize winners (sorry for the ugly code): link

  1. Benq (score = 110)
  2. TLE (score = 107)
  3. ko_osaga (score = 100)
  4. Swistakk (score = 100)
  5. Egor (score = 79)
  6. DearMargaret (score = 75)
  7. ksun48 (score = 60)
  8. Kostroma (score = 60)
  9. natsugiri (score = 45)
  10. AwD (score = 45)

I am 11th in this list :(

UPD: System testing is over, nothing changed.

→ Reply
»
6 years ago, # |
  Vote: I like it +161 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

why cf predictor is not showing anything ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me the reason why changing '&' with '&&' between two booleans give TLE. Solution with '&'

Solution with '&&'

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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(n3) solution

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it
  • Solved: 4 out of 7 ->Solved: 3 out of 7 -> Solved: 2 out of 7 ->Solved: 1 out of 7 (no reverse)
→ Reply
»
6 years ago, # |
  Vote: I like it +99 Vote: I do not like it

The announcement has failed system test too.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

→ Reply
»
6 years ago, # |
  Vote: I like it +42 Vote: I do not like it

It seems that a number of submissions with time complexity O(d(a1, b1)·n) passed problem B, where d(a1, b1) denotes the number of divisors of at least one of a1 and b1.

However, there are only tests with large d(a1) (number of divisors of a1) and d(b1), but not large d(a1, b1): there may be many duplicate divisors of a1 and b1. 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 a1 and b1 below 2·109 with the most d(a1, b1): 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
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +2 Vote: I do not like it

      I searched the prime factors p = 2, 3, 5, 7, 11, ..., and multiplied them to a1 and b1, that is, multiply a1 by p0, p1, p2, ... and multiply b1 by p0, p1, p2, ... each time. Of course we do not want to waste a small prime and use a big prime, so we should avoid multiplying p0 to both a1 and b1.

      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 a1, b1, and xrem, yrem denote 2·109 / a1, 2·109 / b1 in the following code)

      Code

      I think it can even be a nice (and hard) problem in some round (given n, find a1 and b1 below n with max d(a1, b1)) if someone figures out some optimizations to make it run in several seconds :)

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Added, thank you.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    My code still passed this test in practice in 1465ms.
    Link

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We love you so much, GreenGrape... Wish you are already preparing next contest.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

When I click on Editorial, it says "You are not allowed to view the requested page". Please fix it. Edit: Fixed.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated ? Cause i don't see anywhere about rated or unrated announcement.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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://mirror.codeforces.com/contest/1025/submission/41869888

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :)

          → Reply
»
6 years ago, # |
  Vote: I like it +54 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    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 )

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      "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 : )

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        its ok to catch some solutions in that trap, but half of them??? i don't know

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Spoiler
          → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Maybe these downvotes are due to some bots? As happened on Announcement page of Round 502.

    → Reply
»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Any one else thinks random pretests are stronger??

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

when you considering : " come on, codeforces super fast and I get PP with 120ms "

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +53 Vote: I do not like it

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?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

End of the coding weekend! Thank you Mike and CF.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In prob D, I approached it with DP with the parameters left, right and root

So, I guessed the Time complexity will be about O(N^3) but when i made a random test case of 700 it took so long

Then I changed the DP table, and I got MLE...

http://mirror.codeforces.com/contest/1025/submission/41864181

Can anyone tell me where I am wrong?? And, what is the right sol?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretests too weak, Hackforces?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

These submissions are identical, but my solution got tle in system testing :(.

http://mirror.codeforces.com/contest/1025/submission/41880498

http://mirror.codeforces.com/contest/1025/submission/41858978

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 1025B - Weakened Common Divisor

I have a solution and got Accepted but I find a test case can hack the solution:

Solution:41885803

Test case:

3
6 6
2 2
3 3

Expected -1 but this solution got 3. Hacked myself :-)

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Oh my god — they created change.org pull

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your text to link here... Why is this B right?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +45 Vote: I do not like it

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".

→ Reply
»
6 years ago, # |
  Vote: I like it +64 Vote: I do not like it

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Lol, ACM was my life for 5 years, but thanks to you I realized just now what its logo is meant to show.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I still don't get it, can you explain?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        thinking thinking continiously then suddenly an idea strikes you or the aaahhh moment and AC(ballons as you get after solving a problem).

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why this solution can ac http://mirror.codeforces.com/contest/1025/submission/41902787 but this will tle http://mirror.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) "

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you write “a&&b” and a is false,it won’t be true.So we can return false instead of calculating if b is true.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      left first will ac right first will tle I think this mean if I reverse the test data thr data can hack most solutions

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Yeah.Sometimes the hackers or examiners makes the most extreme data.Like random algorithm,SPFA(Shortest Path Faster Algorithm),BST(binary search tree) without adjustment(for example,Splay),will TLE.

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    So if “dfs(l,i-1,i)” are almost false,but “dfs(i+1,r,i)” are almost true,It will be TLE. And sorry for my low English level.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And the same rule as “||”

      → Reply
»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Hi Everyone. Tried to write down A and B's solution. Here's the link. Editorial for A & B

→ Reply
»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I was looking at the fastest solutions to the problem D and found this one — 41869905. What the heck is this?

    if (n == 4 || n == 5 || n == 7)
    {
        cout << "No";
        re 0;
    }

It seems like the author of this solution just explored the tests where his solution is failing and added a simple heuristic. Indeed, it seems like there're no tests with n = 4 and the answer "Yes" which is sad.

→ Reply