ch_egor's blog

By ch_egor, 5 months 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

»
5 months 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 months 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 months ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Why are Chinese always ranting about start time smh ?

    • »
      »
      »
      5 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    Hope every Chinese who will take part in gets good grades

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

I still have questions...

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

    ///786/// maybe it will be the usual Div 2 or, Div 3

  • »
    »
    5 months 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 months ago, # |
  Vote: I like it -42 Vote: I do not like it

Not colorful testers, but good testers.

»
5 months ago, # |
  Vote: I like it -20 Vote: I do not like it

///786///

hope to see another good round

all the best to all participants :D

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

is this rated contest?

»
5 months 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 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    all the best :)

  • »
    »
    5 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seems like you have been granted your wish ...

      • »
        »
        »
        »
        5 months 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 months 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bonne chance

»
5 months 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 months 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 months 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 months 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Finally, a reasonable time for us EST CFers!

»
5 months 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 months 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 months 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 months 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 months 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 months 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 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too

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

    "actually good problems and not some garbage with cows everywhere"

    try creating one on your own, get a pen and a notebook and only look for the information that is actually needed

  • »
    »
    5 months 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 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Wish to see questions with good learning aspects.

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

Nice! The start time is great!

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

All the best everybody.

»
5 months 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 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

Please let me add 5 points

»
5 months 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

No Legendary registered!!!

»
5 months 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 months ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    That's goodbye rating for you my dear son.

    • »
      »
      »
      5 months 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 months 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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hmmm, i guess old age has gotten the better of me.

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

It's so demotivating when I give up the contest so early... :'(

»
5 months 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 months ago, # |
  Vote: I like it -34 Vote: I do not like it

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

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

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

D̶i̶v̶ ̶2̶ ❌

Div1/1.5 ✔️

  • »
    »
    5 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nah me too

    • »
      »
      »
      5 months 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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months 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 months 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 months 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 months 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 months 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 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              5 months 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 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C2???

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

B is a very nice problem :)

  • »
    »
    5 months 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 months 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 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    instead of seg tree do sparse table

  • »
    »
    5 months 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 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Simply segment tree will do

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

      Can you explain the Segment Tree approach for C2?

      • »
        »
        »
        »
        5 months 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 months 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 months 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 months 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.com/contest/1313/submission/71698666

  • »
    »
    5 months 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 months 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 months 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

  • »
    »
    5 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow! Thanks.

    • »
      »
      »
      5 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow nice <3

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

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

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

How to solve B

»
5 months 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 months 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 months ago, # |
  Vote: I like it +33 Vote: I do not like it

difficulty balance be like :

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

What is test 8 in C1 be like ?

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

    int overflow

  • »
    »
    5 months 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 months 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anoyne else solved c1 but couldn't A??

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

i got WA on some testcase in problem A.

  • »
    »
    5 months 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 months ago, # |
Rev. 3   Vote: I like it +113 Vote: I do not like it

  • »
    »
    5 months 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 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      lol i definitely don't deserve to be CM

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

        And I also dont deserve to be a specialist.

      • »
        »
        »
        »
        5 months 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 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would you transition to a new index?

    • »
      »
      »
      5 months 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 months 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 months 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 months 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 months ago, # |
  Vote: I like it +40 Vote: I do not like it

Problem B gave me atcoder vibes.

»
5 months 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 months 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 months 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 months 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 months 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 months 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 months 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 months 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 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    5 months 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 months 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 months 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 months 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 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is copied, not linked.

    • »
      »
      »
      5 months 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 months 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 months 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 months 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 months 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 months ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

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

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

Coronavirus wins!!!!

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

how to solve C2 anyone?

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

    linear dp + non-decreasing stack

  • »
    »
    5 months 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 months 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 months 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 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank u so much. Nice explanation.

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

Will we get to see testcases used?

»
5 months 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 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you message your code erkam plz the submission are not available yet.

»
5 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can you solve B ?

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

      Well...I found the formula by the samples

      • »
        »
        »
        »
        5 months 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 months 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 months 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 months 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 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

»
5 months 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 months 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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I have also used the same approach.

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

      I even did same ,why you arrange them like? 1 . if (a && b) res++, a--, b--; 2. if (a && c) res++, a--, c--; 3. if (b && c) res++, b--, c--;

      it might be 1. then 2. then 3. or 1. then 3. then 2. or............so on.

      3! arrangements

      and where you see it is greedy?????

  • »
    »
    5 months 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 months ago, # |
  Vote: I like it +6 Vote: I do not like it

When will be the rating change?

»
5 months 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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry but your code cant be read now :v

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

    probably you should use long long instead of int

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

    I had incorrect answer on 9th pretest cause int overflow

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

      Thanks, it was int overflow for me too.

»
5 months 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 months 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 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Yes, but he did not have star before

      • »
        »
        »
        »
        5 months 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 months ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          I just think

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

          In fact, anyone rated below 2,100 will be rated on div.2 only round.

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

B is very hard

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

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

  • »
    »
    5 months 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 months 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 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I think B may change position with C1

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

    How can you solve B ? That is nice <3

    • »
      »
      »
      5 months 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 months 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 months 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem E be solved using suffix array?

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

Without samples, I couldn't solve B

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

    Typical maths problem XD

    I solve it in 1hr40min QAQ

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

Finally Master. Hope I can stay a bit longer.

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

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

»
5 months 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 months 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 months 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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
5 months 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 months 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.com/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 months 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 months 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 months 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 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

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

When can I watch other's code?