star_xingchen_c's blog

Codeforces Global Round 13
By star_xingchen_c, 2 months ago, In English

Hello Codeforces!

On Feb/28/2021 16:35 (Moscow time) we will host Codeforces Global Round 13.

It is the first round of a 2021 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 2021:

  • 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 2021 supported the global rounds initiative!

The problems were written and prepared by 3.141592653, Widowmaker, Ynoi, errorgorn, oolimry, star_xingchen_c, syksykCCC.

We would also like to thank:

You will have 3 hours to solve 9 problems. We encourage you to read all the problems and solve them all.

One of these problems is interactive, please see the guide of interactive problems if you are not familiar with it.

UPD1: Scoring distribution: 500-750-1000-1250-1750-2000-2250-3000-5000

UPD2: Tutorial published.

UPD3: System testing finished, congrats to the winners!

  1. maroonrk
  2. DmitryGrigorev
  3. Petr
  4. jiangly
  5. RALZH
  6. qazswedx2
  7. sunset
  8. ecnerwala
  9. lumibons
  10. p_b_p_b
Announcement of Codeforces Global Round 13
 
 
 
 
  • Vote: I like it
  • +1092
  • Vote: I do not like it

Comments Comments (344)
»
2 months ago, # |
  Vote: I like it +236 Vote: I do not like it

I hope our round will have less fst than the last one :D

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

All hail our emperor anton

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

XDD

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

XD Don't fst pls!!!1

→ Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it -13 Vote: I do not like it

I must say that this will be a great competition. Antontrygub is a very good and professional coordinator. The authors are also very good and their level is very high. It is very pleasant to work with them. The topics are very interesting, I hope most of the contestants will like them. I hope the competition can be held smoothly, and I wish every participant good luck and high rating.^__^upd: Celebrate the success of the competition! Congratulations to the participants who played well, and wish the participants who did not play good luck next time!

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    Respect for Antontrygub ,Due to his coordination work he cannot participate in so many rated rounds.

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope this contest has strong test cases:D

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +145 Vote: I do not like it

As a tester,stay calm when you enjoying this great contest and don't throw your laptop or your keyboard at the floor XD

If you keep trying on the problem,you'll find the key and be proud of yourself!

GL and HF!

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    As a participant, these types of comments from testers send chills down my spine :(

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

    As a participant, failed system test is more annoying than Wrong answer on pretest 2, so it may be situation when someone try to throw his laptop or keyboard after system test !

    !
    → Reply
»
2 months ago, # |
  Vote: I like it +58 Vote: I do not like it

Excellent problemsets! Hope you will enjoy it.

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

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

As a tester, please give me contribution!

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

As a tester, I can say all problems are good and interesting. Wish that everyone will enjoy it and get high ranks.

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +66 Vote: I do not like it

As a tester, I would like to recommend reading all the problems. All the best!

PS: Problem quality is good :)

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it -35 Vote: I do not like it

ฅ•ω•ฅ

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

As a tester, please give me contribution!

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

wherever i see the word "interactive", i see the words "binary search" also. XD

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant get ready to brick!

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

I hope this time task C will not be difficult for me like last time)

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope this will be a nice round for all !!!

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

A global round on my birthday; the best birthday present :)

Thanks to Codeforces and all the writers and testers!

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

I hope this round will have less FST than the last round :)

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

As a tester, I found some of the problems quite challenging, but they were all very interesting. Read all the problems and have 3 hours worth of fun!

→ Reply
»
2 months ago, # |
  Vote: I like it +90 Vote: I do not like it
The problem writer said
→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    I'm afraid it will cause panic among all participants and make problems FST easier (?)

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    maybe examples are so strong :dicaprio:

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

oh

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

Attention!

Unusual start time

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

    It's only an hour earlier than regular round, isn't it?

    UPD: Err... It may mean a lot in other countries... Alright.

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      5:35 am infinitely harder than 6:35 am to wake up in west coast :(

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

        That's unless you are too excited about the contest to fall asleep in the first place.

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

          I tried sleeping at 10 pm yesterday but couldn't due to the hype...ended up staying awake till 3 am and dipped the contest rip.

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

All hail our emperor anton.

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

Finally, another chance to decrease my rating

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

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

    ;)

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Does that mean you can think like a master?

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

      Nah specialist is my limit but I still feel masters think like a human beings grandmasters and heigher is just unbelievable

      → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    When grandmasters think:

    <same image>

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this one's great newss

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

→ Reply
»
7 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

My journey towards becoming a specialist will start from this contest InShaAllah

→ Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

I wanna know how difficult this round will be.

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

    I think it will be as difficult as a div1+div2 round

    → Reply
  • »
    »
    7 weeks ago, # ^ |
    ← Rev. 7   Vote: I like it -29 Vote: I do not like it

    I can't tell you too many details, but you can imagine that the first two questions are about the first two questions of div2, and the last two questions are about the last two questions of div1, with increasing difficulty in the middle.(The questions are all interesting, I promise, I suggest you read all the questions)

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is starting time different from usual contests?:-|

→ Reply
»
7 weeks ago, # |
  Vote: I like it -67 Vote: I do not like it

an expert or above comments "all hail our emperor anton" : gets upvotes. a specialist or below comments "all hail our emperor anton" : gets downvotes.....

ye hai aapka equality??

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

Note that timing is unusual, I guess it should be mentioned

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what will be the difficulty level div 1 or div 2?

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for this round.

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

Hope to become cyan this time.

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

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

Really looking forward for this one.

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

I think you may have forgotten to link the scoring table. I found this link in a previous blog post https://pastebin.com/QT5sXEaT

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for good rating change

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Atleast one of these problems is on binary search (interactive)

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I look forward to getting a higher rating for me！

And I hope the round will be very nice.

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

Will rainboy start from the last problem today? Kind of sad for him -_-

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

    He was able to do both the subtasks in the last problem in Global Round 12.

    → Reply
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      I'm curious why he only solved the last 3 problems in recent contests. I mean he solved F, E, D and stoped even though he had around 1 hour left.

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

        No idea but he is definitely IGM Level. Sometimes, he completes the whole set but sometimes he stops at some problem even though he has sufficient time to continue further.

        → Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    OMG! I'm feeling so inspired by seeing his contest history,he tries only the toughest problems of the the contest, doesn't care about his rating. @Foundnt_Alice thanks for letting us know that someone like him also exists in this competitive community. Salute to him!!

    → Reply
    • »
      »
      »
      7 weeks ago, # ^ |
      ← Rev. 3   Vote: I like it -19 Vote: I do not like it

      Ignore

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

        It's not a fake account since he took every contest. Also, take a look at the numbers of problems he has solved

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

          Yes I agree with you, even today he just tried the last question I, and didn't bother to solve any other even if he was not able to solve that question. Who would not participate with his fair account in the Global Round.

          → Reply
»
7 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it
Spoiler
→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is Codeforces recent actions frozen?

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

First time to see '5000' in the score distribution

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

    This requires solution from the moon :)

    → Reply
»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

CodeForces Zindabad!! Long Live CodeForces!!

→ Reply
»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

hi all

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

MiFaFaOvO Registered ...

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

A request to the problem setters. Please add accepted solutions(code) in the editorial.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the diffulty level of global round as compared to div2 rounds?

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

    i think its mixed div1+div2 first 2-3 questions are quite easy ....then for the rest the difficulty increases exponentially.

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

      not aged good....Even tourist did many wa before AC,,,,It is Div 1 only round!!!!!!!

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

      Not as easy as normal div 2 first 3 problems!!

      → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what about penalties? Does Non-Correct Answers have any penalty?

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

    yes 10 min*no of incorrect attempts(excluding the pretest 1 and compile error)

    → Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

No fst, no fst,no fst,ples! (Like everyone has hoped.)

It is said that Globle rounds are always difficult, so I think I may perform poor in the contest.

All in all, I hope we all can have fun solving the problems, stay Cheeki Breeki:)

PS: I hope I can turn my name blue after the contest. (Although I don't think I can do it)

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

If I don't reach Master today I will quit rounds for at least 6 months.

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

Hoping for blue.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Submission in queue from 2 minute

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

Stand by me and let's wait for the memes about tourist and problem C.

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

*sad newbie noises*

→ Reply
»
7 weeks ago, # |
  Vote: I like it -51 Vote: I do not like it

Problem C is bad. Even some Grandmasters and LGMs took a long time to solve it.

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

    Why does that make it bad? I thought it was a good problem. Overall I'm really happy that the difficulty spiked up fast, and the start of the contest wasn't just about writing code to ~5 trivial problems.

    I can see why this would be bad for div 2 though, but that's the thing with problem difficulty of combined rounds, you cannot really make everyone happy :/

    → Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    I think it was a brilliant problem with many tricks. That's why many people got it wrong initially and then corrected it. Overall it was a superb contest with good problems.

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

    I solved G, but failed to solve C in time lol

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

      Even tourist took more than an hour to solve C. D and C should have been interchanged in my opinion. But you know, those who solved C would always disagree.

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

        Yeah I think so, but since the amount of people who solved C is more than D, there should be at least 125 people who disagree XD

        → Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

We can't get FST if we don't pass pre-tests ;) well played cf

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

HardForces

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

    There should be a round like this once in a while to make us question our strength for a sec. But, anyways a lot of registrants didn't even submit knowing they'd lose their ratings.

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me how to solve F after the contest? I came up with many approaches but none of them worked.

Anyway, F is a beautiful problem!

→ Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Very difficult round. Just solved 2. (Pending system tests of course)

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

I'm gonna FST in problem B :-(

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

[Im a tester, so I pre-wrote this]

I solved G through a weird method. It was motivated by the chemistry reaction mechanism known as electrophilic substitution. This reaction involves a negative atom (or number) replacing a positive one, and in so doing causing the positive one to become negative.

This allowed me to motivate a constructive algorithm that basically involved using a negative element out of place to replace the positive ones in the wrong places. It took some casework, left as an exercise.

Here's my code: https://gist.github.com/dvdg6566/fa2bbe6fd49b1109e3639ddaefb1a26c

→ Reply
  • »
    »
    7 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    orz, as a chemist, never before I have though something similar...

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

BREAKING: a monopole has been discovered.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was D? Is there a very silly observation or guesswork that works?

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

    U can move bit from smallest to highest and delete some bits. So, u should check that u < v and on each suffix count of bits in u >= count of bits in v

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

    I tried to do random stuff and one of them worked.

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

    My approach is simply iterating u and v bit by bit, from LSB to MSB. If u[i] is 1, increase a counter; if v[i] is 1, and that counter is 0, return NO.

    Apparently v shouldn't be smaller than u.

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

Why wasn't it explicitly mentioned that there will be no obstacle in first and last column in B? I know the constraints clarified it but it still makes more sense to mention it explicitly.

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

    Wtf :(

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

    I found this out after a long time.

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

    So that idiots like me to quit the contest early.

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

    I also think this should've been mentioned. I didn't pay attention to the constraints, and thought there can be an obstacle in the first or the last column. Finding whether the start and end points are blocked by "triangles" seemed too hard to implement for B, so I moved to C.

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

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought D is just no. of set bits is equal in both the nums and the LSB In u <= LSB in v and u<=v to be Yes cases and everything else as No. But WA on pretest2.

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

    Counter Example: 15 and 16, You can get to 16 by adding a 1 to 15 and that is a valid edge in the graph

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

OK CF! There will come a day when I am not afraid of ya. Wait and watch.

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

Why brute force in C doesn't work? I just start from index 1 and make this value 1 by just doing what's stated in the problem now as not to surpass time limit I check whether i+a[i]>n or not, if it is true then I bring a[i] down to n-i so that i+a[i]<=n (add n-i in answer) and as n can be 5000 at most the complete algorithm would be $$$O(N^2)$$$ but it gave me TLE on pretest-9 can anybody help?

Here's my Submission

Edit:- Its $$$O(N^3)$$$, I got it thanks for the response.

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

    The runtime is not N^2.
    Note that a[i] can get decremented by 1 in your inner loop.
    id can also get incremented by 1.
    Taking overall complexity to N ^ 3

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

    Each number can be around 10^9. Then the time complexity is not O(N2).It is actually dependent on the numbers in the array

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

    I did the same thing only to realise that it is actually O(N^3). For each s_index you are doing O(N^2) work and ignoring the cases where s_index + index > n you will still have O(N^3) work

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

    Your submission is $$$O(n^3)$$$

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

    If the test is 2500 5000 followed by 2500 1 you will take O(n^3) time to compute your function, you need to speed-up your brute force (which is what I did) by storing when there is 1 the next which is not 1

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

    I generated a test case that would take $$$O(n^3)$$$

    Here is the case: https://pastebin.com/0bcp1Y5x

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

    sasuke_uchiha Priyansh31dec well it is indeed $$$O(N^3)$$$ sorry for the silly question I just figured it out, poor me (-_-).

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

    No it is not N^2 something similar like this your code goes N^3

    5000
5000 5000...1 1 1...1 1
There are N/2 times 5000 on first N/2 elements
    → Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I am having the same problem.I Suppose this solution is not purely O(n²).

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please can anyone give some idea for C?? I am getting the wrong answer on pretest 2

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

    For reducting a number to 1, we can either start there or get reductions from other starts to the left of the number.
    Note that for we can jump from any index j, j in [1, i — 1) (i — 1 exclusive) in exactly 1 move.
    ans -= No. of numbers to its left not less than i — j

    From i — 1, we could jump a few excess (equalling the number of visits to that number after it got reduced to 1) . (visits[i — 1] — ar[i — 1] + 1).

    Contribution from the current node will be: ar[i] — visits[i] — 1;

    108735314

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

To those who waited for my stream with solutions: it's canceled because I failed miserably today (solved ABCDE, unsure about my E). Sorry about this.

Instead, I'm going to talk about my team's solution for Google Hash Code Qualification Round.

After the Hash Code stream, I might upsolve F and G.

→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    Solved ABCDE and "failed miserably" don't go together.

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

      Because he is on a higher level dude.

      → Reply
      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it -22 Vote: I do not like it

        I get it. But that's life. You don't get what you want everyday.

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

      Maybe he is sad because he is red? I think, if you were red, you would be sad because of this situation

      → Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    If it is called failing then those who solved A/B are killed.

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

All hail our emperor anton

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

F is a brainteaser, a lot of thinking and a rather simple idea.

Let's try to find the second magnet. We do that by comparing [1] to [2], [1 2] to [3], [1 2 3] to [4] and so on. If at some point we have a non-zero force, then we know that the magnet at the right side is magnetized.

Once we found it, we test it against all the magnets to the right. Also we know that there is only one magnetized magnet to the left, which we may find with a binary search.

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

Wrote this during today's contest. CPP Magic.

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

    Same. Wasted 30 min to debug this :/

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

    The compiler will probably warn you.

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

      I am using CLion and these mistakes are highlighted)

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

      Unfortunately, my compiler didn't warn me.

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

Amazing round !!

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

Problem C and D :|

nothing to say. just :|

C was amazing :/ graphs everywhere. heheboy.

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

    Please can you elaborate on how you used the graphs concept in C??

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What a pity for the authors that no one has solved the last problem(

→ Reply
»
7 weeks ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

was it only my where i was getting verdict late... it was taking like 8 to 10 sec to give verdict and in B typos everywhere

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is tutorial or when it will be published?

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

looks like rainboy (the chameleon of codeforces xD) missed the grey xDxDxD.. sadForces

→ Reply
»
7 weeks ago, # |
  Vote: I like it -152 Vote: I do not like it

I did not submit anything because dislike problem statements of A,B,C.

A: It is obviously a "game" about what is largest, what smallest, and what means ordering. So all in all it is a language riddle. Formulating a word puzzle with intentionally difficult to understand text is bad style. At least do some bold if with largest the smallest is adressed.

B: "Moving one obstacle to an adjacent by edge free node..." Sorry? This sentence in a super lengthy statement that basically explains a simple thing... Again, this is intentionally bad style.

C: Why not simply explain what a "pass" is? Best with first usage of the word? Did took me like 15 minutes to get what is asked.

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

    I guess I can sort of understand your complaints about B and C, but complaining about how "kth largest element" is ambiguous is kind of a bruh moment imo

    → Reply
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      I just don't understand why an intentionally unclear statement is used.

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

    Problem B is so good that you have to look at the constraints to realize it is problem B!

    → Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    And see how the letter u and v are used in D. Once v refers to the sum of the both input values, then v is used for the second input value. sic :/

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

Is it me or D was much easier than C?

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

    For me D was much harder than C.

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

    same here

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

    Yeah, I also found D easier, it was a simple observation. However, it can be very annoying if you don't find it and move on to trying brute-force approaches.

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

      I knew I could not solve C, so I invested my time in D. Unfortunately I wasn't able to make the observation you are referring to. Do you ming explaining what is it?

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

        When you go from u->(u+v), then you are basically adding a number v to u which has bits set on positions where its set for u as well. Eg. u = 11100101 v = 10100100, 11100000, 10100001(many other v's are possible)

        So first of all there were these observations: If you want to make x from y then:
        1. if x<y, then its not possible
        2. if the number of bits in x<y then also its not possible
        3. Also if some suffix (i.e. looking from the right) of x in binary has more bits set than those in y then also it is not possible as you are trying to add a bit to an already set bit, hence you can effectively move a bit to the right or make it a zero (by grouping it with another 1).

        So you just have to iteratively find the number of set bits at each position from 0-30, and then see if any position violates the 3rd observation.

        PS: Its a little tough to explain it properly but I hope you got some idea!

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

    Totally agree!

    → Reply
»
7 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

code submit khan karna hai

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

I think problem statements are not good so I failed to understand some problems and lost the time. I hope this won't happen again :(

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

So many testers, but no one found the bug in the statement of B.

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

    Also wouldn't solution fail (because horizontal and vertical were swapped) if it follows original statement ? I guess problem statement was made bit different after testing round.

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

GG

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

Can anyone share their idea for E?

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

    I didn't solved but i thought in following way : We can calculate the size of tree and if it's equal to some Fibonacci number $$$F_{n+2} = F_{n+1} + F_n$$$ then one it's sub tree must have size either $$$F_{n+1}$$$ or $$$F_n$$$ . Thus we can divide the problem into that subtree and original tree with that subtree removed.

    Since Fibonacci series is exponential , i think it will take $$$nlogn$$$ or $$$n(logn)^2$$$ depending on how fast we find that subtree.

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

    look for some edge where if we remove it we will have f (n-1) and f (n-2), and go back to working only with those subtrees recursively, just grab any edge that meets, if in any case it does not exist, answer in NO

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

      i thought the same but what will be its complexity bound

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

        seeing that F(28)> 2 * 10 ^ 5, each node participates in a maximum of 27 divisions (even less), and to calculate the size of each sub-tree is linear, then it would give as O (n * 27),

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

      What if there are more than one ways to cut a tree to f(n-1) and f(n-2)?

      → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

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

24 tests in a problem with binary answer and a ton of possible heuristic/backtracking/brute force solutions?

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

  • Write bruteforce in E

  • TLE14

  • Print NO and quit if the program was running more than 0.95s

  • ???

  • Accepted :)

→ Reply
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler for solution of E
    → Reply
»
7 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Xtreamely weak A pretests/

Whaaaaaats wrong in this solution ?

https://codeforces.com/contest/1491/submission/108679391

→ Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

how is this supposed to be a global round?! just look at my submission for C

108705080

even a stupid chicken can clearly see that it will TLE. I find it strange that such retarded authors who can't even make decent pretests were allowed to create a global round.

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

Couldn't you make stronger pretests? I didn't enjoy the CM yet XD

→ Reply
»
7 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it
  • Bruteforce in C passes, but with one small optimization:
  • Lets first[i] = g = index of first trampoline such as g > i, s[i] > 1.
  • If we jump at some j-th trampoline, and s[j] == 1, lets instantly jump to first[j]

108736709 — My submission

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

    This is exactly what I did bro,

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

    Yes, I use the exactly same approach which is easy to write and think but with O(n^2) complexity.

    → Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Guys, I have a question, for problem B.

Why in this case does the answer give me 0 if, u = 3 and v = 4? and my answer was accepted 108747951

→ Reply