Endagorion's blog

Codeforces Global Round 8
By Endagorion, history, 4 years 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

Comments Comments (412)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +76 Vote: I do not like it

Surprising that even legendary grand masters have coordinators.

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

Aiming for T-shirt!

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

late announcement :p

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

Combined Round after a long time !

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

Deliveries in corona times T_T

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

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

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

Endagorion... It sounds like a good round

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

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

Will we see a jqdai0815 vs tourist?

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

Links of previous global rounds:

Codeforces Global Round 1

Codeforces Global Round 2

Codeforces Global Round 3

Codeforces Global Round 4

Codeforces Global Round 5

Codeforces Global Round 6

Codeforces Global Round 7

Hope this helps!

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

NICE Round

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

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

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

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

Combined Round! Hope it will be fun.

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

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

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

With how many problems?

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

No offense to anyone

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

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

→ Reply
»
4 years 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.

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

→ Reply
»
4 years 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

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

This comment section is shit.

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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 :)

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

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

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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$$$

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
        • »
          »
          »
          »
          »
          4 years 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.

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

            Yeah, that makes much more sense.

            → Reply
»
4 years 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!!

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

    Waiting for this contest before global round 9!

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

*_*

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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

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

Deleted

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

can someone post previous contest Links by Endagorion.

→ Reply
»
4 years 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

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

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

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

The tourist Is Coming

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

Is there any chance that the contest will be canceled?

→ Reply
»
4 years 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 :(

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

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

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

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

delayed 10 m !

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

More 10 minitues!!

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

Last five minutes delays are the worst thing ever.

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

delayed

Oh boy the queue will troll us again huh?

→ Reply
»
4 years 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

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

    hopefully queueforces 2.0 doesn't happen

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

10 min delay?

→ Reply
»
4 years 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" :(

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

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

    It's called ritual.

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

postponed for 10 mins?

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

Round delayed for 10 minutes.

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

The delay is like the apocalypse trompettes before a round.

→ Reply
»
4 years 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....

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

Hope queue don't play with us.

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

No queueforces please :(

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

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

→ Reply
»
4 years 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.

→ Reply
»
4 years 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 :)

→ Reply
»
4 years 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

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

Comment section nowadays

Apparently this post is included :(

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

Too Difficult.

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

    The second one is kinda tricky

    → Reply
    • »
      »
      »
      4 years 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.

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

What the hell is this 2nd problem?

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

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

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

That gap between D and E. Oooooooof.

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

Solved 4 Problems and left the contest.

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

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

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

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

→ Reply
»
4 years 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...

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

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

    → Reply
»
4 years 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)
→ Reply
»
4 years 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)

→ Reply
»
4 years 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.

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

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

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

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

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

    How do u do it in 4/6?

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

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

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

→ Reply
  • »
    »
    4 years 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

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

How to solve E?

→ Reply
  • »
    »
    4 years 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:

    → Reply
    • »
      »
      »
      4 years 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.

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

KSM problem C

→ Reply
»
4 years 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

→ Reply
»
4 years 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 :(

→ Reply
  • »
    »
    4 years 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!

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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:(

        → Reply
  • »
    »
    4 years 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)

    → Reply
  • »
    »
    4 years 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

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

    try this 2 3 5 ans is 58

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

Please tell any hack case.

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

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

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

How to solve E? someone help please

→ Reply
»
4 years 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!

→ Reply
»
4 years 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.

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

was b something about powers of 2 and 3?

→ Reply
  • »
    »
    4 years 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.

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

https://www.imageupload.net/image/rQ6xS

→ Reply
  • »
    »
    4 years 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.

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

      Its wrong because 4 gray box have 3 gray neighbours each

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

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

        → Reply
        • »
          »
          »
          »
          »
          4 years 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

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

How to solve C

→ Reply
  • »
    »
    4 years 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
    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +164 Vote: I do not like it

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

    Just look at this

    +++
+ +
++X++
  + +
  ++X++
    + +
    ++X++
      + +
....
    → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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.....
................
................
    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
4 years 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?

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

deleted

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

Very very interesting problems, thanks!

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

Worst contest i have ever seen!..

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

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

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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!

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

    looks like someone under-performed

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

How to solve B?

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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..?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years 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?

→ Reply
»
4 years 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...

→ Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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)

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
      • »
        »
        »
        »
        4 years 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.

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

      Even B and D many solved without proving.

      → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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

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

Arthur, please do not manage the ski resort anymore.

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

What so special about 4/7?

→ Reply
  • »
    »
    4 years 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)

    → Reply
  • »
    »
    4 years 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)

    → Reply
»
4 years 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

→ Reply
»
4 years 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.

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

Editorial for C :)

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

→ Reply
»
4 years 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.

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

RIP my rating.

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

My solution for C:

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

    overcomplicated

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

      Tell me if you suggest a better approach.

      → Reply
      • »
        »
        »
        »
        4 years 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));
}
        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's another cool approach!

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

fucking piece of shit.

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

How to solve D?

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

    you have to notice that when we do some operations, sum of array stay the same. So we just count how many bits we have in numbers and solve this problem greedily(sorry for bad english)

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

      that doest seems like a correct explanation the more concrete way is to prove why shifting of a bit to any other will never cause any negative overall effect it is actually easy to prove that!!

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

        Yeah, I proved it during the contest, but I'm a bit lazy, so I didn't want to write evidence here:)

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

          that was too easy for a yellow i guess!! XDD

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

    Here are several ideas that might help you to solve it:

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

    I did it this way: Firstly, note that the total number of 1s at every position summed up for all numbers in binary representations is going to be constant. Use these 1s to create as large numbers as possible. For every position, count all the on bits and now greedily make the numbers.

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

Would someone solving same problems on Global Round get better rating change than solving it in a Div2 Round (assuming same problems and same submission time in both)?

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

Oh, after having so many fast editorials, it feels bad right now to not have the editorial yet :(

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

Problem F: used some time to find $$$R(n)$$$ in OEIS, but failed

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

Problem F was driving me nuts, but I have a method that I thought would work. Does this seem like I'm even on the right track?

Divide n into groups of size k. Then, in each iteration, you can turn on k lights: replace any that were eliminated by the opponent, plus 1 or more in the remaining groups. If you keep doing this with groups of size k, you eventually can fill all but (k-1) in every group (and the opponent can eliminate one full group). So, you could turn on (n/k-1)*(k-1) lights this way (and would want to find the k that maximized that).

But, trying to figure out how to adapt that to cases where (n%k)!=0 was giving me difficulty, and I'm not sure that this method is optimal, even then.

I know I should probably wait for the editorial, but I'd love to know if this was close to the right idea...

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

    I used a similar idea.

    I divided the lamps in groups of size k with 1 lamp between them. The last group could be smaller. K is found by bruteforce.

    Then on each move I turn on all the lamps that should be turned on if there are >k such lamps. The opponent would turn off some of the lamps on their turn, then repeat.

    Example: N = 11, group size = 2

    XX_XX_XX_X_ (after my turn, +7 lamps on)
_______X_X_ (opponent turns off 5 lamps)
XX_XX_XX_X_ (I turn on 5 lamps)
______XX_X_ (opponent turns off 4 lamps)
XX_XX_XX_X_ (I turn on 4 lamps)
____X_XX_X_ (opponent's move)
XX_XX_XX_X_ (my move)
___XX_XX_X_ (opponent's move)
I finish the game here
    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    Note that $$$k=\sqrt n$$$ maximizes $$$(n/k-1)*(k-1)$$$. This is also optimal when $$$k\nmid n$$$, where you can just let the last group have size < k.

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

can somebody explain what's wrong in my approach for problem B?

my approach :- initialise an array cnt having value 1 for each of the 10 places. do prime factorization of k, then multiply the prime factors on cnt elements one by one.

for example, if we were asked to make a string for "hello" & k is 360, my cnt array will look like this [10,2,2,3,3] and answer will be hhhhhhhhhheellllloo

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

    Notice that the product of each character's frequency should be >= k.

    So for each character choose such frequency's such that they are equal or some of them have differences with others.

    Like this, $$$x, x, x,....x$$$ or $$$x, x, x,....x + 1, x + 1, x + 1$$$

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

    Well, I had trouble with it too, but anyways:

    First observation, if you multiply the frequencies of the letters, you get the number of subsequences. Here we are considering duplication of letters in adjacent positions. Ex: ccc ooo dddddd eeeeeee fff o r ccccc eeeee ssssss. So the number of subsequences over here = 3*3*6*7*3*1*1*5*5*6 = 170100.

    Now to start with, keep the frequency of each letter = 1 ie. the array f = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]. Also have an iterator i, which increments modulo n. So all you have to do now, is as you iterate, increment f[i] and see if the number of subsequences are more than the required number k. Refer to my code:- Submission

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

    Basically think of groups of letters: you want some number of "c", then some number of "o", etc.

    The number of combinations possible (i.e. the number of substrings possible) is the number of "c"s times the number of "o"s, etc.

    You can start out with one copy of each letter: "codeforces". Then, just keep increasing until the number of combinations is at least as large as the number you need: ccodeforces would allow 2 combinations. ccoodeforces would allow 4 ccooddeforces would allow 8 and so on. Eventually, you can get to 2^10 combinations possible: ccooddeeffoorrcceess at which point you need to go back and start using 3 of each letter, and so on: cccooddeeffoorrcceess cccoooddeeffoorrcceess etc.

    The key is to realize that you maximize combinations by "spreading out" the repeats: i.e. it is better to do ccoodeforces (4 substrings) than cccodeforces (3 substrings)

    I did this by keeping an array of length 10 that stored how many repetitions of each character would be needed, and just kept incrementing through, keeping the total number of combinations until it hit or exceeded the target number.

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

      once again, didn't read question carefully.

      I thought i have to make a string that contains exactly k codeforces subsequences. and thus did prime factorisation.

      feel stupid now...

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

        it happens. I also misread the problem as exactly k. Luckily I realized that if it were exactly k, then the size of the output is at least k chars for prime k (which is ridiculous for the limits)

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

    According to some mathematical theorem:
    if a*b*c=constant then to have a+b+c to be minimum the values of a,b,c must be very close to each other. So doing prime factorisation won't work, instead you find a number whose power is almost equal to k, copy this value 10 times, now modify values by adding 1 one by one, to get minimum answer ;-)

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

      It's an easy proof. Consider the difference to be $$$2k$$$, $$$k>0$$$. Then $$$(x+k)*(x-k) < x^2$$$. If it is $$$2k + 1$$$, them $$$(x + k)*(x - k-1) < (x-1) *x$$$. Therefore the difference between any 2 values should be less than $$$2$$$

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

      Its actually Arithmetic Mean >= Geometric Mean i.e. p1 + p2 + p3 + .... + pn >= n x nth root of (p1 x p2 x p3 ... x pn). If we make all of them equal to p, only then LHS = RHS otherwise LHS > RHS.

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

    hello bad example because you have to LL in a row.

    For "codeforces" word you can just add one char on each positio and number of subseq will be product of number of chars

    Do it while your number < K

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

Nice Minecraft sword reference on C. And D is a very nice problem.

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

ff

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

It appears I tied the 30th place with chokudai. How does this work, do we both get a shirt?

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

B is more difficult than C

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

nice problems :)

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

Can someone hack my E? https://mirror.codeforces.com/contest/1368/submission/84232635

I tried random, TLE on case 12. Added 2 greedy orderings, if that fails random, then it's AC. Can someone help me proving this solution sucks? :P

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

Thought the tests were faulty, turns out they weren't now I am stuck with this comment which I can't delete, thanks codeforces.

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

    same here

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

      if ta = 1, and tb = 2, and n is too large that O(n), while your first loop work on O(log n)

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

      consider the case: $$$a = 1$$$, $$$b = 1$$$, $$$n = 10^9$$$

      the second while loop will make $$$10^9$$$ operations and it will TLE

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

    Suppose a = 1, b = 2 and n = 10^9. Your second loop will give TLE.

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

    In the second while loop consider this case

    suppose a = 4,b = 1,n = 1000000000

    4 + 1 = 5

    5 + 1 = 6

    6 + 1 = 7

    7 + 1 = 8

    and it will keep going till n, which will cause TLE.

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

    The first loop is $$$O(\log n)$$$, the second loop is $$$O(n)$$$.

    In the first loop, the value of $$$\max(a, b)$$$ on the $$$i$$$th iteration is bounded from below by $$$F_i$$$ (Fibonacci number), so the number of iterations is bounded from above by $$$\log_\phi n$$$. In the second loop, the initial condition $$$a=n$$$, $$$b=1$$$ would yield $$$O(n)$$$ iterations.

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

    i upvote you :) that was quite genuine!!

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

      Thank you alot :), although it seems the community doesn’t agree with you or I for that matter :(.

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

        it doesnt matter i felt like that was genuine, i dont care about my contributions nd will become candidate master soon just watch and community also doesn't matter just do more and more problems.. i can raise my contribution as much as i want once i become purple or above they r gonna upvote me for the shittiest comment XD

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

I'm unable to submit my corrected F — I keep getting Unexpected Error. Am I the only one with this issue?

Edit: MikeMirzayanov, possible bug?

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

    Maybe, there is some technical problem. I am also facing the same problem.
    UPD: problem fixed

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

My solution for problem c is not checked. why? Submission is here: — https://mirror.codeforces.com/contest/1368/submission/84248862 @MikeMirzayanov

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

G was solved by 12 people, E was solved by 243 people. I solved ABCDFG and ended up behind ~40 people that solved ABCDEF (51st instead of 12th), I feel scammed :(

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

    That's one of the reasons I like AtCoder system more. :(

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

Good Problems! Here is my easy solution for C if anyone needs it. https://mirror.codeforces.com/contest/1368/submission/84251207. I have just formed an increasing staircase.

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

    Not just you....Everyone has !

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

      Just helping out those who couldn't solve

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

        It's great that you come forward for help, but there should be something different in what you are doing to help than what has already been done by others. If your approach is different than what others have already added, then it's cool (and rather awesome). But the solution you posted is probably the most common solution to the problem.

        The problem C already has about 6.5k ACs. You can imagine what will happen if everyone decided to help those who couldn't solve it by adding a link to their code in the comment section, even when all the submissions are already visible.

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

I can't submit now. Why?

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

How are the 20 t-shirts assigned? Is there a seed or something?

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

When will be the editorial out??

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

Need Some Help! My pretest are passed for Problem C but didn't checked for the main test. After the final standings submission verdicts Pretest Passed instead of Accepted or Wrong Answer if found on main tests. Endagorion MikeMirzayanov Problem — 1368C - Even Picture Submission — 84230794 Will system testing will happen again or is this a minor bug?

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

My submission for problem d was not checked although its correct why?? MikeMirzayanov

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

I'd like not to miss an opportunity to advertise a service for drawing cells which could be useful for debugging/verifying your solution to problem C

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

    Haha, thats funny.

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

      The limits are 126x56.

      I don't why I did this, but yeah.

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

Can you help me with this solution of mine https://mirror.codeforces.com/contest/1368/submission/84243786

It is giving WA in testcase 14 But on running the same testcase on my machine or codechef IDE or Gfg IDE, I am getting the right answer.

MikeMirzayanov can you look into this please. Thanks

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

    You have a floating-point imprecision error with the logarithm calculation. The submission gets AC when I use long double instead of double for the intlog() function, and also for your count variable. You can check out this submission here 84269419.

    This is exactly what I changed in your code : 

    long double intlog(long double base,long double x) {
    return (double)(log(x) / log(base));
}

    and

    long double cnt = 2.0;

    P.S. This is the code I submitted during the contest 84205432

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

Ugh, of course only after competition do I see the simple greedy solution to E

84267481

Just iterate through every spot in order For each spot a, if it is open and there exists an open spot that has a track to a, close all the spots that a has a track to.

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

    Is this "simply" less than $$$\frac47n$$$ though? It's not obvious to me where that bound should come from in this solution.

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

      Justification for being under 4/7 bound

      Take any spot. It can have a track to at most 2 other spots. Each of those spots can have a track to at most 2 other spot, meaning there are at most 4 spots 2 tracks away from a specific spot. If we close the 4 spots, we have closed 4/7 spots involved.

      The only issue would be if a spot was in the last group for one set of spots, and in the middle for another set. This is avoided by checking in the order of possible middle spots, so if it would be a final spot, it would be closed before we consider it

      EDIT: Another way of explaining it

      Everytime we close spots, we close up to 2. To close those 2 spot, we need 2 open spots, a, and one that has a track to a. The one that has a track to a can only have a track to 2 spots, so it can only contribute to the closing of 4 spots. Thus, we always need at least 3 open spots to close 4 spots, so we never surpass the limit ( a would never be used again to close anything as everything it has a track to is now closed)

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

        I think there's an even easier way to justify a bound of $$$\frac 1 2$$$. Say we have node $$$a$$$ which has a parent $$$a'$$$ and children. It has at most 2 children, so we close at most 2 spots. We can also guarantee that $$$a, a'$$$ will NOT be closed therefore we close at most $$$\frac 1 2$$$ of the nodes. We have this guarantee since we only close nodes that are children of other nodes, and since $$$a$$$ wasn't closed before we got to it, it can't be closed in the future since that would need a node $$$i > a$$$ where $$$a$$$ is it's child which is impossible. Similar logic for $$$a'$$$ remaining open.

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

          That does not quite work, because a' can also have 2 children. say you had these tracks

          1 -> 2

          1 -> 3

          2 -> 4

          2 -> 5

          3 -> 6

          3 -> 7

          Looking at 1, we don't close anything

          Looking at 2, 1 has a track to it and is open, so we close 4 and 5

          Looking at 3, 1 has a track to it and is open, so we close 6 and 7

          Spots 4-7 are already closed, so we skip them

          Since we used spot 1 as a' twice, we ended up closing 4/7 spots, so the bound is not 1/2

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

            Ah that's right. Thanks for pointing that out :)

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

      the worst case would be a perfect binary tree without any overlaps.

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

my screencast, finally not messing things up: https://www.youtube.com/watch?v=w8hClqVhDOU

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

    Look, we need to talk about your solution for E.

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

      Or about your tests :)

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

        I concede that my tests failed to stop this solution. I'm curious if it's possible at all.

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

          "03:42:28 Hacked by dorijanlendvaj" — yes :P. Not sure to what extent it was Errichto's-specific (maybe it would be impossible a priori, I don't know)

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

            Seed uphacking not included lol (I'm looking at you, dorijanlendvaj =)).

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

              He didn't use rand for testcase generation. So seed doesn't make a difference here.

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

                Damn, did I forget to add this... I had a similar construction but with a single cherry at the bottom. Figure that wasn't enough.

                My foot is now permanently in my mouth.

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

          If possible, please write which solution is being talked about here.

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

            Errichto's AC on E which was hacked later.

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

              Lol, that was anyway clear from the comments XD. I was expecting a clue on what was it. Anyway, I've had a look at the video, thanks.

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

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

      Mine wasn't randomized :/

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

what will be the rating of E??

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

So curious to see the Editorial....i don't know why is it taking so long?

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

Some post contest analysis for problem D (observations / pseudo-proof) :

  • For any two numbers in the sequence, if you calculate their AND and OR values, you'll see that the sum of squares of the AND and OR values is always higher than or equal to that of the two numbers.
  • As an example, let's take two numbers: 6 (110) and 5 (101). The OR gives 7 (111), the AND gives 4 (100).
  • Observe how this operation simply took the last 1 from the 5 and gave it to the 6 (hence 6 becomes 7), while leaving the first 1 in the 5 untouched (hence 5 became 4)
  • So every exchange just transfers the missing bits from the smaller number to the larger number, leaving the common bits intact with the smaller number
  • To maximize results, you want to get the largest possible numbers using the count of bits at each position. Count the number of bits at each position and start assigning them one by one. This way the largest number will have every available bit set, the second largest would have every available bit set from the remaining bits, etc.
  • Now just add up the squares of all elements
→ Reply
»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Please tell a hack case

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

Do checkout our video tutorials Q.D https://youtu.be/54lWTHW3DBE Q.B https://youtu.be/x_bf-8iHLvY Q.C https://youtu.be/L2-pyk4rq7g Q.A https://www.youtube.com/watch?v=mTeiYFrSRyc&feature=youtu.be&sub_confirmation=1

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

Man, at first for B I thought it said that the number of subsequences has to be equal to $$$k$$$. Does anybody know how to solve that version of the problem, i.e. writing $$$k$$$ as a product of ten integers and trying to minimize their sum?

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

    Should this work?

    Do prime factorisation of $$$k$$$ and then multiply the smallest two prime factors until there are less than or equal to 10 elements left in the array

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

      Did exactly that at first, it doesn't work well for primes of size 10^15 though :)

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

    we will not be able to print the answer for very large primes in that case right ?

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

      Ah true, I should've thought about that :). Regardless, still an interesting problem for, say, $$$k <= 10^6$$$.

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

      Are you sure? It won't be necessary to have just one string of "codeforces" and then increasing the count of characters, for example, we could have "codeforcescodeforces" and increase the count.

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

    At first i also had the same thought and i thought for this solution. Guide me if i am wrong somewhere. this solution is for k<=10^6. I created a vector of 10 int elements and assigned 1 to them(let's call the vector 'cnt'). I stored all the prime numbers less than 10^6 in another array say 'primes'. Then, i traversed this prime array and for each prime i calculated what is the maximum power of that prime that divides k (let's say p^m divides k) then i will just multiply next m elements of my cnt vector with p cyclically. After this i am just printing each character of "codeforces" same no. of times the value stored in cnt vector ex- if the cnt={6,2,3,3,3,3,3,3,3,3} then i will print"ccccccoodddeeefffooorrrccceeesss".

    This is my code for the main algorithm (t is the prime array): int x=0; for(int i=0;i<t.size()&& t[i]<=k;i++) { int c=0; long long power=t[i]; while(k%power==0) { c++; power*=t[i]; } while(c>0) { cnt[x]*=t[i]; if(x==9) x=0; else x++; c--; } }

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

My friends: how to solve problem C?

Me, an intellectual:

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

    Not really :3 next square starts from the center of the current one xD

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

    Nice!.. but more like

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

      There's a lot of different valid constructions for that problem, consider the obsidian blocks :)

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

What if in Problem C we have to print the smallest k satisfying the conditions? Any Ideas

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

When will the editorial be released?

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

    Working on it! Will update in a couple of hours.

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

      Okay, thanks. May I also ask how t-shirt winners will be announced?

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

For those looking for solutions to A-E, I explain how I did them at the end of my screencast of the round.

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

how to solve D if we Have to minimize the sum of square

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

    The answer would be not doing any operation

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

    Leave the array as it is because sum of squares of two numbers ( a and b ) is always less than the sum of squares of (a&b) and (a|b)

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

Event i can't solve problem B. This round is in another level:(

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

Why does my code for problem E give TLE? Any help would be appreciated. Link:-https://mirror.codeforces.com/contest/1368/submission/84298529

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

    Maybe it is much faster if you use references instead of copies.

    int does(vector<int>& v,set<int>& s)

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

Peace

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

Hi! Thanks for your participation. I'm glad to announce the winners of the t-shirts! They are:

List place Contest Rank Name
1 1368 1 ecnerwala
2 1368 2 tourist
3 1368 3 Marcin_smu
4 1368 4 Petr
5 1368 5 Radewoosh
6 1368 6 Um_nik
7 1368 7 maroonrk
8 1368 8 eatmore
9 1368 9 snuke
10 1368 10 KAN
11 1368 11 hank55663
12 1368 12 neal
13 1368 13 Egor
14 1368 14 frodakcin
15 1368 15 xiaowuc1
16 1368 16 TLEwpdus
17 1368 17 orz
18 1368 18 79brue
19 1368 19 uwi
20 1368 20 Noam527
21 1368 21 244mhq
22 1368 22 natsugiri
23 1368 23 Errichto
24 1368 24 jhnan917
25 1368 25 Benq
26 1368 26 LayCurse
27 1368 27 zeliboba
28 1368 28 Yongaron
29 1368 28 _h_
30 1368 30 chokudai
78 1368 78 loup
85 1368 85 Aeon
111 1368 111 keymoon
149 1368 149 sqrtdecompton
153 1368 153 aropan
160 1368 160 cstuart
170 1368 170 hitonanode
181 1368 181 AngrySeal
207 1368 207 tribute_to_Ukraine_2022
210 1368 210 KayacanV
272 1368 272 Hakiobo
292 1368 292 _Samir
340 1368 340 alexwice
342 1368 341 zscoder
370 1368 370 amnesiac_dusk
408 1368 408 sansen
436 1368 435 sniffleheim
447 1368 447 demoralizer
469 1368 469 ouuan
496 1368 496 minato
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thx :p

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

    So, how was the winner determined between me and chokudai? Did I not get a T-shirt because I'm later in the alphabetical order?

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

      Ties are broken using the time of the last accepted submission. But IMO this should be used only for random T-shirts.

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

      Update: It seems that there was a technical error. I am receiving a T-shirt now :)

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

Why is rating of the questions of last 2 contests not added?

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

Is it valid testcase for problem E ? If NO, then why ? 1 3 4 1 4 2 3 3 4 4 5

→ Reply