Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Автор awoo, история, 2 недели назад, По-русски

Привет, Codeforces!

В 08.09.2021 17:35 (Московское время) состоится Educational Codeforces Round 113 (Rated for Div. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

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

Место Участник Задач решено Штраф
1 Geothermal 6 183
2 qpEDop_MuXauJloBu4 6 216
3 hanbyeol_ 6 219
4 tute7627 6 221
5 fastmath 6 287

Было сделано 69 успешных и 304 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
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: Разбор опубликован

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

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

Hoping for a great contest!

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

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

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

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

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

      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.

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

        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.

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

          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.

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

MF

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

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

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

what are the score distribution for the individual problems ?? Btw, looking forward to a great contest ahead!!!

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

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

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

Looking forward to losing my newbie virginity to this contest !

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

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!

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

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

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

This will definitely be another brilliant contest!

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

Really looking forward to this round. To improve my rating. It sucks.

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

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

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

Another brilliant round, i hope this round improve my rating. Upvote for your kind wishes.

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

good luck!

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

Always like Educational Rounds :D

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

To be educated in educational round..

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

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

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

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.

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

can you move the contest Educational Codeforces Round 113 [Rated for Div. 2] can you go up 1 hour?

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

shinzou WO Sasageyo...!!

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

    What is freedom?

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

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

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

      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.

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

        factorial and mod disasterrrrrr

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

          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.

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

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

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

Div-2 C :

bool unsolved = true;
while(unsolved)
{
crying due to mod&factorial = true;
if(crying due to mod&factorial)
unsolved = true;
}
»
13 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

back to newbie

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

the first testcase in C makes the solution obvious

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

How to solve C?

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

    the only wrong case might occur iff all the second maximum numbers are behind the maximum number, if there are two maximum numbers then answers is fact[n]. To calculate we can note that the first thing is equal to the non integral solutions to a number. Also the numbers themselves are different so you multiply the factorial of the second maximum also. Rest numbers can be permutated also so we need to calculate the number of permutations with common objects and multiply that also.

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

    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.

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

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

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

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

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

      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?

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

Problems were hard.

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

How to solve D

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

    I missed the registration, but my guess is

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

    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://codeforces.com/contest/1569/submission/128325617

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

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?

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

A very heavy meme :

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

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

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

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

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.

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

Solved C literally a minute after the contest ended damn

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

Could anyone give me a hint for problem B ?

I thought about using backtracking but could not implement it.

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

    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

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

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

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://codeforces.com/contest/1569/submission/128287672

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

    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://codeforces.com/contest/1569/submission/128280479

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

      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.

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

        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.

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

          Thanks for the explanation it helps a lot!

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

            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

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

    Well, cases to consider, Suppose maximum number present in array is X and second maximum is Y. i) When are we not going to have any nice permutataion? The case when X-Y>=2. Otherwise, ii) If there are two or more occurrences of X, we can always permute the whole array in any way possible and get a nice permutataion. So, that would be n! ways. or There is just one occurrence of X and some occurrence of Y. In that case, We can try to solve it by finding count of all permutation — permutataion when X comes after all occurences of Y.

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

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

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

Waiting for the solutions....

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

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.

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

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

»
13 дней назад, # |
Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

As a contestant solved one problem give me contributions (◕‿◕)

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

How to do E?

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

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

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

      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

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

        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.

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

          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.

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

    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.

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

C is just abbreviation for crying

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

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

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

    No fast IO?

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

    ? 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

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

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

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

when the editorial will come out?

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

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!

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

    This fails: 1 5 22222

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

      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

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

        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!

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

          Hey! Thanks for putting in the time and effort! Really helped me understand my mistake :) My greedy approach does in fact not work and now I understand why

          Thanks once again, I would uovote you more if I could

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

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.

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

All those who cheated in this round i hope you loose your genitals. Peace :) !

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

When the editorials will be published?

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

And tasks were pretty good.

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

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

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

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?

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

    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

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

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.

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

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?

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

      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.

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

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

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

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

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

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

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

    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 )

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

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

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

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 ?

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

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.

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

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

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

      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.

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

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

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

problems were nice.

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

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

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

    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.

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

      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.

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

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

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

    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.

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

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

  • »
    »
    13 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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]] = '-';
    
  • »
    »
    13 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

When would the editorials be live?

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

tutorial??

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

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.

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

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

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

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

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

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

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

      Can you pls explain why so ??

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

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

has the contest been called unrated ?

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

Can problem C be solved in O(1)?

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

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

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

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

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

        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 ?

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

        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

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

          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

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

I see that many of the contestants who have a few wrong submissions before their first correct one have got no penalty. Can someone kindly clarify?

»
13 дней назад, # |
Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

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

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

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

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

      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.

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

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

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

Can anyone please explain why in Problem D sample case 2 does not count 4 and 5 points as inconvenient? Is there anything I am missing here?

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

Why is education more difficult than ordinary div2 ?

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

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

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

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

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

fuck the rubbish contest

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

how to solve C?

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

Where's the editorials?

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

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

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

My rating is below 2100. But my rating hasn't increased or decreased yet.. Can anyone tell me why?

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

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

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

    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.

»
12 дней назад, # |
Rev. 4   Проголосовать: нравится -13 Проголосовать: не нравится

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

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

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); }

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

Can someone explain me the idea behind B?

  • »
    »
    12 дней назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    • First i filled the matrix with '.' , then , if the string has '1' at position i , then the best case for us would be that , he doesn't wanna lose , so we draw all the matches in row i , ie. fill the row i with '=' and fill i = j with 'X'.
    • Now , iterating through the matrix , we check if there are some dots left , if we find dot and the corresponding (corresponding for i,j is j,i) is also filled with'.', then we put a '+' and fill corresponding with '-'. The row i had to win atleast 1 , which he did , so put all the '.' in the current row to '-' and the corresponding to those are replaced by '+'.
    • After all the iterations for checking the case of -1 , what i did was check if the string given in input had 2 but if the row did not have any '+' , then answer is NO, else print the matrix formed.
    • No condition can also be checked using a casework

    Submission link : https://codeforces.com/contest/1569/submission/128246925

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

Is this a rated contest?

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

Why hasn't the result been out yet?

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
not lighthearted meme
»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

For Problem D can someone please tell me how to find points like (2 and 7) in the second test case since I need to subtract these points from my final answer? i.e points which have either same x co-ordinate or y co-ordinate and there is no line which is intersecting between the points.

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

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

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

I got WA on problem B just to realized after the contest that I forgot to memset my array xD. What a pity. That being said the contest is super awesome and suitable for newbies like me! Thanks a lot!

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

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.

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

yamete kudasai

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

Thank you because of this helpful contest!

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

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

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

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

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

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

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

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

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

    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.

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

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?

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

22k registered but only 11k submitted, this is bad :(

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

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