Блог пользователя star_xingchen_c

Автор star_xingchen_c, 3 года назад, По-английски

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. gop2024
  3. Petr
  4. jiangly
  5. RALZH
  6. qazswedx2
  7. sunset
  8. ecnerwala
  9. lumibons
  10. p_b_p_b
  • Проголосовать: нравится
  • +1092
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +236 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +277 Проголосовать: не нравится

All hail our emperor anton

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

XDD

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

XD Don't fst pls!!!1

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -13 Проголосовать: не нравится

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!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +50 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope this contest has strong test cases:D

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +145 Проголосовать: не нравится

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!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 !

    !
»
3 года назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

Excellent problemsets! Hope you will enjoy it.

»
3 года назад, # |
  Проголосовать: нравится +103 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

As a tester, please give me contribution!

»
3 года назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +66 Проголосовать: не нравится

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

PS: Problem quality is good :)

»
3 года назад, # |
  Проголосовать: нравится +104 Проголосовать: не нравится

As a tester, please give me contribution!

»
3 года назад, # |
  Проголосовать: нравится +189 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant get ready to brick!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

Thanks to Codeforces and all the writers and testers!

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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!

»
3 года назад, # |
  Проголосовать: нравится +90 Проголосовать: не нравится
The problem writer said
»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Attention!

Unusual start time

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +31 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Finally, another chance to decrease my rating

»
3 года назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +345 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

I wanna know how difficult this round will be.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 7   Проголосовать: нравится -29 Проголосовать: не нравится

    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)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -67 Проголосовать: не нравится

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??

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thanks for this round.

»
3 года назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

Hope to become cyan this time.

»
3 года назад, # |
  Проголосовать: нравится +297 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Really looking forward for this one.

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope for good rating change

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -23 Проголосовать: не нравится

    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!!

»
3 года назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится
Spoiler
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is Codeforces recent actions frozen?

»
3 года назад, # |
  Проголосовать: нравится +94 Проголосовать: не нравится

First time to see '5000' in the score distribution

»
3 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

MiFaFaOvO Registered ...

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

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)

»
3 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Hoping for blue.

»
3 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

 *sad newbie noises*

»
3 года назад, # |
  Проголосовать: нравится -51 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится

    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 :/

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

HardForces

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I'm gonna FST in problem B :-(

»
3 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

[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

»
3 года назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

BREAKING: a monopole has been discovered.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня одного в Е по ощущениям зашла лажа?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +93 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Wtf :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I found this out after a long time.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 
    
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 года назад, # |
  Проголосовать: нравится +176 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +111 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Wrote this during today's contest. CPP Magic.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Amazing round !!

»
3 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Problem C and D :|

nothing to say. just :|

C was amazing :/ graphs everywhere. heheboy.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -152 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +40 Проголосовать: не нравится

    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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

    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 :/

»
3 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Is it me or D was much easier than C?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    For me D was much harder than C.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same here

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Totally agree!

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

 GG

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Can anyone share their idea for E?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      i thought the same but what will be its complexity bound

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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),

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem C?

»
3 года назад, # |
  Проголосовать: нравится +181 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

»
3 года назад, # |
  Проголосовать: нравится +220 Проголосовать: не нравится
  • Write bruteforce in E

  • TLE14

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

  • ???

  • Accepted :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Spoiler for solution of E
»
3 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Xtreamely weak A pretests/

Whaaaaaats wrong in this solution ?

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
  • 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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    You only have obstacles in 1, 2, ..., 10^6 columns. Not 10^6 + 1.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Red dots cant be placed at 1e6 + 1

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Thanks, my reading comprehension is bad, sorry

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      imo the problem should have made this more clear, it takes a lot of time to notice it

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This is why i took over a hour to solve this problem because i didn't properly seen the input limit. it doesn't contain 0 or n + 1 that make this problem a lot easier. But i missed this 0 and n + 1 are not in the input range for 1 hour and when i realized that, it was just a bunch of code.

»
3 года назад, # |
  Проголосовать: нравится +106 Проголосовать: не нравится

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

I got +117 delta change like my contribution :p

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What's wrong in my solution???? https://codeforces.com/contest/1491/submission/108741793

I modify the code to store all the obstacles and get AC, but have no idea with that :((

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

For problem D I tried the following for v > u

x = u
diff = v-u

for i:0 to 29
  if ith bit of x is 0 and ith bit of diff is 1:
    search for biggest j such that j < i & jth bit of x and diff are both 1
       if there is no such j then return "NO"
       if for any k between i & j:
          if kth bit of x and diff are both 0
                 return "NO"
return "YES"

But it is failing

I am unable to come up with a counter example. Please help

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Here is some code to help you generate counterexamples. https://paste2.org/yYY5PV46

    A few counter examples:

    Fail: u = 3, v = 12: correct answer is YES, your answer is NO

    Fail: u = 3, v = 20: correct answer is YES, your answer is NO

    Fail: u = 3, v = 24: correct answer is YES, your answer is NO

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In question B: for this tc: n = 3, u = 3, v = 5 a[0] = 2, a[1] = 1, a[2] = 4 I am thinking the output should be 3 but as per the solution the output is 0. Can anyone please help me to understand how the output is 0 for this tc ?

Thank you!!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve C? it didn't get the editorial nor the comments. can someone explain it breifly?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Since you move left to right, at the beginning of any pass, the optimal solution is to start at the leftmost index such that A[i] > 1, after which that pass is entirely determined by the values of A[i]. Since simulating the entire path each time might be too slow, we need to efficiently determine the impact of this index on the indices to the right.

    Each index between A[i+2] and A[min(i+A[i],N)] will be visited once from this A[i]. We store the number of times each index is visited (number_of_visits[i] = number of times we have already visited index i when we reach that iteration). If an index i is visited more times than necessary, then each additional visit will result in one more visit to index i+1 (since A[i] = 1 for each subsequent visit).

    At each index, therefore, we must add max(A[i]-1-number_of_visits[i],0) to the final answer.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Obstacle can't be in first and last column in B was evident only from constraints on ai. It was not written in problem statement. Costed me B :( .

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

[deleted]

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -67 Проголосовать: не нравится

CODEFORCES JUDGEMENT ERROR

this is my submission of problem A in java. https://codeforces.com/contest/1491/submission/108703837

import java.util.*; public class ss { public static void main(String[]args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int k=in.nextInt(); int c=0,d=0; int[] a=new int[n]; for(int i=0;i<n;i++) { a[i]=in.nextInt(); if(a[i]==0) c++; else d++; } for(int i=0;i<k;i++) { int l,x; l=in.nextInt(); x=in.nextInt(); if(l==2) { if(d>=x) System.out.println(1); else System.out.println(0); } else { if(a[x-1]==0) { a[x-1]=1; d++; c--; } else { a[x-1]=0; c++; d--; } }

}

}}

Unfortunately I have got a TLE for the same O(n) approach that got accepted in c++. I request MikeMirzayanov , star_xingchen_c and the rest of the problem setter to kindly go through this . I am greatly disapointed that judging time was not adjusted properly for java.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Unfortunately , my solution for E failed system test :(

But I wish I could get a T-shirt :D

My solution for E :

To find all the edges which link two parts that both size are in fib.

Try to cut the edges and dfs to find if there is a solution.

It got TLE on test 20.

The correct solution is to find one of the edges which satisfy the condition.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great problemsets except some typo problem, hope to see this kind of great round again :)

»
3 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

sad... my problem E TLE on test 22, when I switch language to GNU C++17 (64), it passed in 748 ms.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Me too.

    And when I submitted again with the same code and the same language,it Accepted. :(

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Great unusual contest! Thanks.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

Thanks for the great round!

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Wait, nobody is gonna talk about Pekora?

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Can anyone say me, when i can find a list with winners t-shirts?

»
3 года назад, # |
  Проголосовать: нравится +87 Проголосовать: не нравится

Congratulations to tshirt winners!

List place Contest Rank Name
1 1491 1 maroonrk
2 1491 2 gop2024
3 1491 3 Petr
4 1491 4 jiangly
5 1491 5 RALZH
6 1491 6 qazswedx2
7 1491 7 sunset
8 1491 8 ecnerwala
9 1491 9 lumibons
10 1491 10 p_b_p_b
11 1491 11 Radewoosh
12 1491 12 duality
13 1491 13 Marcin_smu
14 1491 14 Golovanov399
15 1491 15 AndreySergunin
16 1491 16 Sugar_fan
17 1491 17 aid
18 1491 18 never_giveup
19 1491 19 Endagorion
20 1491 20 dlalswp25
21 1491 21 LJC00118
22 1491 22 uwi
23 1491 23 YeongTree
24 1491 24 amethyst0
25 1491 25 Um_nik
26 1491 26 MAOooOAM
27 1491 27 nutella_waxberry
28 1491 28 Anadi
29 1491 29 dsgrekova2
30 1491 30 Farhod
37 1491 37 hos.lyric
42 1491 42 chenyanbo
47 1491 47 Comet_Honeymoon
59 1491 59 szb
62 1491 62 Ra16bit
135 1491 135 TrivialMan
137 1491 137 KrK
139 1491 139 Clix
167 1491 167 MonkeyKing
171 1491 171 kizen
173 1491 173 klimoza
247 1491 247 SEGFAULTSEGFAULTSEGFAULT
248 1491 248 balbit
255 1491 255 olimpo
273 1491 273 demagleb
316 1491 316 mr_chen116
327 1491 327 achi_basadzishvili
374 1491 374 algo.code
382 1491 382 Sh0
445 1491 445 Flame_Kaiser
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

128744013--->1491A - K-th Largest Value--->Java 11. The above submission is giving me TLE on test 6 the complexity of my solution is O(Q+N) I am not able to figure out where I am going wrong it would be great if anyone helps me with that. And also the same solution got accepted if I change the language to Java 8 --> 128744181. Kindly explain me this too.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The problems are that the complexity of your input is O(Scanner) and the complexity of your output is O(System.out.println)