Endagorion's blog

By Endagorion, history, 4 months ago, In English

Hi!

On Jun/18/2020 17:45 (Moscow time) we will host Codeforces Global Round 8.

It is the second round of a 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

  • 30 best participants get a t-shirt.
  • 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2020:

  • In each round top-100 participants get points according to the table.
  • The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
  • The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2020 supported the global rounds initiative!

Problems for this round are set by me. Thanks a lot to the coordinator 300iq and testers thenymphsofdelphi, Lewin, Golovanov399, Osama_Alkhodairy, gamegame, dorijanlendvaj, HenriqueBrito, kocko, ruban, Origenes, Ilya-bar, rahulkhairwar. Their feedback was a huge help and affected the problemset greatly.

The round will have eight problems and will last 150 minutes.

Scoring distribution: 500 — 1000 — 1500 — 1750 — 2500 — 3000 — 3500 — 3000+1500

Good luck, and see you on the scoreboard!

UPD: the round has concluded, congratulations to the winners:

  1. ecnerwala
  2. tourist
  3. Marcin_smu
  4. Petr
  5. Radewoosh
  6. Um_nik
  7. maroonrk
  8. eatmore
  9. snuke
  10. KAN

Check current Codeforces Global series standings here (courtesy of aropan).

You can find the editorial here.

Stay tuned for prizes announcement!

Announcement of Codeforces Global Round 8
 
 
 
 
  • Vote: I like it
  • +1315
  • Vote: I do not like it

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

Surprising that even legendary grand masters have coordinators.

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

Aiming for T-shirt!

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

late announcement :p

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

Combined Round after a long time !

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

Deliveries in corona times T_T

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

Can we expect more than 20k participants in this round.

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

Endagorion... It sounds like a good round

»
4 months ago, # |
  Vote: I like it -157 Vote: I do not like it

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

Will we see a MiFaFaOvO vs tourist?

»
4 months ago, # |
Rev. 2   Vote: I like it +57 Vote: I do not like it
»
4 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

NICE Round

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

    Hey everyone, those who are turely annoyed with her and want to choose a cool institution please set your institution as of mine. Its a request

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

      I'm annoyed with her, but I don't agree with your opinion too. I don't want to be in any Anti-Fanclub, okay? And also, don't use your second account to post bad comments. You registered 6 weeks ago and didn't participate in any contests, but your contribution is below -70.

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

      Is it like I hate Rachel club ?? Only this time _chandler_ is a part of it instead of Ross xD.

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

A newbie like me should participate in this? though it is rated for all and the level of questions will be hard

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

    Don't be afraid because you are a newbie. You have to participate in many rounds, and then you would be able to increase both your rating and skills.

»
4 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Hello guys.I have no idea about calculating contribution.I commented in the last div3 contest announcement then my contribution began to low.Before this i thought contribution is calculated only for blog.Please anyone explain about calculating contribution..Thanks in advance.

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

    Hey bro ,I don't know much about contribution bur make sure that your comment make a positive impact to the community and don't post negative comments. I think it will increase your contribution points. Hope it helps. PS: I earned +2 yesterday

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

    rule but i think skills is more important than your contributions..

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

Combined Round! Hope it will be fun.

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

tourist and MiFaFaOvO both have registered for this round! It will be exciting to see.

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

    Game of thrones... XD

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

      Indeed! GOT without any bloodshed! :p

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

    Don't forget about Um_nik. He will also join the party.

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

    7 among top 8 are registered for this contest and left one is coordinator of this round.

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

With how many problems?

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

No offense to anyone

»
4 months ago, # |
Rev. 2   Vote: I like it -60 Vote: I do not like it

would it be rated? EDIT: sry missed it in the announcement.

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

A codeforces round from Endagorion after a long time. Eagerly waiting...XD

»
4 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Nice round after a long time..

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

I hope to see myself as a pupil in today's contest. Good luck for everyone.

»
4 months ago, # |
  Vote: I like it -63 Vote: I do not like it

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

Is the rating calculated differently for these rounds? For example if I get rank 500 in a global round and in a div2 round, would my delta be higher for global round since div1 participants are also considered in official standings? Or will it be the same

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

Expecting a very good problemset .

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

This comment section is shit.

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

    Agreed, the memes turned from actually funny into shit that takes up space.

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

    MikeMirzayanov should actually ban photo comments to prevent this.

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

    What do you expect it to be before the contest started?

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

    Welcome to memeforces!

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it -51 Vote: I do not like it

    The only way to avoid people posting memes in comment section is to downvote them. So , its a request to all if anyone finds any meme just downvote that(If you found meme funny then laugh and downvote), but you have to downvote,that's the only way because mostly people post memes to increase contribution

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

    You got many upvotes (including mine). Because you are Errichto.

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

    Great performance Errichto, I'm glad to see ur level hasn't dropped down even after dedicating so much time to YT.

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

For the top-100 participants, how is the points calculated? I mean the sequence {$$$1000, 706,575,497,443,403,371 ...$$$} apparently makes no sense. Or does it?

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

    It actually does!! Being a competitive try to find what are the cons of making this sequence in decreasing AP :)

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

    $$$\left \lfloor{\frac{1000}{\sqrt{rank}}-rank+1}\right \rfloor$$$

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

      This function seems pretty interesting, it is ranged between 1000-1 for rank 1-100, also the decay seems fair. Is it the only standard function used for such scoring or there exists more ?

      Thanks

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

        If you want fair decay..Why not use...

        $$$ points = \lceil{-\frac{ 111 * rank }{ 11 } + \frac{ 11111 }{ 11 }} \rceil$$$

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

          Is it always an integer ? I can't see a clear cut proof.

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

          Because the difference between 1st and 2nd place should be much larger than the difference between the 99th and 100th place.

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

            Yeah, that makes much more sense.

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

waiting for this contest after global round 7!

and hoping to get t-shirt!!! good luck to all others!!

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

    Waiting for this contest before global round 9!

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

*_*

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

Hey, I am somewhat new in Codeforces. I want to ask that ofc my standing will be lower comparable to other Div. 2 rounds, so will it affect my ratings in a negative or positive way?

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

    your rating is based on how you do compared to other participants not your rank. You can read more about it here link.

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

Codeforces and Polygon may be temporarily unavailable 2 hours starting from July 18, 05:00 (UTC) due to infrastructure updates.

I think it should be June 18 ? MikeMirzayanov

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

    They will be upgrading Russian and English versions separately one month apart.

»
4 months ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

Deleted

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

    Plot twist : round will be hosted in ACM-ICPC style

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

can someone post previous contest Links by Endagorion.

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

i hope "pretest passed" and "accepted" will not follow the rule of social distancing

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

    Actually this was really fun. Surprised that you got downvotes.

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

The tourist Is Coming

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

When score distribution will be announced?

»
4 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Is there any chance that the contest will be canceled?

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Please check previous comments before commenting something, don't post same repetitive comments and memes in the same blog.
Remember, it's Codeforces, so don't make it memeforces or spamforces :(

»
4 months ago, # |
Rev. 4   Vote: I like it -13 Vote: I do not like it

Wow! The score distribution for the last problem is almost equal to the score distribution for the first 4 problems!

Good luck everyone!!

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

Scoring distribution: 500 — 1000 — 1500 — 1750 — 2500 — 3000 — 3500 — 3000+1500. Actually, I am not clear about "3000+1500" part.

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

    May be at that problem there will be a sub-problem also. Like B1, B2 type.

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

      I don't think so, otherwise problem count must have been 9. There might be possibility of subtask1 & subtask2 with partial marking.

»
4 months ago, # |
  Vote: I like it -63 Vote: I do not like it

MiFaFaOvO vs tourist ... who will win today ??

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

delayed 10 m !

»
4 months ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

More 10 minitues!!

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

Last five minutes delays are the worst thing ever.

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

delayed

Oh boy the queue will troll us again huh?

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

Let's hope that this delay is not a sign of long queues

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

10 min delay?

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

Seriously why does Codeforces like to delay contests in the last minutes? It's really ruining the momentum and the "zone" :(

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

    So that we can have a short contest of commenting about the delay.

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

    They don't like to delay, there must be some problem. A delay is much better than an unrated round.

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

    It's called ritual.

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

    I almost always barely make it on time because I underestimate how much time is left before a contest starts. Then the delay is announced and I get time to open my IDE.

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

postponed for 10 mins?

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

Round delayed for 10 minutes.

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

The delay is like the apocalypse trompettes before a round.

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

I got electricity cut and contest is delayed. Hope electricity returns in 10 minutes....

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

Hope queue don't play with us.

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

No queueforces please :(

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

    Really, is it common to have delays like this?

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

I hope the round doesn't get cancelled. Fingers crossed XD

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

If it gets delayed by 10 more mins, I'm gonna have my dinner.

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

Wouldn't it be amazing to know what exactly happens when codeforces is working on it's infrastructure? Anyone? Just curious :)

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

I hope this round will go without any problem and no more delay

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

Comment section nowadays

Apparently this post is included :(

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

Codeforces waiting for 20k registrations? :P

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

love to see Radewoosh in top rank

»
4 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Too Difficult.

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

    The second one is kinda tricky

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

      yea, I'm getting rekt at pretest 3. C was easy tho. Sometimes I don't understand question ordering.

»
4 months ago, # |
  Vote: I like it -17 Vote: I do not like it

What the hell is this 2nd problem?

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

    Same thing :/ but I figured it out 10 minutes before the end :)

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

That gap between D and E. Oooooooof.

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

Solved 4 Problems and left the contest.

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

Speed-forces for non-red coders. >_<

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

What a mess I've done? Hope others did well

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

Nice problems, but it is so demotivating when you just sit 2 hours straight not even coding something...

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

    really.... i think my solution of E is correct... but wrong answer..

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

For example u have:

7
1 2 3 4 5 6 7

Let’s write it in bits:

0 0 1 														
0 1 0
0 1 1
1 0 0  
1 0 1
1 1 0
1 1 1

turn on gravity for let bits fall down and stack at each other, now u have:

0 0 0
0 0 0
0 0 0
1 1 1
1 1 1
1 1 1
1 1 1

Now u just need to sum squares of this numbers

Python code:

am = int(input())
arr = list(map(int,input().split()))
bits = [0]*21
for i in range(am):
    n = list(map(int, reversed(list(bin(arr[i]))[2:])))
    for i in range(len(n)):
        bits[i]+=n[i]

b = max(bits)
s = 0
for i in range(b):
    n = 0
    for g in range(21):
        if bits[g]:
            n+=2**g
            bits[g]-=1
    s+=n**2
print(s)
»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I made a video explaining problem D because I really liked the problem — https://www.youtube.com/watch?v=oHgcHjk2fIM

There are many people with these videos, so let me know if it's worth doing more, thanks!

(Well, I liked problem E too, but I didn't solve it)

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

    Understood everything..... Make Video editorials for every Div2.D&E

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

By any chance, were the rooms decided based on rating? Mine only had me as >= CM and 2 blues rest all cyan or below.

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

Why limit in E is 4/7, not 4/6? ;.;

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

    If 4/6 this is Problem A/B :P

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

    How do u do it in 4/6?

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

      Iterate from 1 to n. If the current node is not deleted then delete the adjacent nodes of the current node and keep the current node. It will be true because we are always deleting maximum of 2 nodes but keeping 1 node

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

      Let's color the graph in 3 colors such that vertices of the same color don't have edges between them. You can do this from right to left. Then delete 2 smallest sets.

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

These problems are good. Great round! Took me a long while to find the idea for C. I tried so many things lol. Can anyone share ideas for D?

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

    For D you can just count number of bits that are 1 for every position and then construct from them biggest numbers.

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

What was the catch in Problem B?Can anybody explain?

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

    2 * 2 * 2 * 2 * 2.... generates longer subsequences than 1*1*1.. *n for a smaller cost, so greedy check 2*2*2*2 and then 3*3*3... (keep on incrementing so 4*4*4... and 5*5*5... etc) until you're ready (you can mix different numbers suchas 2 * 2 *... *3 *3 *3

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

How to solve E?

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

    Judging from ecnerwala's solution, it is just greedy. And that's where I first realized that "landing spots on the mountain numbered from 1 to n from the top to the foot of the mountain" :facepalm:

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

      It's a construction problem with large constraints, of course it's greedy. That doesn't help with finding the correct solution.

»
4 months ago, # |
  Vote: I like it -31 Vote: I do not like it

KSM problem C

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

First time participated in a "global contest", Wow it was amazing, thanks to the organizers

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

How to solve D? Whats so easy about D?

My approach which is wrong was to store numbers in min_heap, extract 2 and operate on them, store the greater one back in heap. This worked on so many handwritten cases but not pretest 4 :(

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

    Just count the frequencies of bits, then keep on generating numbers using them till they are not finished greedily!

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

      Oh my god now this looks obviously correct, why I didn't see this :O

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

        I also feel the same way.I was roaming here and there with approaches like set and heaps but after seeing this I feel like how can I miss it:(

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

    Short version — For each operation, you are just swapping the bits in the two numbers. In the end, sum of the count of bits in each position will be the same. Hence just do a column sort (assuming you have a 2D array of numbers represented in binary form)

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

    count the number of bit, For Loop(n) , Loop(bit) if count of bit is more than zero, you add the bit value in tmp, and ans += tmp*tmp

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

    try this 2 3 5 ans is 58

»
4 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Please tell any hack case.

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

You just need to learn concept of gravity to solve Problem D

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

How to solve E? someone help please

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

I solved D in 8 minutes and B in two hours, I was trying to increase subsequences using suffix earlier on, but prefix gave a better answer. Really upset! But a really nice round overall!

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

Lol, didn't expect C to be a pattern based problem. Just print the coordinates and thats it.

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

was b something about powers of 2 and 3?

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

    We have 10 factors so I did it by making them as close to each other as possible.

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

    Don't know how to upload images. Sorry about that. ^^ This is what I got for case 1 in problem C.

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

      Its wrong because 4 gray box have 3 gray neighbours each

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

        yah its wrong just realized.. how to solve it? help me.

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

          Actually during contest I was making for $$$n=2$$$ and it was not working placing them side by side. So I tried putting them diagonally and it worked. After some time I realised it worked. Refer this I exactly did like this : link

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

How to solve C

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

    Find a correct answer for the case n = 1. For the rest, build the staircase.

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

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

    You can fill n cells in diagonal order and then make sure that all their neighbouring cells are also grey.And when will you draw this you will find that to make no. of neighbours even you need to fill two cells more diagonally one at top and other at bottom.Hope this helps.

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

    Just look at this

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

    It was basically a problem of constructive algorithm. The major sticking point was to decide which n should have all neighbors grey. I chose them as (1,1), (2,2), (3,3) and so on till (n,n). Now chose all 4 neighbors for them. Some of them might repeat. Also chose 0.0 and (n+1,n+1) because neighbors of first and last point will not have even neighbors

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

    If you take pleasure in blowing 1.5 hours building fancy patterns, you can do it like below (for n = 4).

    (After the contest, I saw the other solutions and then smacked myself)

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

Was that any problem ordering C->D->B. B was really hard.

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I'm noob so asking, Is B supposed to be easier than C?

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

    Yes, A<B<C.... in order of increasing difficulty.

»
4 months ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

deleted

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

Very very interesting problems, thanks!

»
4 months ago, # |
  Vote: I like it -114 Vote: I do not like it

Worst contest i have ever seen!..

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

    every time there's this one guy saying: "Worst contest"

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

      I think he is justified because gap between D and E difficulty wise was large

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

        well yes and I too would've liked to get an easier problem E, but at least it was reflected in the scoring distribution — we knew beforehand that E would be hard!

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

    looks like someone under-performed

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

How to solve B?

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

    let number of first character of "codeforces" n(1), second character n(2) ans so on. Then, just check for the combination of these n(i) with greedy method for which it reaches k at the lowest cost.

    Meaning, suppose for k = 4, firstly, the string is "codeforces" which is k = 1 and every n(i) is 1. then, check if it reaches k with 2 first characters, which is "ccodeforces". (combination is 2*1*1*1*1*1*1*1*1*1 = 2) If not, check again with 2 second characters, which is "ccoodeforces". (combination is 2*2*1*1*1*1*1*1*1*1 = 4) which reaches k and is the answer.

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

      Thanks. I don't understand what happens when k is odd, say k = 3. Are you saying that we check for all from 1*1*1*1*1*1*1*1*1*1 to something*something..?

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

        Yes, you can just increment the smallest value of the 10 (if multiple are smallest chose any of them) until they multiply together to be larger than the target.

        In theory you can optimise by finding the largest x where x^10 is less than the target and starting from there, but it's not needed.

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

        in the statement, it says at least k in minimum length of string. So, if you try out different cases of odd k, you'll see it is all the same as the even. Because the string length remains the same even if the combination exceeds k. Just write down 2 cases for odd, you'll understand. As for your second confusion, not something*something.. Just go by incrementing number of characters one by one from 1*1*1... (like the example shown in the parent comment) and check if it crosses k.

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

How to solve F? I think the maximum of $$$R(n)$$$ is $$$\lfloor \frac{n}{2} \rfloor - 1$$$, am I right?

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

Do you think believing is worth more than proving? Don't do this in a speed-solving contests...

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

    I kind of see your point, and that wasn't the intent. Apart from E, do you think other problems suffered from this?

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +76 Vote: I do not like it

      Thanks for your comment. I was not particularly suffered from other problems than E because of the believe-vs-proof issue, but the overall experience wasn't good.

      I think B, D, and F have a similar kind of issue to some extent. For B and D the proof is rather easy (?) but the "targeted" contestants for them could have felt upset as I have for E.

      F is more approachable by experiments (and indeed I did), which is good. But I submitted without proving no better solution exists. Who proved it would have spent non-negligible amount of time, which could lead to a terrible performance for this round.

      The ideas for E and F themselves were pretty nice! (at least for Mathematical Olympiads)

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

        Thanks a lot for your feedback! I have a pet peeve for open-ended problems where the initial direction is not immediately clear. Still, too many of such problems is too frustrating, and they tend to get too "mathy". I'll try my best to balance things better next time.

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

          I proved E,F before coding. I don't like hard-proving problem too in rated contests but I think it was not so hard (than coming up with a correct solution) this time.

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

        I think the proof for D is fairly easy and i was able to do it in a fair amount of time,and since i am the "targeted" contestant for it than i think i am the right person to speak for it.Same goes for B, B involves simple high school mathematics to prove.Sorry for my poor English.

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

      Even B and D many solved without proving.

»
4 months ago, # |
  Vote: I like it -55 Vote: I do not like it

I found the solution for E, but I can't implement in time —

solution for E : === infinite loop === node i = minimum of nodes There is no edge comming to node i.

(i's leaf) <= 2,

(i's leaf's leaf) <= 4

open i and i's leaf / close i's leaf's leaf // opened node / (opened + closed node) >= 3/7 : you always satisfies erase-ratio.

erase the i, i's leaf, i's leaf's leaf in the graph

Am I solved right?

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

    No, there are complications. For example, suppose you have i, i's leaf and i's leaf's leaf. Then say j is another parentless node, and say j's leaf's leaf is one of i's leaf.

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

I solve problem C with smallest k value... and after end of contest.. k doesn't need to be smallest. T^T

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

Arthur, please do not manage the ski resort anymore.

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

What so special about 4/7?

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

    i did some cases and it seems that if you greedy for low cases 4/7 should work because you break alternating connections (so if you find a path of length N break 2, 4, 6, etc) but it fails for larger cases like 28 for some reason or another (i drew 28 vertices and kept on mixing and matching but couldn't find the intuition to solve)

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

    If you remove the ends of all the paths of 2 greedily(starting from top to bottom). Then, if x spots are removed, there will y>=x/2 spots that were before these spots in the paths and z>=x/4 which were before the y spots. (x+y+z >= 7/4x => x <=4/7 n)

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

No one:

Literally no one:

Me: Scribbling problem C in-contest using online minesweeper

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

In E, does anyone have a counter for this?

$$$S$$$ = {$$$1,2,3,..N$$$}.

while $$$S$$$ isn't empty
Take smallest numbered node $$$v$$$ from $$$S$$$ with indegree 0, add nodes at distance 2 to the answer.
Delete $$$v$$$ and nodes at distance 1, 2 from $$$v$$$ from set $$$S$$$ and update indegrees.

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

Editorial for C :)

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

»
4 months ago, # |
  Vote: I like it -68 Vote: I do not like it

What is this?

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

Least binary searchy interactive problem I've ever seen. Really enjoyed that one.

C and E were really nice too, and I don't have any complaints about the other problems. Great work on the contest overall.

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

RIP my rating.

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

My solution for C:

Tutorial
Solution
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    overcomplicated

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

      Tell me if you suggest a better approach.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
         vector<pair<int,int>>v;
          
          
          
          for(int i= 0; i < n+2 ;i= i+1){
             
              int a,b;
              if(i==0) a = 0;
              else a = i-1;
              if(i==n+1) b = n+1;
              else b = i+1;
              for(int j =a;j<=b;j++) v.pb({i,j});
              
          }
          
          cout<<v.size()<<ee;
        
      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it
        int dim=n+2;
        for(int i=0;i<dim;i++) {
            System.out.println(i+" "+i);
        }
        for(int i=0;i<dim-1;i++) {
        	System.out.println(i+1+" "+i);
        	System.out.println(i+" "+(i+1));
        }
        
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's another cool approach!

»
4 months ago, # |
  Vote: I like it -57 Vote: I do not like it

fucking piece of shit.

»