Автор GreenGrape, 6 лет назад, По-русски

Привет.

В 19.08.2018 16:35 (Московское время), состоится общий рейтинговый раунд Codeforces Round #505. Этот раунд идет в паре с раундом #504.

Часть задач взята с Финала VK Cup 2018 (ashmelev, Errichto, Lewin), часть придумана мной. Спасибо моим товарищам — Диме (cdkrot), который, кстати, является координатором этого раунда, Коле (KAN), который позвал меня его проводить, а также Грише (vintage_Vlad_Makeev) и Ильдару (300iq) за то, что они просто клевые.

Также спасибо Майку MikeMirzayanov за множественные баг-фиксы и замечательный Codeforces!

Задач будет семь со следующей разбалловкой:
500 — 1000 — 1500 — 1750 — 2250 — 2750 — 3500

UPD. Систесты окончены. Разбор

Поздравляем победителей!

  1. Swistakk
  2. DearMargaret
  3. Kostroma
  4. Benq
  5. AwD
  6. xumingkuan
  7. webmaster
  8. TLE
  9. Egor
  10. kriii

Так же, как и в прошлом раунде, по инициативе компании ВКонтакте будут разыграны очки GP30.

Участники сортируются по очкам за оба тура (если участник не участвовал в одном из туров, очки, набранные за него, полагаются равными нулю); при равенстве очков как тай-брейк используется максимальное за оба тура время, прошедшее от начала тура до последней посылки, прошедшей претесты.

Напоминаю, что лучшие 10 по сумме очков GP30 получат фирменного плюшевого персика.

Надеюсь, что вам понравится. Удачи!

  • Проголосовать: нравится
  • +91
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +429 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

palindromic round :D

»
6 лет назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

имя раунд

»
6 лет назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

Ok so greengrape, another shitty maths contest.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -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.

»
6 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

How many problems, duration, scoring?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +51 Проголосовать: не нравится

some strong pretests please GreenGrape :D

»
6 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Happy Hacking&&High Rating

»
6 лет назад, # |
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....

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

How many problems and what will the scoring be like?

»
6 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

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

»
6 лет назад, # |
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")

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I think the last few games are very difficult.

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I think the problems will be very interesting.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

.

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    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.

»
6 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Will it be harder than 504 or not?

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +127 Проголосовать: не нравится

Mike Mirzayanov slaps codeforces roof

  • this boy can hold so many contests without crashing
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I wish to turn blue!

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Hope I will become expert after this round

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я так понял, что примеры из условий — это и есть все претесты.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Совет — если хочешь зашутить в комментах, чтобы твою шутку оценили и при этом в посте есть англ перевод, пиши на англ

»
6 лет назад, # |
  Проголосовать: нравится +100 Проголосовать: не нравится

U want strong pretests? Hehe. Hehehehehe. AHAHAHHAHAHAHAHHAHAHAH!

»
6 лет назад, # |
  Проголосовать: нравится +207 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +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).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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).

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

    http://codeforces.net/contest/1025/submission/41844612

»
6 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          can you explain a bit more abt rootpos

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 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.

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 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 ?

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

what was pretest 6 for problem B?

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Как решать D?

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve problem B?

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve B and C?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          My bad, this will time out.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
              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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +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]).

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +172 Проголосовать: не нравится

Me while coding div2C:

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    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.

    • »
      »
      »
      6 лет назад, # ^ |
      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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится

Me vs. problem C

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve C?

  • »
    »
    6 лет назад, # ^ |
    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)

    • »
      »
      »
      6 лет назад, # ^ |
      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.

  • »
    »
    6 лет назад, # ^ |
    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

»
6 лет назад, # |
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.

»
6 лет назад, # |
  Проголосовать: нравится 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.

»
6 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Is ans for C just max for all cyclic shifts?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Yes.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится 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.net/contest/1025/submission/41865118]

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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

»
6 лет назад, # |
  Проголосовать: нравится +62 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    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).

»
6 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +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"

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anyone used articulation bridge to solve D like me?

»
6 лет назад, # |
  Проголосовать: нравится +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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    F is similar to the JOI problem: solution

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to solve B?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • bwbw (most common)
      • www
      • w

      Two latter ones seemed mostly participants' implementation failure though.

»
6 лет назад, # |
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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +48 Проголосовать: не нравится

    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

»
6 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

typical contest from GreenGrape

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 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?

»
6 лет назад, # |
  Проголосовать: нравится +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.

  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)
  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe solving F would be a better choice.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
6 лет назад, # |
  Проголосовать: нравится +171 Проголосовать: не нравится

F*** your pretests again.

»
6 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Тупые претесты как же я вас блин ненавижу

»
6 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Probably wanted to exclude O(n4).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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)

»
6 лет назад, # |
  Проголосовать: нравится +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 !!!

»
6 лет назад, # |
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]);
		}
	}
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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).

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        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)

    • »
      »
      »
      6 лет назад, # ^ |
      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!

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Weak pretests for B.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

big fat L

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

These are the contests when you feel grateful for Hacks.

»
6 лет назад, # |
  Проголосовать: нравится +91 Проголосовать: не нравится

System test failed !!!

»
6 лет назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Waiting for a standard 5 problem contest

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hackforces as usual :(

»
6 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

F*** your pretests!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Downvoting the blog right away for the pathetic pretests.

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Good problems(except C) but terrible pretests !

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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?)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
      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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

no feedback contest

»
6 лет назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится
»
6 лет назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

But Is It Rated?

»
6 лет назад, # |
  Проголосовать: нравится +190 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится +167 Проголосовать: не нравится

Congrats to Swistakk for finally winning something!

»
6 лет назад, # |
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?

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

system testing is a massacre for us noobs

»
6 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
    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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          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.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Most importantly:

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

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 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.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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).

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          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.

»
6 лет назад, # |
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.)

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +29 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +161 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

why cf predictor is not showing anything ?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Solution with '&&'

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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(n3) solution

      • »
        »
        »
        »
        6 лет назад, # ^ |
        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.

  • »
    »
    6 лет назад, # ^ |
    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

»
6 лет назад, # |
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)
»
6 лет назад, # |
  Проголосовать: нравится +99 Проголосовать: не нравится

The announcement has failed system test too.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

codeforces need to organize more combined contests(div1+div2). bcoz i think solving more not easy problems with stronger participants let us to rise faster

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D ?

»
6 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

It seems that a number of submissions with time complexity O(d(a1, b1n) 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
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Added, thank you.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 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)).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.net/contest/1025/submission/41869888

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 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 :)

»
6 лет назад, # |
  Проголосовать: нравится +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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -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 )

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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 : )

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Spoiler
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

Any one else thinks random pretests are stronger??

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
6 лет назад, # |
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?

»
6 лет назад, # |
  Проголосовать: нравится 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 :)

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.net/contest/1025/submission/41864181

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Pretests too weak, Hackforces?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

http://codeforces.net/contest/1025/submission/41880498

http://codeforces.net/contest/1025/submission/41858978

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
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".

»
6 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

When do we get the editorials?