MikeMirzayanov's blog

By MikeMirzayanov, 7 months 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, PikMike, Narts, anon20016, Stresshoover, Ivan19981305.

Good luck on the round
MikeMirzayanov

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

»
7 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Round #543?

»
7 months ago, # |
  Vote: I like it -29 Vote: I do not like it

MikeMirzayanov you need to join the gym xD

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    Hold on guys I meant the gym on codeforces what did you all think lol

»
7 months ago, # |
  Vote: I like it +202 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -16 Vote: I do not like it

from where mike mirzayanov practice problems ?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for this sudden surprise during these boring holidays

»
7 months 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?

»
7 months ago, # |
  Vote: I like it +62 Vote: I do not like it

I'm happy :)

»
7 months ago, # |
  Vote: I like it +33 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +112 Vote: I do not like it

Where are div1 rounds?))

»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
7 months 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

»
7 months ago, # |
  Vote: I like it -18 Vote: I do not like it

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

»
7 months 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. ;)

»
7 months 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. :)

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

»
7 months ago, # |
  Vote: I like it -22 Vote: I do not like it

Sir, why don't you write Tutorial on Competitive Programming for low rated users like me. It will be a great honor to learn from you. And hats-off to your great determination in making this community more strong.

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
7 months 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 :(

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

»
7 months ago, # |
  Vote: I like it +35 Vote: I do not like it

CF-MEME-2
:3

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Please change the contest timing to same as of last 6-7 contest that is 1 hour later from current start time ,

»
7 months 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

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

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    7 months 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

  • »
    »
    7 months 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

»
7 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Very difficult problems Bad Contest for beginners

»
7 months ago, # |
  Vote: I like it -18 Vote: I do not like it

MikeMirzayanov Sir , Please create little bit easy problems for beginners

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

Well, it is harder than normal div3.

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

»
7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I submitted problem D in the last second but the submission was not considered apparently?

»
7 months 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

»
7 months 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

  • »
    »
    7 months 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 ?

    • »
      »
      »
      7 months 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.

    • »
      »
      »
      7 months 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yep :(

        I tried to minimize it as possible i can but it was the same order O($$$ N^2 $$$) ... lack of mathematical thinking as usual :")

»
7 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Server lag ? Clicked "submit code" at 2:00, waiting to paste code at 00:43, guess what ? Loading and loading until the contest is over, submission denied. How fucking frustrated ! Moreover, judging system works like an "out-of-budget-server", "In Queue" more than a minutes for every submission ?

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

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

  • »
    »
    7 months 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

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

  • »
    »
    7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
7 months 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 ????

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

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

»
7 months 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

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

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

      Thank you! I will tried another solution.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F?

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot both of you :)

    • »
      »
      »
      7 months 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?

      • »
        »
        »
        »
        7 months 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.

      • »
        »
        »
        »
        7 months 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.

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

I enjoyed this round Strong pretests and balanced problemset

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Awsome DIV3 contest!!!

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

can someone please help with f2

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

»
7 months 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?

»
7 months ago, # |
  Vote: I like it -6 Vote: I do not like it

The round gave a feeling of div2 . good one . not so easy .

»
7 months ago, # |
  Vote: I like it -34 Vote: I do not like it

How to solve H?

»
7 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
7 months 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

  • »
    »
    7 months 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.

»
7 months 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

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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it -30 Vote: I do not like it

    please tell anyone . MikeMirzayanov whats the tc : 92 , why my code is giving wa

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

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

    why i am dwnvted. have i asked anything wrong

»
7 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Deleted

»
7 months ago, # |
  Vote: I like it -9 Vote: I do not like it

+1 if you read MikeMirzayanov as Mike Mirazapur XD

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Have the ratings after the contest not been updated yet?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone could say me the solution of problem G ?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 months 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)

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thank you . i understood very well :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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?

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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.

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

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

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I had to post this

              Spoiler
  • »
    »
    7 months 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

    • »
      »
      »
      7 months 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!

      • »
        »
        »
        »
        7 months 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 .

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes u are right. I realized it very late. :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How long will it take to update the Ratings?

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did system testing rollback?

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

whats going on?? why C is rejudged?

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

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

      • »
        »
        »
        »
        7 months 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.

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

  • »
    »
    7 months 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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same thing happened with many people(including me).

  • »
    »
    7 months 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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can someone please tell me why codeforces is giving a runtime error on test 42 in C? It is working fine on my machine

»
7 months 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?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone, Please explain D.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it. Thanks a lot Can you please give some hints for E also.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the tutorials be uploaded?

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

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have found it!!!

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          and here is a test for you
          6
          ??aa??
          ??????

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you very much! I have done it!

»
7 months 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?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for clarification! Is it stated somewhere?

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

Thank you for this good contest.

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

C was indeed a creative problem! :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When can we expect editorial of this contest?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial please.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the editorial?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

someone please explain that in problem e how to calculate number of cycles.