When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

MikeMirzayanov's blog

By MikeMirzayanov, 5 years ago, translation, In English

Hello, Codeforces!

I am pleased to invite you to Codeforces Round 547 (Div. 3), which will start on Mar/19/2019 17:35 (Moscow time). Everyone whose current rating is strictly less than 1600 is invited to participate officially. All others can take part out of the competition.

It so happened that the schedule of this month is not replete with rounds (coordinators, we hope for you!). Therefore I decided to partially correct the situation. All the problems of this round were invented and prepared by me on the last day of Hello Muscat Programming Bootcamp 2019 and on flights from Muscat to St. Petersburg. I even specially noted the time for preparation: for the current moment (the problems are ready for testing) I spent about 6 hours on their preparation, including inventing some of the problems. I really like working on problems, this is something at the intersection of creativity and programming. I really hope you enjoy the result of my work.



I am in Oman while writing the problems for the round.

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

Note that the penalty for incorrect submissions in this round is 10 minutes.

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

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

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

I hope a little later a list of thanks to testers will appear instead of this paragraph. So far I only plan to give the round to testing. Many thanks to the testers ivan100sic, KrK, Benq, I_love_Tanya_Romanova, nhho! UPD: And extra thanks to more testers Pavs, awoo, Narts, anon20016, Stresshoover, Ivan19981305.

Good luck on the round
MikeMirzayanov

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Round #543?

»
5 years ago, # |
  Vote: I like it +202 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

MikeMirzayanov is always ready to take codeforces to a great level. Thank you so much for providing us a great platform to learn.

»
5 years ago, # |
  Vote: I like it -16 Vote: I do not like it

from where mike mirzayanov practice problems ?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for this sudden surprise during these boring holidays

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Just asking, but how many time did you sleep for the last two days?

»
5 years ago, # |
  Vote: I like it +62 Vote: I do not like it

I'm happy :)

»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I'm a simple man, i see Mike i upvote

»
5 years ago, # |
  Vote: I like it +112 Vote: I do not like it

Where are div1 rounds?))

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Will Div.2+3 be a new kind of contest

»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Happy to know that the test cases will be stronger enough.

Best of luck

Happy Coding

»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Where's the "Thanks to MikeMirzayanov for codeforces and polygon"???

»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

A round without dear Vovuh, but we still got the great Mike :D
Looking forward to it. ;)

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It seems to have been quite a while since the last contest has ended. So I'm looking forward to the next contest. :)

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Great to see Mike frequent involvement in the codeforces community, really inspiring :-)

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

last div3 was awesome!! looking forward to this now...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"It so happened that the schedule of this month is not replete with rounds..." true... thats sad :(

»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

wow(copy-paste is not contained in the blog of div3 round). I think it is going to be an interesting contest.

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

CF-MEME-2
:3

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm so happy that the original creator is still in touch with us students. Even takes time to think up new and creative problems for us in Div 3 :D

»
5 years ago, # |
  Vote: I like it +40 Vote: I do not like it

You forgot to thank MikeMirzayanov for the awesome Codeforces and Polygon platforms, hope everything goes well!

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think two hours isn't enough to solve 8 problems!!!

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

    It is real to do this, and if this fails, you can always complete tasks after the competition

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    well it obviously isn't but do they care? no, they don't care about us

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Well, it is harder than normal div3.

»
5 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

One of the best contests I have given. All the problems were very interesting. Problem F was very good, I thought of the logic but could not code it within time.

»
5 years ago, # |
Rev. 3   Vote: I like it +47 Vote: I do not like it

I think this Div.3 is a Good Contest with high quality

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

I rewrote my solution for D at the last moment and submitted when 3/4 minutes was remaining.But it was kept in queue for the last 3/4 minutes . And after the contest ended I now see that I got WA for a small mistake that I could have fixed if the verdict was given on time . Is this fair !!!

If there is In Queue problem the duration of round should be extended

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C was nice. Other ones- Don't give up while implementing. (I did) :p

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

    I go TLE. i tried to avoid it but got TLE in different test cases.

    This is my Code

    any hint ?

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

      assuming there are n numbers then you can get n equations with n variables from the constraints given. Use the fact that the sum of numbers is S= n*(n+1)/2 and other n-1 equations can be obtained from the q array. You can get the last number using these equations and then all other numbers can be calculated using this and q array.

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

      If you get any element other can be found. So we try to find out the first one. Observe that p2=p1+q1 , p3=p2+q2 = p1+q1+q2 , p4 = p3+q3 = p1+q1+q2+q3 and so on. So add all p1,p2...pn which is an equation in p1 and you already know the sum of the expression. Thus you get p1 and other elements. Output -1 if p1 is not an integer or obtained permutation doesn't contain all numbers from 1 to n.

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

      The time complexity of your code is O(n*n)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C was very nice problem, can anybody explain me the approach. Can't wait till editorials are out!

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

    You are given essentially a difference array, so if you compute the prefix sum array you should get the original elements offset by some number. You keep track of minimum and maximum of this prefix array, and the first element should be 1-minimum. While constructing the original array you also make sure each element from 1 to N is seen once only.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Hello! Let's write our array as: p2-p1, p3-p2, p4-p3, ... , p(n) — p(n — 1).

    Now let's find the prefix sum of this array. Then we will have following: p2-p1, p3-p1, p4-p1, ... , p(n) — p1.

    I think it is obvious that if we have two same elements in the prefix sum array then answer is -1.

    Otherwise let's take element n-p1 (it is the maximum). Let it be equal X. Then n-p1 = X -> p1 = n-X. Now, using this p1, we can construct our array. If such answer is valid, we can print it. Otherwise answer is -1.

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

    You can assume the first element be x. then the second element is q1 + x third element is q1 + q2 + x. the fourth element is q1 + q2 + q3 + x and so on. the sum of all elements is (n*(n+1))/2

    so you can find the value of x.

    after finding x you can easily find entire permutation

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    I solved using prefix sums and some basic maths.

    Approach:

    $$$(q_1) = (a_2-a_1)$$$

    $$$(q_1+q_2) = (a_3-a_1)$$$

    $$$(q_1+q_2+q_3) = (a_4-a_1)$$$

    And so on. Summing all the above equations we get:

    $$$\Sigma ($$$prefix terms of $$$q)=(a_2+a_3+...+a_n)-a_1(n-1)$$$

    $$$\Sigma ($$$prefix terms of $$$q)=((n*(n+1)/2)-a_1)-a_1(n-1)$$$

    Find $$$a_1$$$ from the above equation. Once you find $$$a_1$$$, you can easily find the rest terms using the given values of $$$q$$$. Finally, check if all terms are present in the range $$$1$$$ to $$$n$$$ and also check if all terms are distinct or not. If not, print $$$-1$$$ and exit. Else print the numbers.

    I'll leave the implementation part for you to try. Hope this helps. Happy Coding.

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

      Nicely explained. Thanks

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

      I followed the way you explained but getting WA could you please give a look here? 51556867

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

        You are probably getting an integer overflow. Make sure you have used the right data types.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Think of it as plotting n points on a 2d grid where the index of the array is the x coordinate and value at that index is the y coordinate, start from (1,0) (assume the value of the first element to be 0) and use the given array q for calculating the position of next points. a[1] = 0 a[2] = a[1] + q[1] a[3] = a[2] + q[2] and so on. Now find the minimum value in this array, let the minimum value we get from the constructed array be min_val. Now add min_val+1 to all the elements of the array (shifting the whole plotted figure up so that the lowest point is 1).Now check whether the array is a valid permutation or not and print the result. Here's the implementation of above mentioned approach. 51508498 Hope this helps.

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

    My approach i wrote the O(n ^ 2) approach to find a sequence. let's assume that the first element is a1 = n, so we get sequence a1, a2, .., an if we decrease the first element by 1 all other elements also decrease by 1 so i assume that the first element is n and i make sure that are elements are distinct and if i increase or decrease my sequence the min and max element inside the sequence is 1 and n. 51541819

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The speed at which people here solve problems is just unbelievable! Kudos!

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Kudos to MikeMirzayanov. Organized a great Div. 3 round in minimal time!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well I thought there were ONLY 24!!!! characters in English then I got sweet WA for D at last second, switch to 26 after the contest and I got AC What the heck I am thinking about ????

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem G is a fake problem! I'm so weak

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you help me problem C, I got TLE. I generate all permutation and check for each of them. My code: https://ideone.com/PME2fJ

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

    This complexity is too high I think you should learn from others' code.

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

    The number of all permutation is $$$O(n!)$$$, and for each permuation, you need $$$O(n)$$$ to check it.

    So your solution is $$$O(n\cdot n!)$$$, quite large :(

    You can try an array $$$n, n-1, n-2,\dots,1$$$, and n is $$$10^5$$$, your solution will get TLE :(

    When n is quite small, your solution can get the answer.

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

      Thank you! I will tried another solution.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F?

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    Just use map<int,vector<R,L>> store the sum of every l and r,after that you can sort the vector and get the answer.

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

    $$$n \le 1500$$$, so you can use a map to store each block with the same sum.

    For each sum, there are many segments, and some of them may intersect. so you need to calculate the maximum number of disjoint segments, and this problem an be solved using greedy algorithm.

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

      How would you calculate time complexity for this solution? O(n^2) for all possible sum but what about upper bound on processing each vector corresponding to a certain possible sum?

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

        There are $$$n^2$$$ possible sum, so $$$O(n^2 log n^2)$$$ insert all the sum into the map.

        In the greedy algorithm, we also need at most $$$O(n^2 log n^2)$$$ to sort all the elements(each element will be sorted at most once), and $$$O(n^2)$$$ to get the answer.

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

        Same as total times insertion is done because each pair is processed only once.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I enjoyed this round Strong pretests and balanced problemset

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Awsome DIV3 contest!!!

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can someone please help with f2

»
5 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

For question 2, How

1
1

is invalid input. According to question it seems good.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i have a question what will happen if you hack your own code?

»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

How to solve H?

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

kudos to MikeMirzayanov !!! . Conducted really good round with awesome questions.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why its showing WA even though the TC is giving the correct result on my PC. solution

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

    I'm pretty sure that your solution also gives the wrong result on your computer. Check again.

»
5 years ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

plz find a test case at which my solution is getting wrong answer. https://codeforces.com/contest/1141/submission/51545372

»
5 years ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

Problem E , Can anyone tell me why this code is giving wrong answer at test case : 92

https://codeforces.com/contest/1141/submission/51547489

what i did is , suppose we had played x-1 round and currently at round x , we will check whether we can kill monter in that round x or not , if yes we shift high to curr round — 1 else low to curr round + 1 .

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

    Write a brute-force program and make some small scale random input to check whether your algorithm is correct.

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

    If you can't kill the monster in round x, it doesn't mean that you can't kill it in earlier rounds.

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

    why i am dwnvted. have i asked anything wrong

»
5 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Overall round was pretty good, I thought that this was one of the easier Div 3. Although wish I had 10 more min to submit E ;) I hope to see more of these types of problems in the future.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone could say me the solution of problem G ?

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

    So, I haven’t submitted this solution yet, but I think I have the idea.

    Generate the degree sequence for the tree. The k nodes with the highest degrees will be bad nodes. Then the (k+1)th highest degree (call it c) will be the number of colors needed so that (n-k) nodes are good and k are bad. That is, with c colors, we can color edges so that (n-k) nodes have edges of all distinct colors. This will work because (n-k) nodes will have degrees <= c.

    We can then choose a root, and greedily color the tree from the top down.

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

      why color the edge greedily will be the answer ? (with dfs)

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

        let's say the highest degree is C.

        if we're at a node which has a degree greater than C we can colour them all the same colour, it doesn't really matter. If it's less than or equal to C, we start colouring it from 1 and keep incrementing it for each child(with the exception that it can't be the edge connecting it to the parent's colour)

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

          thank you . i understood very well :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here,the scenario is look like for starting questions Div2<Div3

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone solved problem E using Binary search, I am getting wrong answer on test case 17.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Your binary search borders are so high they cause long long overflow in min hp calculations.

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

      Yes i got it why it is failing. can u suggest what changes should i make?

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

        I set the upper bound to $$$\lceil \frac{hp}{-sum} \rceil$$$ in my solution and it worked fine.

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

          Yes, you are applying binary search for the round right? I was applying for the minute at which the monster will be killed. The solution with binary search on rounds got accepted. Thanks.

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

            Oh, true, binary search on minute is surely inapplicable.

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

              I had to post this

              Spoiler
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    yes.. i solved it.. see my solution and if doubt dm or tag me in announcement

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

      Yes, I saw ur solution, it was involving binary search on rounds right? I was applying binary search for the exact minute at which the monster will be killed, and apparently as Pikmike mentioned, while calculation of min, long long would overflow. Thanks for help!

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

        no calculation of minute along with overflow will give wrong answer .

        if it is not possible to kill monter in x th minute then its not possible to kill monster in < x minutes , is wrong approach . u have to take rounds .

        at first i thougt bs on minutes , but laster i realized its wrong .

»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Why my contribution went from 0 to -4 by itself (just wondering)

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

whats going on?? why C is rejudged?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem c Many people construct a sequence starting at 1, and then judge whether {1 2 3 ... n} is satisfied. In the judgment, some people use the Vis array mark to determine whether there are duplicate numbers. This is not a good solution. Considering the worst case, (2e5 19999 19999.....), this will appear. The case where the array is out of bounds.

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

    Meh, that's the boring hack. Check this solution 51538168! $$$cp$$$ gets equal to $$$-2^{31}$$$, then $$$x$$$ becomes $$$2^{31} + 1 = -2^{31} + 2$$$ and thus no $$$-1$$$ checks are hit because the conditions are too weak.

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

      X and map should be long long? I think his code is not rigorous.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Basically, $$$x$$$ and $$$cp$$$ is enough to be long long. I don't think you can break map being int tbh.

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

C:

Runtime error on test 42;

solved: 5->4;

standing:249->756;

I:happy->unhappy;

Anyway, excellent and innovative problemset .

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

    You are already very good, I only solved 3 problems.

    Great contest, I learned a lot of ways to think about the problem.

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

    Same thing happened with many people(including me).

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

    Not sure those are final, as an unrated before taking part in the contest, I'm already rated, but seems final standings are yet to be shown.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody please tell me why this solution for problem F2 is failing at test case 28?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    The segments should be sorted by the right end, so you greedily take always the one that ends the earliest.

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

      Thanks. Just by changing sort to right end it passed all the test cases.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone, Please explain D.

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

    Just think simple!
    We know that ? will make compatible pair with anything!
    So first we make pairs that doesn't have any ? and after that pairs that has exactly one ? and at the end pairs that are both ?.
    It is clear that the algorithm is the optimal.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

wrong answer in D: "You can't use one boot in two pairs", can anyone tell me what it means? and why it give me a wrong answer, this is my practiceYour text to link here...

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

    Look, the boots are for the left or for the right foot.
    You want to match these boots (make pairs of left and right boots).
    And "You can't use one boot in two pairs" means that you can't match a boot with two other boots.
    For example you have two boots of left foot numbered 1 and 2, and two boots of right foot numbered 3 and 4. you can't match boot number 1 with boots 3 and 4, you can choose at most one of them.

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

      oh, Thanks for your answer! I have thought that! But why my practice is wrong, I have checked for much time, can you speed a little time checking my practice? Wrong answer on test 22, the test data is so long, I can't see the remaining part.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought successful hacking would add my points, but it seems to be not the case. The rule says it's worth 100 points. Has it been changed?

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

    that is for div2 and div1 contests (expect educationals).
    hacks in contest's that have hacking phase after the contest don't have any point.

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

      Thanks for clarification! Is it stated somewhere?

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for this good contest.

»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Why did so many people fail problem C? Somehow, my solution passed but I was still wondering.

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

    most people did not check the duplicate elements they generated in permutation

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

C was indeed a creative problem! :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When can we expect editorial of this contest?