Educational Codeforces Round 113 [Rated for Div. 2]
By awoo, history, 3 years ago, translation, In English

Hello Codeforces!

On Sep/08/2021 17:35 (Moscow time) Educational Codeforces Round 113 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Geothermal 6 183
2 qpEDop_MuXauJloBu4 6 216
3 hanbyeol_ 6 219
4 tute7627 6 221
5 fastmath 6 287

69 nice successful hacks and 304 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Geothermal 0:00
B Geothermal 0:04
C Geothermal 0:07
D jayeshaw 0:18
E tzc_wk 0:28
F jiangly 0:30

UPD: Editorial is out

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

Comments Comments (209)
| Write comment?
»
3 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Hoping for a great contest!

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

    Weak pretest of F even do not have cases of disconnected :(

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

      So this is the reason why it was a "good contest" lol

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

      There were disconnected graphs but no ones with a lot of edges. I personally think it was decent enough for pretests.

      To be honest, from your solution I'd say it should've been pretty fair for you to assume that it passes only if the tests are weak. Maybe I don't know the estimates on the number or the sparsity of hamiltonian paths in connected graphs, but you do. In that case I'd love to hear why that solution can be fast enough.

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

        It is such interesting. I also don't know why my code can run so fast :D .But it seems to be slow when it doesn't exist a solution (disconnected or do not have a vaild path).I judged them before my programm and can AC now.

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

          There is a lower bound on the minimum possible non-zero number of hamiltonian paths for some fixed n and m. It seems to be somewhere around $$$10^5$$$ for 12 45-48. I guess you are abusing this fact implicitly.

          Maybe you'll be able to pass any test within given constraints with more optimizations.

          Feel free to tinker with my generator to make your solution (or my tests :P) stronger. It finds connected graphs with the smallest number of hamiltonian paths, spitting out every improvement (or same answer but not too often) into folder "tests". I run it with "./gen n m k 1e5 0.999", these temperature and cool down rate seem to get you nice graphs fast enough.

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

Thank you all the people who have put in time and efforts in making this contest for us. Upvoted!

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

What are the score distributions for individual problems?? Looking forward to a great contest!!

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

Looking forward to losing my newbie virginity to this contest !

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

    Never thought u to be a saint, I believe that u r a slut , haha

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

Is it just me or half of the trickiest problems am not able to solve during practice are always authored by BledDest.?:)

Looking forward to it!

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

Ok, new contest, new story, just gotta give virtual rounds of all contests by this author and that's enough practice. Wait...

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

This will definitely be another brilliant contest!

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

Our friends at Harbour.Space don't have any messages for us this time?

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

Always like Educational Rounds :D

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

    In fact,Educational Rounds is good for our rating :)

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

To be educated in educational round..

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

    Tbh, Atcoder ABC's are more educational nowadays.

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

      bro you said Atcoder two times. ABC = Atcoder Beginner Contest. Atcoder ABC = Atcoder Atcoder Beginner Contest.

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

    In my experience with educational rounds, the only 'educational thing' with them is that they are not educational :/

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

Nowadays participating in ABC contests is helpful for CF edu rounds lol

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

After a long time, an educational round is going to be held. I hope the problem set will be interesting and contest will enjoy the round.

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

shinzou WO Sasageyo...!!

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

    What is freedom?

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

      What is love?

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

      Freedom is an action governed by nothing but your own free will.

      • Eren Yeager (aka) Hitler2, tatakae yeager, Ereh, Hitler kin, Angry German kid, True Sigma, Suicidal Bastard.
      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    what is the lie, what is the truth, what to believe

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

      The truth is whatever lie you choose to believe...

      And the truth is that neither of us were able to solve problem C... I choose to believe that if I had some extra time... maybe I could have solved it...

      PS: This is what I chose to believe, It's not the truth.. the truth is I couldn't have been able to solve it even if I would have dedicated my complete day on it... but I chose to believe that I could have provided that I just had 1 more hour for it.

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

        factorial and mod disasterrrrrr

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

          They are the true enemy of mankind... They must be annihilated as soon as possible so that the human race may be able to continue for eternity.

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

This doesn't seem Educational at all. :( Not at all for Div-2 also

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

Div-2 C :

bool unsolved = true;
while(unsolved)
{
crying due to mod&factorial = true;
if(crying due to mod&factorial)
unsolved = true;
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I too am crying due to the 3rd question... :_)

    1st problem : combinatorics

    2nd problem : modulo

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

      Meanwhile me :

      WA on test 4

      ll sub(ll a, ll b){
  return (a-b) % mod;
}

      AC

      ll sub(ll a, ll b){
  return (a-b+mod) % mod;
}
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I am really tired ... was unable to solve problem C even after struggling for 1.5 hrs straight.

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

      Me after this contest:

      Change my organization to "Fool of Combinatorics and Number Theory"

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

the first testcase in C makes the solution obvious

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

    But you also need to be careful with other special situation!

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

How to solve C?

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

      This logic is easy to come up with...I feel the tough part was to calculate bad permutations using combinatorics

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

        the tough part is to not mess up the calculation and mod correctly

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

    The answer will only depend on the largest number, second largest number, and their respective frequencies. I'll denote largest number as $$$max$$$ and second largest number as $$$secmax$$$. If the count of $$$max$$$ is greater than $$$1$$$, then the answer will $$$factorial(n)$$$ (all possible permutations), because all permutations will be nice in this case. If the difference between $$$max$$$ and $$$secmax$$$ is greater than $$$1$$$, then the answer will be $$$0$$$ (since no permutation can be nice in this case).Now the only case remaining is when $$$max=secmax+1$$$ and count of $$$max$$$ equals $$$1$$$. Here, a permutation will not be nice only if $$$max$$$ is behind all the $$$secmax$$$ in the permutation. So the number of not nice permutations will be $$$nCr(n,(countmax+countsecmax))*factorial(n-countmax-countsecmax)*factorial(countsecmax)$$$. The final answer will be $$$factorial(n)$$$ — ($$$no.$$$ $$$of$$$ $$$not$$$ $$$nice$$$ $$$permutations$$$), which we calculated above.

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

      Could you explain the formula for the number of the "not nice"-permutations?

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

        I just realized that I complicated the formula a bit. Basically, think of the permutation consisting of $$$n$$$ empty spaces. First we need to fill the empty spaces with all the numbers which are smaller than $$$max$$$ and $$$secmax$$$. There are $$$nCr(n,(countmax+countsecmax))$$$ ways to fill the permutation with the smaller numbers and $$$factorial(n-countmax-countsecmax)$$$ ways for the smaller numbers to permute. Now we only have to worry about the no. of permutations of all $$$max$$$ and $$$secmax$$$ in the rest of empty spaces. Since there is only 1 $$$max$$$ and it will be placed in the last of the remaining spaces, we only have to find the number of ways to arrange all $$$secmax$$$, which is $$$factorial(countsecmax)$$$.

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

      Thanks alot for explanation.

      I am not able to understand that we have secmax whose count is "countsecmax" ,they all are same value wise, then why are we multiplying factorial(countsecmax) in invalid case.

      Lets say we have 333 , so to arrange them we only have 1 way right?

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

        The permutation they have asked for is for the indexes (1 to n) and not the values of the permutation themselves.

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

Problems were hard.

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

How to solve D

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

    I missed the registration, but my guess is

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

    Just separate the points into two parts one where the x of the point matches with any of the x of vertical roads and other part where the y of the point matches with the y of any horizontal road. these two parts may or may not be disjoint as it is also possible that point's x as well as y matches with any vertical and horizontal road then this point will be the part of both parts.

    Now solve the answers for both the parts separately ->

    for 1st part Sort it using a comparater which sorts first according to y and then according to x. Now just iterate one by one on the points since the points are sorted using the above comparater so the points will be divided into groups which lie on the same horizontal line(same y) and this group is also sorted according to x also. Now we can see that the vertical roads divides the x axis into some segments. (x0,x1) (x1,x2) (x2,x3) ........

    for calculating the answer we will maintain one array f of size (n-1) where ith element represents the number of points that lie in the ith segment and whose y is also less than the current y(on which we are currently at in the iteration).

    f[i]=number of points which lie in the segment (x[i],x[i+1]) end points not included.

    for finding the segment-number of a point (a,b) we can easily find it using binary search(using lower_bound in c++)

    now let us assume we are at a point (a,b) so to find out the pairs that this point will make with other points that are already visited in the iteration we can make use of the array f.

    first we find the segment to which the point (a,b) lies and then the bad pairs which it makes is equal to f[segment-number]. because f[segment-number] stores the number of points that lie in that segment in the previous horizontal line (y<b). This can be easily observed that bad pairs are the points which strictly lie inside same segment(end points not included) and which do not lie on the same line.

    Now when we move to the next horizontal line (y>b) then we need to add the point (a,b) to its respective segment(increment value of f[segment-number]) so that it can contribute the points which lie on the horizontal line above it.

    what we can do is we can maintain a cnt variable which stores the number of points which lie on the same horizontal line and in the same segment of x axis.When we move to next segment then we can just update the value of f[prev-segment-number]+=cnt.

    for 2nd part-

    Sort it using a comparater which sorts first according to x and then according to y. It's exactly same the difference is just the change of axis now we will iterate vertical line by line and in increasing order of x.Now the y axis is divided into segments.

    Link to my code- https://mirror.codeforces.com/contest/1569/submission/128325617

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

adedalic vovuh BledDest I recently discovered this youtube channel https://www.youtube.com/watch?v=ScJlgbUDMq4, where solutions of the ongoing contest are being shared. I was not able to solve any problem in this contest since I m a newbie but I also don't go for these unethical ways to increase my rating. Can anything be done against this form of cheating?

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

    These guys now even seem to be crowd-sourcing solutions.

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

      yep, I would be really happy if something could be done against these people

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

A very heavy meme :

Pics-Art-09-08-10-05-20

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

I might go -200 today , I am not losing hopes

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

My soln 128273615 of F should be hackable. I just have an early exit in case a particular assignment of colors finds a palindromic path. It reduces the time taken from 35s (locally) to 1s (on present test cases). 128279840 takes 30s — 40s locally on a complete graph.

Update: Hacked by pikmike. Accepted submissions would now get TLE on tc 103 during system testing.
Update 2: 128290681 should still be hackable.

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

Solved C literally a minute after the contest ended damn

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

    If it makes you feel better I forgot take mod of the final answer.

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

      I forgot to use LL for D, and got two WA at testcase 6. After contest finshed I just realized...

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

Could anyone give me a hint for problem B ?

I thought about using backtracking but could not implement it.

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

    Just try for individual competitions... using brute force suppose there are two players i and j, if any of them is aiming for 1, you can simply draw the match '=', if both are aiming for 2, think... if A has won in any of the previous matches... declare B and the winner and A as the looser, else B as the winner....

    In the end just check if all of the players were able to achieve their goals or not... the problem is solved...

    This is my submission... ignore everything above //MARK :- SOLUTION=====...

    I hope this will help... ;)

    128236197

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

    First of all separate all the players who are satisfied with not losing a single match from those who need to win at least one as games need to be won or lost only in the case of the latter.
    Now, a valid solution can only exist if the number of unique pairs that can be formed between the players of the second type is greater than the number of players of the second type.
    Why?

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

could problem C be solved using combinatorics? i tried below solution but i got wrong answer

let 
maxValue = maximumValue in the array
nextMaxValue = maxValue - 1
maxCnt = # maximum Value in the array
nextMaxCnt = # nextMaxValue in the array
fact[n] = n! (factorial)
comb[n][r] = nCr (n Choose r)

case1 if (maxCnt == 1 && nextMaxCnt == 0)
    answer = impossible

case2 if (maxCnt >= 2)
    answer = fact[n];

case3 if (maxCnt == 1 && nextMaxCnt >= 1)
    r = maxCnt + nextMaxCnt
    answer = fact[n-r] * (comb[n][r] * (fact[r] - (fact[maxCnt] + fact[nextMaxCnt])))

----updates---

I got AC. after I use modular inversion when divide it. solution: https://mirror.codeforces.com/contest/1569/submission/128287672

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

    in the last case, basically its the number of ways to put the maximum element in any spot while there exists atleast one or more nextMax on it's right side

    you can see my submission here https://mirror.codeforces.com/contest/1569/submission/128280479

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

      thanks for the sharing. but could you elaborate more? I cannot understand left and right in your solution. or could you provide a related thread for it? Thanks in advance.

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

        Yeah sure, so basically for instance in the last test case n = 6 and there's 3 NextMax so NextMaxCnt = 3 and so we have 2 elements that's less than NextMax, right? if we put the Max(which is 4) at any spot from 1 to 3 there's gonna always be a nextMax on it's right side. So the answer is premutation of the 5 spots (all spots except spot of the Max). now from spot 4 to 6, the answer would be the number of ways to have atleast one nextMax or more on the right side of the Max. There's many ways to calculate this but i calculated it by totalnumber of ways to arrange 5 spots subtracted by number of ways to have NO nextMax on the right side of the max. In my case left is just number of ways to order the left remaining spots on the left and right is the number of ways to have NON nextMax values on the right.

        Apologies if my explanation isn't the best.

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

          Thanks for the explanation it helps a lot!

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

            if you still didnt understand it lmk. But basically the idea is to calculate the number of ways to have atleast one or more nextMax on the right side of the Max given that the max can be at any spot. There's many ways to calculate that i assume

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

Nice problem E. I came up with some backtracking optimizations but couldn't complete it on time :D

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

Nice set of problems, got the logic for D but found it implementation heavy, it took all my time, and couldn't make code for it.

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

In E, is it fast enough to do 2^28 * (some big constant) ?

It looked way too slow to me so I didn't code it, but the idea was to brute-force the first three levels of the tournament, bringing the number of contestants from 32 -> 16 -> 8 -> 4, and for the final four to have precomputed in O(32^4*2^4) all the numbers that can be achieved, for every possible quadruple of people playing. (I can see the hash of the first three levels, and substract it from H to get the required hash of the last levels).

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

How to do E?

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

    For k=5 you just can solve for k=4 (2^15) and get the solution with meet-in-the-middle (2^8).

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

      Oh, so for the "upper" part of the tree and the "lower" part of the tree, and you combine them in the final game where the total winner is determined? Or how do you split it

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

        If you know winners of first phase(16 matches), 16 teams will remain and it's same as k=4 (You can determine places with O(2^(2^k-1)) bruteforce). To determine winners, you can split first 8 matches, and last 8 matches, and combine the results with meet-in-the-middle.

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

          Ok I'm too dumb to understand I'll wait for the editorial

          Edit: Ok I understand now, thanks. The 2^8 is, for four possibilities of the first 2^16, who will win, and weather he will win once or twice. And same for the second 2^16, teams from [16,32], who will win and will the winner win again or not.

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

    I tried to reduce the possibilities of backtracking by fixing the sum of eliminated people for every stages. I believe that will be enough to pass the tests in 4 seconds.

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

C is just abbreviation for crying

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

    It's pretty hard for C, lots of combinatorics

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

Solved A , but why does a 2 pointer approach to solving it give TLE ?

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

    No fast IO?

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

    ? Couldn't it be solved in $$$\mathcal O(n)$$$?

    Here's the approach:

    First, obviously, if all the characters in the string are 'a' or 'b', there must be no solution. Otherwise, there must be a position $$$x$$$ that makes $$$a_x\neq a_{x+1}$$$, scan this string directly to find the position $$$x$$$. The answer is $$$x,x+1$$$.

    UPD: AC Submission 128343804

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

      Did this problem really worth time of CM?

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

All those who cheated in this round I hope you all die due to Covid-19 :).Peace!

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

    I guess codeforces has a good system to detect cheaters

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

    Woah bro, chill, there are way worse people who are still alive than those who cheat in online contests.

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

when the editorial will come out?

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

Hi everyone, thanks for the contest I can't seem to figure out what I have done wrong in problem B. If anyone can provide with a test case so I can understand I would greatly appreciate it. Here's my submission: 128271618

Thanks all!

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

    This fails: 1 5 22222

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

      Hey thanks man, just tried it.

      I get that it fails, but I can't yet understand why? Do you happen to know?

      Thank you

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

        This really took lot of time to debug. The reason you are getting wrong answer is that because in your solution same two players are having a match twice. I'll explain your mistake with this test case 1 5 22222

        Explanation: your set initially contains [0,1,2,3,4], after this when you start running the outer loop, these indexes are having a match together 0 4, 1 3, 2 1, 3 2, 4 0

        Now since you had a condition that if a player has already played with the same player than next = -1, so in final iteration your next is -1 , because 0 and 4 have already played. And why this is happening is because you are using a set and then erasing, instead you could just use an array or vector and played adjacent players , and last player with anyone except second last. Hoe you got your mistake and this helped!

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

In problem C, I found the maximum number in the array and if it exists more than once, the answer should be n!. Because they will go to the end of the discussion together. But if there exists only once, We should put at least one maxi-1 in front of this maximum. - If maxi-1 is not in the array we should print 0 - Else we will permutate other numbers:

We will replace other numbers except for maxi and maxi-1 after we have replaced them. Maxi and maxi-1 can be in number_of(maxi-1)! ways. after we have multiplicated them. We will print n! — this.

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

When the editorials will be published?

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

And tasks were pretty good.

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

This is the first contest in which I am able to solve problem B

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

I made submission of Problem D in contest it gives TLE here.

But After contest is over I submit same solution with no change it is working fine here .

Why this is happening?

I wonder if my TLE solution rerun after hacking is over?

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

    The AC solution is way too close to time limit and +/- 50 ms is expected natural behaviour imo which depends on judging machine. So there are lot chances it might still tle after systest

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

I have coded the 1st question(That is equal no of 'a's and 'b's) thinking that even finding "ab" is sufficient as they haven't mentioned that the substring should be largest . can anyone please tell me whether I had taken it right because actually I got wrong for that question.

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

    Yeah, it's right, but make sure you're also searching for "ba".

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

In problen D I tried to calculate count for points between consecutive 2 x-axis-parallel lines, which were grouped by their y-axis-parallel lines. The same works on y-axis. However the answer might always be little different to the Jurys answer. Any situation I missed or over-counted?

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

    128278666

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

      If a point is on the intersection, you should not count it, it adds 0 to the solution. If a point is on an X line, don't count it in solving for Ys, and vice versa.

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

        My sol had taken them into accout, so I think it may be some sneaky bugs.. Anyway, thanks!

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

That Problem C was simply wow! I did not have this much fun facing a problem in many days. Thank you!

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

Solution for problem C: First sort array $$$p$$$. If $$$p[n] > p[n-1]+1$$$ then there is no solution. If $$$p[n] == p[n-1]$$$ then every permutation is a solution. The only case remaining is $$$p[n] = p[n-1] + 1$$$, note that a permutation is a solution in this case, if and only if, $$$n$$$ comes before at least one element equal to $$$p[n-1]$$$. It is easier to count the complement and subtract from $$$n!$$$. So let's count number of permutations where $$$n$$$ comes after every element equal to $$$p[n-1]$$$. Let $$$freq$$$ = count of elements equal to $$$p[n-1]$$$. Suppose element $$$n$$$ is at position $$$i$$$ in permutation. Note that $$$i>freq$$$ is necessary. We must choose $$$freq$$$ positions in prefix $$$[1..i-1]$$$ (binomial coefficient $$$i-1$$$ choose $$$freq$$$) to place all elements equal to $$$p[n-1]$$$ and also permute them between these positions. Remaining elements can go in any remaining position. Thus $$$ans$$$ is equal to the sum for all $$$freq < i < n+1$$$ of $$$i-1$$$ choose $$$freq$$$ multiplied by $$$freq! * (n-freq-1)!$$$. Note we can group all factors $$$freq! * (n-freq-1)!$$$ outside the sum. The sum of $$$i-1$$$ choose $$$freq$$$ for all $$$freq < i < n+1$$$ is equal to $$$n$$$ choose $$$freq+1$$$ (Hockey Stick Formula).

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

    The third case where p[n] = p[n-1] + 1 can be simplified. Let freq = count of all elements = p[n-1]. Then answer simply is (freq*fact[n])/(freq + 1)

    Please correct me if i am wrong ( may be with an example )

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

      You are correct. We can simplify the answer = $$$\frac{n!}{(freq+1)! * (n-freq-1)!}*freq!*(n-freq-1)!$$$ = $$$\frac{n!}{freq+1}$$$ When we subtract this from $$$n!$$$ we get exactly what you wrote!!

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

What is the intended solution for D? Are we supposed to do 6-8 binary searches to find the number of elements in some ranges ?

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

Observations on Problem D: I could not get AC, but I hope the ideas below can help someone. Note that person $$$i$$$ and person $$$j$$$ form an incovenient pair, if and only if, they are on roads of the same type (vertical or horizontal) AND there is a road of the other type between them. Therefore, if person $$$i$$$ stands on both a vertical AND a horizontal road then this person cannot be in an inconvinient pair. We split set of people in $$$2$$$: people in vertical road $$$vert$$$ (sorted by $$$y$$$) and people in horizontal road $$$hori$$$ (sorted by $$$x$$$). We solve for each set separately and sum answers. We consider people in $$$vert$$$ one by one. Suppose we are considering person $$$i$$$. We keep a pointer indicating highest line below $$$i$$$. We also keep a queue of people already considered AND above this line. We keep a frequency array for $$$x$$$ coordinate of people in queue. In each iteration we update line by moving pointer to the right AND pop elements is queue below line. We add $$$queue.size() - freq[i.x]$$$ to answer. Set $$$hori$$$ can be solved in the same way.

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

    You don't need to use queue. You can get an AC by every Time Binary searching as well.

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

      I guess the ideia is the same, both solutions explore Monotonicity. The only difference is in complexity analysis. Using pointers and queue we get $$$O(k*log(k) + k + n + m)$$$ solution because we sort each array but answer each person in amortized $$$O(1)$$$. Using binary search gives $$$O(k*log(k) + k*log(n) + k*log(m) + n + m)$$$ because we sort each array ($$$vert$$$ and $$$hori$$$) and perform binary search for each person in both. Both are ok for time limit.

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

    Finally got Accepted on problem D after reading this comment (plus ~2 hours of coding/debug), thanks a lot.

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

I don't understand why my solution for problem B fails. For 4 2212 (failing 24th test) on codeforces my solution gives
YES
X+==
-X==
==X=
===X
However, on my pc, ideone, and random other compiler my program gives correct output
YES
X+=-
-X=+
==X=
+-=X
What have I done wrong???

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

    Solution for problem B: I will explain a possible construction of solution matrix. If a person wants to not lose any game, then we set all this person's game as DRAW. We store people who want to win at least one game in vector $$$must_win$$$. If $$$must_win.size() > 0$$$ AND $$$must_win.size() < 3$$$ note that solution does not exist. However if $$$must_win.size() > 2$$$ consider array as cyclical and let person $$$must_win[i]$$$ win against person $$$must_win[i+1]$$$. All conditions are satisfied by this construction.

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

      I did exactly that! Except a bit of different way: i marked all 1st type persons as draw between each other, then I gave victory to 2nd type person as soon as possible (and assigning defeat in the correct place, of course), any later game between 2nd types in matrix above the main diagonal is a defeat, below — win. Resulting in a nice right solution. But I dunno why in codeforces last 2nd type person somehow treated as first.

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

        I looked at your code and I think I know what your mistake is. You need to reset your matrix for each test case. A character '+' or '-' from previous test case can interfere with your current test case!!

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

    When you create an array (not a vector) inside your main function, it can be filled with some weird values (its contents are undefined). So, when you try to compare $$$b[j][i]$$$ with some other values, the result of comparison may vary between different systems or even different launches on the same system.

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

Can anybody come up with a case where my 128251114 for B fails?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    ans[twos[twos.size() - 1]][0] = '+';
ans[0][twos[twos.size() - 1]] = '-';

    Should be:

    ans[twos[twos.size() - 1]][twos[0]] = '+';
ans[twos[0]][twos[twos.size() - 1]] = '-';
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 5 12221

    Answer says first row has a minus. However, first item is a '1'. There should be no minus on the first row (1 means zero losses).

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

When would the editorials be live?

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

It was mentioned that this contest is rated...but it is not. I was unrated and still. Please, tell me if there is a problem. Thank you.

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

    You will be rated when the hacking is complete and final standings are published.

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

    You'll be rated once hacking is finished

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

      Thank you. I have earned the rating. However, I want also to ask about my contribution. It is now -1. What does that mean. Thank you.

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

Video Tutorial for Problem C: Jury Meeting

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

Can anyone tell me why I'm getting RUNTIME error on TEST CASE — 3 My_B_Code

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

    try to use char arr[N+1][N+1] instead of string arr[N+1].

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

    change: string arr[n+1] ; to: //string arr[n+1] ; vector<vector> arr(n+1, vector(n+1));

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

      Can you pls explain why so ??

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

        string arr[n+1] is a 1-D array of string, which is like a 2-D array of characters. However, each string's length is not specified. You are accessing arr as if it were 2-D array of characters: arr[i][j]. Not specifying each string's length is the problem. It works ok only when n is small. When n is bigger, it is not ok.

        This code below is similar to the issue, but a bit easier to understand:

                cin >> n;
        string s;
        for (int i=0; i<n; i++)
            cout << s[i];
        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem C be solved in O(1)?

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

    It is obvious that the time complexity of the input is $$$O(n)$$$ .

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

      I meant the solution itself without regard to input, like an $$$O(1)$$$ formula

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

        If you get an algorithm which can solve it in $$$O(1)$$$ time without regard to input , that means you can get the answer without using the input numbers (if you use the input numbers , the time of iteration of the input numbers is greater than $$$O(1)$$$) . So why we input these numbers ?

        Can you get the meanings ?

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

          lol, you're right... Confused C with something else, My bad.

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

        There is an O(1) formula but it happens only after you spend 2N time (2 loops of size n each.) More specifically the answer is

        n! — (n — cnt — 1)! * cnt! * nC(cnt + 1) where cnt is the number of juries with the second largest number of tasks to tell.

        You can refer to my video and the pinned comment for more clarity on the same.

        Video Editorial for C

        Code demonstrating the O(1) idea

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

          that's great, here is the same idea, but more simplified.

          after sorting the array, if last two elements are same, then our answer is n!, means all permutations are nice.

          otherwise we can just subtract number of not nice permutations, which is eventually n! / (cnt+1), where cnt is count of second largest element.

          so our answer becomes n! — n! / (cnt+1).

          Here is my python submission

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

I see a lot of contestants haven't received any penalty for wrong submissions before their first correct one! Can somebody kindly clarify?

MikeMirzayanov adedalic vovuh BledDest Neon

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

    Submissions which fail on the 1st test case don't incur any penalty.

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

      Thanks for your reply! That's advantageous for some but really disadvantageous for many. For example I managed to check if my code passes the sample testcases locally but one of my friend made 3 wrong submissions which didn't pass those. He is ranked better than me.

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

        This is how it is (and should be).
        The first test case acts as an example on which you can test your code (and the compiler of your choice, if there are multiple versions).
        The question of it being an undue advantage to some users just doesn't arise...

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

Why is education more difficult than ordinary div2 ？

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

    If I am not able to solve C in the next round (probable), it will be a hat-trick.

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

Hey, why this contest is not rated, even though it is written it will be rated for the participants with rating lower than 2100. Can please anyone explain this? As I am new to the codeforces and this was my first contest..

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

I guess the open hack is over. But the contest rating has not been updated yet and the editorials as well.

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

    Please be patient, it takes time to update the rating after checking and removing plagiarism

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

fuck the rubbish contest

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

Where's the editorials?

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

    The editorials are somehow a bit slow on "Educational" Rounds . Maybe they want us to think more and be better "Educated" :)

    Don't vote me back or I will be sad :(

    It may be just a joke :)

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

Is everyone else rating changed after the contest? My is still not changed and also contest is not being reflected in my rating graph.

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

    Man, this is not your first educational contest, so I am pretty sure you already know how they work. Is it really fun to ask such questions repeatedly? I am also sure that if you scroll a bit before commenting yourself, you will find a similar question, or two.

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

Update : I just misunderstood the contest.Sorry to everyone. :(

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

My solution for problem C is just a formula- if(count(max-1)!=1){ print(fact[n]); } else{ int cnt=count(max-1); int ans=fact[n]*cnt/(cnt+1); print(ans); }

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

Is this a rated contest?

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

When rank is rated :(( ?? I look forward a better rank through this contest hmu

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

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

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

    The comment every newbie was waiting for lmao.

    I'm not a bad person guys
    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone give some strong test cases for D? I thought of every test case I could and stil couldn't figure out the bug in my code.

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Contrary to all the comments complaining about problem C, I found solving problem C was very enjoyable. I felt it was a good Combinatorics problem, especially for newbies like me.

When I read the statement I instantly realized that the largest element would always be the last to remain, and the same thing for the second largest element. Thus I only need to pay attention to these two. I then tried permutating the 2 elements to see what would happen if the second largest was before the largest, the largest was before the second largest, etc. I later deduced that:

  • If the second largest equals the largest, they will be the last elements in the array together after deletion, so every permutation of that array is a nice permutation.
  • If the second largest is smaller than the largest by 2 or more, we need extra decreases just for the largest element only. Hence, no matter how the array was arranged, the array remained not nice and the answer was 0.
  • Else, the array is nice only if there exists at least one second largest element after the position of the largest element in the array.

The first 2 cases could be solved simply by using $$$std::map$$$ or sorting. I did struggle with the last case at first since I couldn't come up with any formula to count, but then I found out I could solve it by counting the opposite case when the permutation was not nice. Let's call the largest element $$$x$$$ and the second largest one $$$y$$$. To start with, I fixed the position of the $$$x$$$, so it looked something like this:

_ _ _ $$$x$$$ _ _

In order to make the array not nice, in the last 2 slots, we should choose any elements other than $$$y$$$. It means that we need to choose 2 numbers from the set of numbers not including $$$y$$$, or $$$P(k, 2)$$$ with $$$k$$$ is the size of the set of numbers excluding $$$y$$$. We can calculate $$$k$$$ by subtracting the number of elements in the array (which is $$$n$$$) by the number of $$$y$$$ and then subtracting it by $$$1$$$ (the element $$$x$$$ itself). But that's not all, we can continue to permutate the first 3 slots, thus multiplying the answer by $$$3!$$$. So the general formula for $$$x$$$ at any position $$$i$$$ is:

$$$P(k, n - i + 1) * (n - i)!$$$

With $n - i + 1$ is the amount of slots after $$$x$$$ and $$$n - i$$$ is the amount of slots before $$$x$$$. Little note that when $$$n - i + 1$$$ is larger than $$$k$$$, $$$P(k, n - i + 1)$$$ is $$$0$$$ instead. I prebuilt a factorial array so I could calculate $$$(n - i)!$$$ in $$$O(1)$$$, then I used fast exponentation for the modular inverse needed to calculate $$$P(k, n - i + 1)$$$, making each position $$$O(logN)$$$. Finally I iterated every position from 1 to $$$n$$$, so the total complexity is $$$O(N*logN)$$$.

Unluckily I didn't solve this problem quick enough, so I wasn't able to make a submission before the end of the contest. Still feel pretty bad now :(((

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

I have earned the rating. However, I want also to ask about my contribution. It is now -1. What does that mean. Thank you.

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

    Well, that means that you are asking questions that were disliked by the community. The contribution is somehow calculated using the numbers of upvotes and downvotes your comments have.

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

For some reason, it showed plag for a certain question in this contest, they cancelled the contest for me. I'm not that very much concerned about that but are there any further measures?

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

The comment is hidden due to the large number of negative reviews about it, click here to view it

→ Reply