ch_egor's blog

By ch_egor, 5 years ago, translation, In English

Hi everybody,

This Sunday there will be a Moscow programming competition for school students of grades from 6 to 9. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594).

Round will be held at Feb/23/2020 12:05 (Moscow time). You will be given 5 problems and 2 hours to solve them. Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.

Problems are prepared by KiKoS, DebNatkh, grphil, Sehnsucht, voidmax, isaf27 under my supervision.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1:

Scoring distribution: 500 — 1000 — (1000 + 1000) — 2000 — 2500

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

UPD2: Winners!

Div. 2:

  1. SARS-CoV-2
  2. kvk1920
  3. Crazy_Diamond
  4. KwanghyunOn
  5. pufanyi

Div. 1 + Div. 2:

  1. amnesiac_dusk
  2. jiangly
  3. SARS-CoV-2
  4. wiwitrifai
  5. cookiedoth

UPD3: Editorial

Tags 622
  • Vote: I like it
  • +197
  • Vote: I do not like it

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

Nice!The start time of this contest was very friendly to the Chinese. :-)

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

    It's hard to see the round at this time.I hope it's easy.

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

    Why are Chinese always ranting about start time smh ?

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

      Most rounds start at 9-10 pm in China, which is quite late for some people

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

    Yes, it's very friendly to the Indians as well.

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

    Hope every Chinese who will take part in gets good grades

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

I still have questions...

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

    It can be a new contest format or something like global rounds(div.1+div.2)

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

Not colorful testers, but good testers.

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

is this rated contest?

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

I just wanna be specialist again, so I hope it will be easy to solve C at least :)

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

    all the best :)

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

    Keep pushing and Good Luck. You'll be the best. And I wanna becmoe purple too :).

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

      Seems like you have been granted your wish ...

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

        Yep. Becoming a candidate master is the gladdest thing in these days. And good luck && high rated for you in next contest.

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

    How do you think about (1250+750)? Perhaps solution of Problem C will be short but difficult.

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

bonne chance

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

3am for people in North/South/Central America, but I'll surely do a virtual participation when I wake up :). Good luck everyone!

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

It's been a long time for Chinese to participate in a proper time.:-D

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

why do some of the rounds listed have div1 while some don't?

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

    as lots of people can make div.2 problems, but div.1 is something else, much harder and much more important. also if you can make div.1, then you will add two simple problems to it, then it would be div.1 + div.2, but you cant add div.1 E/F that much easily. and its the reason that we dont have too many div.1 only rounds, but we have lots of div.2 + div.1 rounds and more div.2 rounds.

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

One year after Codeforces Round #541?? And the same author?

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

Opencup and round at the same time, not cool man, not cool

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

It's sort of crazy to have two rounds one after another, with an interval of only a couple of hours. I'm so excited! LOL

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

    have the same feeling :), what if we participate in this round as a warm up for the next one?

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

      The second round is, however, time-unfriendly to Chinese participants. Rounds like this one are known as "sudden death round" among Chinese OIers since they're in the midnight. I guess my parents won't let me take part in this round. (sad face

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

        i havent ever seen a cf round that has bad start time for us, love Iran :D, this contest was 12AM, and the normal cf round are about 6PM here

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

          Damned. We almost always have to burn the midnight oil to take a cf round.

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

Let's hope this contest has some actually good problems and not some garbage with cows everywhere.

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

    Disagreed. Cows aren't making problems garbage. I think they are making them easier to understand.

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

Wish to see questions with good learning aspects.

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

Nice! The start time is great!

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

All the best everybody.

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

Lol, score distribution can be really useful for on-site participiantes, You know

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

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

Please let me add 5 points

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

The start time is so nice to Chinese! Hope to be a Master or a Candidate Master!

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

Yeah <3 I am ready and exiting to join the contest !

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

No Legendary registered!!!

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

Thanks for the Round, but I left when I failed to solve pretests for problem-A , and didnt even understood problem-B in first 30 mins :(

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

    That's goodbye rating for you my dear son.

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

      How come...??? Why would I make a submission if I haven't solved for the pretests.

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

        it's too early to give up. your rating doesn't make any sense if you give up like this.

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

Question plz! Why is this contest Div.2 instead of the first five problems of Div.1+Div.2?

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

B is very nice. It should've been C though.

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

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

D̶i̶v̶ ̶2̶ ❌

Div1/1.5 ✔️

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

    haha :D

    I cant solve B for 2 hours ;-; How stupid I am for a math problem

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

      dude i couldnt solve problem B, look at my rating, so that i gave up writing the segment tree on C2 and left the conest :(, the gravity is pulling my rating to newbie

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

        Are you going to drop the rank like I am now ? ;-;

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

        I know B is not always easier than C but I still try all of formula I can think to solve B first and I failed ;-;

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

        New experience for me: Change problem if you think you cant approach furthur although you tried your best for an hour ;-; What a math problem ;-;

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

        I hope we will rank up the next contest :D Good luck <3

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

          thx dude, no hard-feeling, its just a contest which wasnt good for us, maybe next round well get +300 rating(shotor dar khaab binad panbe dane)

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

            Good luck ! Hope I can solve A-B-C and get +50 too

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

              And I solved A-B-C <3, how about you

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

              But I didn't feel too good, since it took me 40 minutes to understand B, and I submited wrong code for C because I was hurry ;-; If I have more time, I hope I can still solve D <3

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

How to solve C2???

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

B is a very nice problem :)

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

    No, it is a horrible index fiddling with absolutly nothing to learn. You might be happy if you solve it, but that does not make it nice.

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

      Not the solution. I meant the idea of the problem is nice. I agree. There is nothing to learn from it.

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

is the solution of C2 segtree+binary search.got tle with that

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

    instead of seg tree do sparse table

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

    For each position i you should calculate the total size of increasing buildings ending at that position.

    Which is equvalent to the Next smaller element problem.

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

    My solution is O(n), you can count all values using stack

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

    Simply segment tree will do

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

      Can you explain the Segment Tree approach for C2?

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

        for each element , we need the closese element on the left of it and on the right of it that has value less than equal to it.So maintain a minimum seg tree and for left and right both elements for each index, do it seperately. For elements in between ,they contribute value equal to element value to its answer. For the rest of elements,answer is already found before. Say for left partition, ansL[i] = ansL[left] + arr[left] + (i-1-left)*arr[i].Same is done for right partition. And then ans[i] = ansL[i] + ansR[i] + arr[i].

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

    No. It is sth like lineral dp + non-decreasing stack. The time complexity is O(n). Plus, I think n=500000 is aimed at preventing some O(nlogn) solution.

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

    I used a different approach.

    I built the cartesian tree of the array in O(n). Basically, each subtree represents a contiguous sub-array. And the root of a subtree is the index of the minimum element of the subarray. It's left and right childs are respectively the sub-array to the left, and to the right of the min.

    Once I have that, I compute the solution for each subtree. Noticing that the buildings size must be constant either on the left subtree, or the right subtree. So I can calculate the answer in O(n) for all subtrees.

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

    You can do binary search on the segtree and use logn time instead of log^2n. You can check my submission https://codeforces.me/contest/1313/submission/71698666

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

    It can be done using a stack. First, we calculate the maximum score we can make from the left side (all buildings in non-decreasing heights) and the right side (all buildings in non -increasing heights). We can do this by maintaining a stack with increasing values. Then taking maximum among all index for left[index-1] + right[index].

    Link

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

how to solve c1 ? i got wrong answer on pretest 3 my code: 71682077

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

    Try putting each element as peak element and the left part forms a increasing segment and the right part a decreasing segment, compute maximum answer for all peaks, and then take the maximum one.

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

How to solve B?

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

    Form min place let $$$lx = min(n-x-1, y - 1), ly = min(n - y - 1, x - 1)$$$. $$$Ans_{mn} = max( y-1-lx, x - 1- ly) + 1$$$. For max place $$$lx = min(n-x, y - 1), ly = min(n - y, x - 1)$$$. $$$Ans_{mx} = max( y-1-lx, x - 1- ly) + lx + ly + 1$$$. Maybe its too complicated, but I came with only this solution

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

      Wow! Thanks.

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

      @kun4ik I did similar to this, can you tell where I went wrong, here is my submission: my submission

      @kun4ik why dont you consider the additional min(n-x-sg1, n-y-sg2) which is there in my code which denotes pairing of those whose performance is worse in both contests? similarly for max?

      Finally found the answer : I didnt check if some terms went negative, so they needed to be 0 capped.

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

      Wow nice <3

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

      It will not work for a==n and b == n

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

How to solve B

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

How do you solve B? It took me over an hour to even come close to a submission. My logic was to casework on N, and the sum of A & B, but I'm pretty sure this isn't correct. This is what I came up with.

if (N == 1) {
    cout << 1 << " " << 1 << endl;
    return;
}    

else if (N == 2) {
    if (min(A, B) == 1 && max(A, B) == 2)   
        cout << 1 << " " << 1 << endl;
    else if (A == 1 && A == B)
        cout << 1 << " " << 1 << endl;
    else
        cout << 2 << " " << 2 << endl;

    return;
}

if (N >= (A + B))
    cout << 1 << " " << (A + B - 1) << endl;
else {
    cout << ((A + B + 1 - N)) << " " << N << endl;
}
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

cool contest but not a good contest problem C idea were really cool but problem B....

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

difficulty balance be like :

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

What is test 8 in C1 be like ?

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

    int overflow

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

    Just a guess, maybe something like this:

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

    I also get WA in test 8.

    I use the maximum number to construct answer, which is totally wrong. The flaw of my solution is that it can't detect the nearby situation and went wrong, like:

    10 5 64 62 62 14 84 59 13 1 15

    64 should be the summit of the answer, but I got 84.

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

anoyne else solved c1 but couldn't A??

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

i got WA on some testcase in problem A.

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

    This is what I was about to go for, then made triplets using sruct lolol

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

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

    Quite tough as a Prob.B :(

    I got stuck with that for 40min, with three Wrong Answers.

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

      lol i definitely don't deserve to be CM

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

        And I also dont deserve to be a specialist.

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

        i have the same feeling dude ;(, after doing nothing on B, there's no reason for me to stay violet

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

Is intended sol for D dp[index][mask] which means we use chosen segments, corresponding to mask, covering point of coordinate index? My code is a mess, I need to transform mask for each transition, there has to be a simpler solution.

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

    How would you transition to a new index?

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

      Find the intervals that cover both points, shift mask the appropriate amount

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

    I pretty much got the same, including the mess and the fail at pretest 2 (and couldn't correct in time)

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

      BTW, I fixed pretest2 WA by fixing test:

      1 3 1

      2 2

      Might help you :)

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

    You can preprocess the intervals in order and map each interval to one of the available bits:

    whichBit.resize(n,-1);
    vector<bool> used(8,false);
    for(int i=0;i<at.size();++i){
    	for(auto interval:out[i])
    		used[whichBit[interval]]=false;
    	for(auto interval:in[i]){
    		int bit=find(used.begin(),used.end(),false)-used.begin();
    		whichBit[interval]=bit;
    		used[bit]=true;
    	}
    }
    

    If you want to set / unset an interval, you should use (1<<whichBit[interval]).

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

Problem B gave me atcoder vibes.

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

Was D something like $$$dp[pos][mask]$$$ denoting max happy children for current position and the mask of the intervals taken?

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

System test will run after 30 minutes? Or right now?

Reason —

"Due to the official competition source codes of other participants will not be available for an hour after the end of the round."

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

Once editorial is published, I'm going to learn much useful stuff

and you know, problem B, I won't let you discourage me!

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

Thanks for this contest. I know my real rating now. I can't solve a Div.2 B for an hour.

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

    Haha :D

    Me too ;-; I thought that B is always easier than C so I tried my best to solve it, and failed ;-;

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

    Actually I spent almost 40 minutes on Problem A after I solved B & C. I did not see the condition that at most one portion is allowed, and was completely stuck.

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

      Oh, and I can only solve the max position of B in first 10 minutes but 1h50 minutes left I cant solve the min position ;-;

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

      Hope you will solve A, B, C in 45 mins in the next contest :D

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

Does anyone have any ideas about div2-D/E?

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

    D, can you explain sample test?

    "In this case all children will be happy except the third." The third kid gets 3 candies, which is odd, so it should be happy. Kids 2 and 4 get two candies, should be unhappy. ???

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

      Only 1-3 and 3-5 are chosen, so 1,2,4,5 will have one candy and thus be happy, while 3 has two candies and is unhappy.

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

I had a hunch that solution of C2 could be related to dilworth theorem?Is it true?

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

For the problem B

The worst position is min(n,x+y-1) Reason: we can always arrange (first k natural)(we have this set 2 times) numbers with minumum sum k+1.

eg. k=5 we have set1 = 1,2,3,4,5 and set2= 1,2,3,4,5 so to get the minumum sum we can arrange 1+5, 2+4, 3+3 (=6)

so if x+y is 6 we can have at most 5 players ahead of Nikolay. in general we can have at most x+y-1 players ahead of Nilolay.

The best position is 1 if x+y<=n by the logic mentioned above

else (when x+y>n) we will try to find the number of pairs of a and b such that a+b>x+y

to do this efficiently lets have a target=min(n+n,x+y+1)

to reach the target set a=n so b=target-a

thus b is the best position achievable.

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

    What's wrong with the following code?

    ll n,x,y; cin >> n >> x >> y;
        ll best,worst;
        if (x+y<=n) cout << 1 << " ";
        else
        {
            best=min(n,1+x+y-n);
            cout << best << " ";
        }
        if (x+y<=2) cout << 1;
        else
        {
            worst=min(n,1+x+y-2);
            cout << worst;
        }
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is copied, not linked.

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

      I am not able to understand why have you written worst = min(n,1+x+y-2);

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

        It just ended up like that while i was coming up with the idea, it's equivalent to x+y-1 anyway so it doesn't really matter, what does matter is why it's giving WA on test 3.

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

          You have done the same thing... what I did.

          Don't know why WA on test3.

          Just a matter of some kind of bad luck :(

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

            Thanks for giving it a thought, i'm really puzzled with this :/

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

              you forgot cout<<endl; lol consider having 5 tests you need to do cout<<endl;

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

                Omfg you are right i can't believe this ever happening

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

Coronavirus wins!!!!

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

how to solve C2 anyone?

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

    linear dp + non-decreasing stack

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

    The final array of the answer can of these 3 forms :

    1). Non-decreasing order
    2). Non-increasing order
    3). Non-decreasing order upto some index i, then non-increasing order from i+1 to n.
    

    Part 1 and 2 is straight forward. For 3rd part we will do some preprocessing. Let's construct two arrays Pre, Post.


    Pre[i] will contain the number of floors we can make if the array is in non-decreasing order starting from 1 to i. Post[i] will contain the number of floors we can make if the array is in non-increasing order starting from i to n.

    let's calculate array Pre.

    Consider 1 based indexing.
    Pre[i] for a particular index will be (i - j) * arr[i] + Pre[j]. Here j is **largest** index of element which is smaller than arr[i] to the left of it. If no such j exists then j = 0. More formally, arr[j] < arr[i] and j < i. Index j can be calculated using stack.
    

    Similarly Post array can be calculated. And the array will be splitted at the point where pre[i] + post[i+1] is maximum. See this for stack method.

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

      that's what i was going to write, but i was about to use segment tree instead of the idea to move over indexes. thx for the solution

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

        I too used Sparse table + binary search for such type of problems until i read the editorial of this problem from Codeforces.

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

      Thank u so much. Nice explanation.

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

Will we get to see testcases used?

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

I couldn't find a O(1) math solution for first integer in B,so i just used binary search to find it :) (nice C btw)

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

    haha, nice bro <3

    ;-; Sad for me trying all the O(1) formula I can think with no result

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

Div.2 $$$\times$$$
Div 1.414 $$$\surd$$$
Difficulty:A<C1<B<C2<<D<E

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

    How can you solve B ?

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

      Well...I found the formula by the samples

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

        ... My code can output as the samples but not for my own created tests ;-; Every formula I try is still fail 1 ~ 3 tests ;-;

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

          That't too bad...

          My formulas are min(max(0,x+y-n)+1,n) and min(x+y-1,n)

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

            How did you arrive at this solution? Can you please provide some mathematical proof

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

          i guess you may solve B/C in next round if you stop wasting your time(like what i do right now) and start upsolving(like what i will do) :)

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

            why down voting, iam just leading him to a better rate

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

Can any one tell the approach of A I just list out cases for it. Any other method?

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

    I used greedy method

        /// Sort a > b > c
        if (a < b) swap(a, b);
        if (a < c) swap(a, c);
        if (b < c) swap(b, c);
     
        int res = 0;
    
        /// Take 1 disk
        if (c) res++, c--;
        if (b) res++, b--;
        if (a) res++, a--;
        /// Take 2 disks
        if (a && b) res++, a--, b--;
        if (a && c) res++, a--, c--;
        if (b && c) res++, b--, c--;
        /// Take 3 disks
        if (a && b && c) res++, a--, b--, c--;
    
        cout << res << endl;
    
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that you should take (a-b) and (a-c) before take (b-c) else you will get WA

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

When will be the rating change?

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

My code for C1 gave an incorrect answer on the 9th pretest. Any idea what's wrong with it? 71676960

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

    Sorry but your code cant be read now :v

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

    probably you should use long long instead of int

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

    I had incorrect answer on 9th pretest cause int overflow

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

      Thanks, it was int overflow for me too.

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

Why fake123_loves_me just disappeared in the standing? He was first, but he disappeared and everyone else's standing get one step upper.

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

    I think because he is unofficial participants. You can see him if you tick on the [] show unofficial on the top right.

    Correct me if I am wrong

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

      Yes, but he did not have star before

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

        But I thought that join with >1900 rating will be unofficial participant ? (he is 2044)

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

B is very hard

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

Can anyone provide the solution for C1? Thanks in advance!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    int n;
    cin>>n;
    
    int a[n];
    for(int &i:a)cin>>i;
    
    int ans[n];
    
                int sum3=0;
                int index=0;
    
                for(int ind=0;ind<n;ind++)
                {
                    int tsum=0;
                    int temp[n];
                    tsum+=a[ind];
                    temp[ind]=a[ind];
    
                    for(int i=ind-1;i>=0;i--)
                    {
                        temp[i]=min(temp[i+1],a[i]);
                        tsum+=min(temp[i+1],a[i]);
                    }
                    for(int i=ind+1;i<n;i++)
                    {
                        temp[i]=min(temp[i-1],a[i]);
                        tsum+=min(temp[i-1],a[i]);
                    }
    
                    if(tsum>sum3)
                    {
                        index=ind;
                        sum3=tsum;
                    }
                    //cout<<tsum<<endl;
    
    
                }
              //  cout<<index<<endl;
    
                  ans[index]=a[index];
                    for(int i=index-1;i>=0;i--)
                {
                    ans[i]=min(ans[i+1],a[i]);
    
                }
                for(int i=index+1;i<n;i++)
                {
                    ans[i]=min(ans[i-1],a[i]);
    
                }
                for(int i:ans)cout<<i<<" ";
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sharing code is not appreciated here. Better share links if you really have to; even better share your approach!

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

I think B may change position with C1

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

    How can you solve B ? That is nice <3

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

      Suppose in the first round we took x-th place and in the second round — y-th place

      First we consider the max: We can let the person who took (x-1)-th place in the first round took the (y+1)-th place in the second round. Then the total score of this participant is (x+y) which can contribute to the answer .Similarly, with this strategy we can know that the ans is min(n,x-1+y-1+1)

      Then we consider the min: We can let the person who took (x-1)-th place in the first round took the (y+1+1)-th place in the second round. At this moment , the total score of this participant is (x+y+1) which is strictly larger than we. By doing this,now1=max(0,n-(y+1)) of the first (x-1) people's final scores are strictly larger than B.The same is true for the dimension y and the number is now2. So the number of people who may not strictly larger than we is (a-1-now1+b-1-now2+1(myself)), but this is not the optimal answer, We can make pair X and Y smaller than me in pairs and make the ans to {a-1-now1+b-1-now2-min(a-1-now1,b-1-now2)+1}

      My Submission : 71671193

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

        {a-1-now1+b-1-now2-min(a-1-now1,b-1-now2)+1}

        what is "a b" means ? please

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

      worst pos is min(n, x + y — 1) best pos is (x + y >= n ? min(n, x + y — n + 1) : 1)

      proof is left as an exercise to the reader

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

Can problem E be solved using suffix array?

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

Without samples, I couldn't solve B

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

    Typical maths problem XD

    I solve it in 1hr40min QAQ

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

Finally Master. Hope I can stay a bit longer.

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

I cant see the code of others (it is almost 2hrs)

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

I THINK I VE COME UP WITH THE ULTIMATE GENIUS 35182798 IQ THINKING PROCESS FOR SOLVING B.

First you reduce the problem to a matching problem 71692875. I copypasted preflow pushes but it doesnt really matter!!! You could use ford-fulkerson or any other algorithm.

Then you notice a pattern and write this 71692875. Then you submit it and do not lose 5512571829 rating.

I think I am a fucking genius right guys?

Proof by AC is the way to go smart people told me this!!

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

    actually i wonder how many of those who got an ac actually know why their solution works

    i dont

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

      You didnt even submit your super solution. In both of ur submission you got AC using the same 1 line of code.

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

        okay man thanks for telling me something i didn't know

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

My code for C2 (here got the wrong answer. But when I changed at line 118 from '<' to "<=", it got accepted. I tried that to handle the case of all zeros (even though it is outside the constraints). Is their test case 20 outside of constraints or am I missing something?

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

Does anyone have the similar situation?

The System says I may write a code very similar to other's.

But this is problem A.

I think it's because the code is too simple so that it's easy to be very similar.

What should I do?

My Submission:71656145

What the system has sent to me:

Attention!

Your solution 71656145 for the problem 1313A significantly coincides with solutions Acranker/71656145, hnust_zhouzisheng/71662017. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

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

Why do i keep getting runtime error on test 5 in D? Here's the link to my code

EDIT: Got the mistake

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

When will the system tests be visible, I want to know why my C2 failed!!!!

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

    maybe i can help you with the problem, u can pm me if u wish

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

tfw you're purple but can't solve div2 B...

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

When will submission be visible? It's nearly 3hrs instead of so-called "1hr"! And I'm anxious to see why my C2 failed!