erniepsycholone's blog

By erniepsycholone, 7 weeks ago, In English

“It is not important to be better than someone else, but to be better than you were yesterday.” — Master Oogway, Kung Fu Panda

Hello, Codeforces! We are proud to present Codeforces Round 929 (Div. 3), and we hereby invite all of you to take part in it. This round will start on Feb/27/2024 17:35 (Moscow time). You will have 2 hours and 15 minutes to solve 7 problems. The penalty for a wrong submission is equal to 10 minutes.

This round will be rated for participants with ratings lower than 1600. However, all of you who wish to take part and have a rating of 1600 or higher, are welcome to register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

Remember that only the trusted participants of the third division will be included in the official standings table. As stated in this blog, this is a compulsory measure for combating unsporting behaviour and upholding gracious professionalism. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)

  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems were authored and prepared by erniepsycholone, snowysecret, dbsbs, jerryliuhkg, lomienyeet, and our beloved coordinator Vladosiya.

We would like to thank:

We hope that this contest, regardless of your background, rating and result, will increase your exposure to competitive programming and make you better than you were yesterday. Have fun!

UPD: Let's continue the streak of announcements with photos of the authors. This time with our coordinator and testers :)

UPD2: We discovered the screencast from Um_nik a short while before the end of the contest, and it had around 400 views by the end of the contest. Round is still rated, however, people who have used his solutions will be punished.

UPD3: Editorial is out

  • Vote: I like it
  • +444
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

As a part of the problemsetting team, we unfortunately cannot offer any competitive programming socks as prizes.

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

{Get's a -200 Δ} "There are no accidents" $$$-$$$ Master Oogway, Kung Fu Panda

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

As a coauthor, I encourage everyone to participate, regardless of your ratings. I also hope you enjoy the problems. :)

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

Wish to become an expert with this round :)

»
7 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

As a grandmaster testing...

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

    As an international master, I am disappointed that there has been no international master testing.

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

Time to unleash the inner Kung Fu Coder and make Master Oogway proud! #CodefuPanda

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

Will become Expert after this contest

»
7 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

As a tester, I cannot pupil

»
7 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

As one of the testers of this round (i definitely dropped to specialist on purpose to get my own line in the round announcement), I unfortunately did not receive any competitive programming socks for my testing efforts.

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

After rating rollback i became Expert so this is my first Unrated Div3 :)

»
7 weeks ago, # |
  Vote: I like it +129 Vote: I do not like it

Random meme:

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

maybe you can translate the saying into master turtle.

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

As a participant, CR7 is GOAT.

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

nice ạ

»
7 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

As a tester, I encourage every fellow programmer participating in the round to look at every problem to prevent skill issue. But anyways I hope everyone participating can have fun and hopefully learn something from this well crafted round~~

(The problemsetting team has genuinely dedicating a whole load of time to make sure this round runs smoothly with great problems!)

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

NEW DIV 3 ROUND YEAHHH

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

so many dbs students no kgv fame :( (dbs op)

»
7 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Master Oogway quote beautifully encapsulates the essence of personal growth and self-improvement. Focusing on our own progress rather than comparing ourselves to others is a valuable mindset to adopt. Each day presents an opportunity for us to strive for excellence and become the best version of ourselves. Thank you for sharing such a meaningful perspective!

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

As a tester, I wish you high rating and hope you achieve the rank you aspire to be :)

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

The secret ingredient is... !

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

    Actually, the secret ingredient is... !

    Spoiler

    Big respect to Master Oogway though.

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

It's time to make yourself and you better♥♥♥.

"Goodluck.", — Master Oogway, Kung Fu Panda.

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

ok

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

I hope I get blue :)

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

the quote hits really hard...

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

i wish i could solve A,B,C.

»
7 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

DBS forces

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

Finally unrated for me!

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

GOOD LUCK !!!

»
7 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Cumulative sum of their age is less than me or they looks very young?

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

Nice, new round, new training. BOTAAAAAAAT

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

Finally, another round where I can try hit pupil!

Good Luck for everyone!

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

Ohhhh,I see Atletico Madrid fan

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

I hope to solve AE

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

»
7 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

Kids are writing problems for a grownup like me. I guess that is the benefit of receiving a good education right from your childhood. The first time I used a computer was when I entered college :(

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

I predict that there would be a problem involving some range queries or stuff like that probably C or D It would have a simpler solution but will be overkilled by many using segment trees or something similar.

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

I hope to successfully enter the youth league tonight :)

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

Hoping for a fun contest.

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

give me a chance that making my name become yellow!

»
7 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Thanks for continuing streak of putting authors pictures on the contest blog

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

Good luck to everyone!

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

Hope fast ABCD

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

Mathforces

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

LOL, umnik_team uploaded the solutions before the end of the div

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

    Why did you write this here!? Now there will be a lot of cheaters!

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

um_nik is 1 hour ahead of us(iykyk)

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

WTF is this? why were the solutions posted before the round ends by Um_nik??? This is not fair. I hope they dont make this round unrated because of this.

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

    The problem-setting team has acknowledged the issue, and I have already tried my best to contact Um_nik on the issue a while ago to try to remove the video. I also hope the round doesn't get unrated :(

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

      What is the use of removing now? The damage is already done

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

        the video was there for more than 30 mins too, why didn't here remove it earlier

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

        We contacted him before the round ended of course.

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

    Most of the participants wouldn't have even seen the video. Hope contest doesn't get unrated (even though I couldn't implement E), as I truly enjoyed the contest.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

..

»
7 weeks ago, # |
  Vote: I like it +73 Vote: I do not like it

Thanks for the fast editorial!

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

I hate myself for not reading problem E correctly I was able to do it in 10 min once, I read the statement properly...

anybody did the same mistake?

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

is problem E binary search?

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

    I used ternary search

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

    yes

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

    yup. DP to calculate sum i -> j. then binary search

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

      search over what

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

        to find out K such that Math.abs(aL + a(L + 1) + ... + a(K) — U — 0.5) is Max

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

          why does that function work

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

            n = 1 => U

            n = 2 => U + U — 1

            n = 3 => U + U — 1 + U — 2

            ...

            n = m => U*m-(1 + 2 + .. + m-1) = U*m-(m-1)*m/2 = -1/2*m^2 + (1/2 + U) * m.

            It max when m = 1/2 + U

            => find K such that aL + a(L + 1) + ... + a(K) closest to m or 1/2 + U

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

              yeah sorry you're right, I misread the problem statement. shit. this is so much easier than what I was tryna do

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

    I was able to do it using binary search

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

    yes, binary search on convex function.

    you can see my code for reference:

    problem E solution
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      its just a linearly increasing function.. the score is the convex function... only the index is needed so you can just use binary search on prefix sums

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

        yes i saw after the contest, did not realise it in heat of the contest, as I misread the problem wasted 1 hour on completly different problem.

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

problem e was truly painful to implement

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

can someone tell me where it is giving wrong answer 248621389

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

I used logic similar to finding peak element in array. But got WA. Could anyone please point out the mistake in my code?

Submission : https://mirror.codeforces.com/contest/1933/submission/248632005

Edit : Found the mistake. I was subtracting a[low-1] instead of a[l-1] :(

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

    Thanks for the hint and your code,I tried implementing using peak element concept, but got stuck in the code, actually I did not initialize my ans to l and also did not make neighbour= -INF if they did not exist and your code came to my rescue.

»
7 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

It was a good bluff to require us to answer modulo 998244353 in problem G. (I intuitively knew that the answer could not be large given the harsh conditions, but because of this requirement, I was not sure of my consideration that there are at most 8 patterns even after writing an experimental code with a brute force.)

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

great contest! i really enjoyed A,B,C,D,E, but couldn't implement bs in E, I need to practice more bs problems( Anyway great contest!

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

anyone can explain the test case in problem G ?

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

Um_nik has uploaded a video about solving this contest before the contest ended: https://www.youtube.com/watch?v=Asqk4kXi8os&ab_channel=umnik_team . Will this contest unrated?

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

    There is no point in making the contest unrated. Cheating happens and solutions get leaked on Telegram and YouTube in every contest.

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

      But this is a public solution from a LGM while the contest is running. Anyone can AC all 7 problem with this video.

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

    I think it should be unrated because there used to be cheating to some level but this is not done, i was able to solve 4 in div 3 which is good enough, still suffered 44 rating decrease because of soo many cheaters. Ratings should be rollbacked for this contest. This was too much!

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

Brooooo my stupid "print" statement costed me PROBLEM-C ripppppp

print
without

This could have been the greatest clutch of my life but NOPE. I want to jump off a cliff :((

»
7 weeks ago, # |
Rev. 3   Vote: I like it +26 Vote: I do not like it

Hints for all the problems before the editorial comes out.

A: Collect all the negatives in one subarray.

B: Maximum answer can be 2. Think about the cases when 1 and 2 will be answer.

C: What if we fix values of (x, y)? Also, the value of k will not be always distinct.

D: What if you keep minimum element at first? What if there are multiple minimums?

E: The sum is increasing upto a point and then it decreases. It starts decreasing after the (u + 1)-th section.

F: Firstly, coming at the same position again is not optimal. Secondly, we don't need the UP move until the last column.

G: Constructive problem, try to come up with a pattern using second test of sample. Also, the answer can be max upto 8, ignore the modulo.

Thanks to the authors for some very interesting problems.


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

    Happy to hear that you liked F a lot (I wrote it) Thank you very much you have made my day.

    Hopefully, I don't get downvoted by saying this... ik this task kinda was a nightmare at first sight for some of you, but hope it was an interesting and insightful task. Hope it wasn't that hard to understand as well, I already tried to draw better graphics for the explanation.

    Anyways, we will try to get the editorials out as fast as possible :)

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

      Keep up good work making problems interesting to think about and easy but not boring to implement.

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

      No no, I think it was fine for everyone. And, the graphics were actually cool.

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

      I really liked F :> Might even take inspiration from it to create some educational DP problems myself

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

    hi, about problem F, do we really this observation to come up with a solution,

    "Secondly, we don't need the UP move until the last column."

    I think we can use simple bfs to reach the end

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

      The observation is correct, but there are also other ways to realize such an observation which will be mentioned in the editorials. Of course there might be alternate solutions that also work, but having this observation does simplify the question a lot and can be done through dp or bfs.

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

        yeah, I do know that, just wanted to know if someone solved this by just first obs,

        from each point, we move to three possible cells(up, down, right), using bfs we find the ans for last cell

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

    In problem C, Why I am getting TLE in this code. It is O(max(13,sqrt(100))+ 3*10^3) .

    My submission

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

      You forgot to add the complexity of creating a 10^6 sized vector in each testcase.

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

        Thank you. I realised that I don't need to create those arrays .

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

    In E, how can you say that the sum is a convex function?

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

      you may have misread the problem description just like i did. among tracks the decline by one continues.

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

    Could you please explain why we dont have to use the UP move until the last column, it will be very helpful

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

      When you're doing the UP move, your position relative to stones isn't changing, so basically the whole setup is same in a rotational manner. The only thing that changes is relative position of ending cell, which you can also change when you're in the last column.

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

    someone explain what does it mean by seeing the grid in the pov of grid? Everyone says see the grid as static? Someone kindly explain

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

Is this one about turtles?

Every question is about a turtle.

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

    Originally we had a storyline, but it was decided to be removed in the end to improve the task's clarity. The idea came from a few sources. The first one is because the old workplace or "home" of my school's robotics team (I was the captain last year) was next to a turtle pond, and so I have a strong love for turtles :) FYI, each of the teachers having their seats next to the pond were also called turtles with different nicknames for each of them. The second reason was that we liked Master Oogway in the movie Kung Fu Panda, so we thought it would be a good choice to use it as a theme, both silly and inspirational.

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

Don't know! Should I be motivated or demotivated?! after seeing the problem setters...:/)

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

I could not even solve B. Every one here is discussing about problem E

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

Problems: Turtle

Editoral: Rabbit

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

W contest , W younglings who made these questions ,Hope its not gone to waste cause of the stream upload

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

Can anyone give any counterexample where this submission 248545787 doesn't work for C?

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

fastest editorial ever seen

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

I performed well in this contest but the contest is unrated for me because I became exactly 1600 after the rating roll back.

If I was 1599 I got +70 at least :)

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

https://mirror.codeforces.com/contest/1933/submission/248622479 can anyone tell me what is wrong with this code for problem E

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

.

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

    If this is true I think CF can spot cheaters and skip them. so no worry :)

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

    i mean people always post the solutions on youtube while the contest is running and have alot of views as well. i don't understand why when umnik do it it will be unrated , F and G don't have a lot of ACs anyway.

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

      [deleted] it's not intentional ,it's a mistake and he apologized

      Edit: it was a great contest ,hope to see more such contest from authors

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

        nvm

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

          Few stupid guys!=whole india Stop using "Indians" "Russians" "Chinese" Do you compare umnik with this guys ? Definitely not

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

            ok buddy I'll edit the comment and remove indians since this annoyed a lot of people.

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

              No hate bro ,what you said is correct there is a mass cheating in every contest and we can't stop them

              I know that umnik is not one of them

              but we can't judge a country by some brainless individuals

»
7 weeks ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it

really liked both F and G, they are great! though $$$n, m \geq 5$$$ and strong sample little bit spoiled main idea of problem G, IMO.

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

    I guess n = 3 and large m is way harder than the current problem, thus they made such constraints.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Please don't make this one unrated:(

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

In C, l could have been much larger.

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

UPD2: Since the editorial is not out yet...

A solution
B solution
C solution

Original Post: Solved ABCDEF and I had no non-trivial idea for G. I enjoyed this problemset, and DEF are good problems in my opinion.

D solution
E solution
F solution

UPD: G upsolved. The ST was slow and I submitted 1 hour after finishing coding.

G hint 1
G hint 2
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please tell me what is wrong with my implementation of E. I can't think of anyother way to implement it and also cannot make this implementation work. 248638966

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

      why are you going up to u+1?

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

        I may be wrong about it. Is that the issue ? I tried submitting with critical = u which also doesn't work.

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

          if two index that are adjacent make same answer then you should take the lowest one. I think in the first test case your answer is giving wa. 3 1 4 1 5 9 for l = 1 and u = 8 your code gives r = 4. But r = 3 also gives the maximum sum. You should go upto u and check the next index also which is res+1. if it makes greater sum then output res+1 otherwise output res.

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

            Now I got it, thanks a lot. I thought of checking neighbouring elements to the r that I found, also but it felt very hacky to me and did not try it even once. :(

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

    Good hint for F. I was able to code it up after looking at your hint

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

    begin with other elements, and you will get 0 at the first x. can you explain this with proof? Thanks in advance

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

    For Problem-F

    Can you please help me :

    lets say that we reached the cell a[i][m-1] ...

    Why currAnswer = dist[i][m-1] + abs ( n-1 -i ) is not correct ?? ( where dist[][] can be found by simple BFS ) and thus the final answer will be Minimum over all i...

    How to correct it ?

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

      What if you walk down and there are rocks in your way? The "wait" is to go up all the way(i.e. stay in place from the grid's viewpoint)

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

The best insane problem D ever !!

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

Great Contest

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

Please don't make contest unrated. Just check for plagiarism for problems E,F,G that were send last 30 minutes with the umnik's code from youtube.

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

in prob C https://mirror.codeforces.com/contest/1933/submission/248626484 I am getting wrong answer from codeforces judge but if I am testing the wrong test case on my local machine it's giving me the right answer? WA on test case 2 40th test 8 4 780

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

why Um_nik why

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

The contest was very interesting, thanks to the organizers of the contest. I just found this stream where Um_nik broadcast the last ~1 hour of the contest. I felt very sad because some of the participants cheated and one of the great codeforcers has ruined contest. In fact, it's not about cheating, but about respect for the creators of the contest.

Dear organizers you did really greate job!

»
7 weeks ago, # |
  Vote: I like it +69 Vote: I do not like it

heres why i solved this G 2x faster than rainboy.

https://imgur.com/dKUPRJ3

»
7 weeks ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

sirs

thank u the much for this roudn !!

but fapipitito notice G is pretty specil?? fapipotato confused !!

fapipotato find solution near end but cannot code fast be cause hand weakk :((((

i liek all problom and this very high qualiti round!!

mcuh love and look forward to more future later round from u guys!!

fapi potato

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

:)

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

Really Great Problemset!

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

I did a BFS implementation in Problem F. Sadly, I got a TLE on Test 12. Can someone point out how to avoid it from my code?

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

    I did same. i did not observe that robot will move up only in last column :(.

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

    so move up only in last column will reduce your time complexity from O(n*n*m) to O(n^m)

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

      Ohhh man. This ignorant habit of mine just sucks af! :") Thanks btw.

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

Um_nik you are very bad

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

    Everyone makes mistake

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

      I guess Master Oogway's words work again, "There is always something more to learn. Even for a (Legendary Grand) Master" lol.

      And despite such issues may be problematic, I think we shouldn't put all the blame onto Um_nik as him doing his videos were for a good cause in teaching programming, just that he may have accidentally posted it early. Additionally, he has already apologised as well and I agree everyone makes mistakes, me included. Hopefully, such issues will be prevented in the future. :)

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

        but one thing i would say, umnik got really good taste in music xD!

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

Problem F is Awesome.

A bit different from usual problems.

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

was stuck at e, but then saw huge num of ac in E, around 4500 solve, now really upset after seeing the comments.

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

    e is still not hard despite the cheating . you just have to find the first sum that's bigger than u, using binary search and find what's bigger this value or the one behind it

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

      True. E was easy, but as i become super saiyan level dumb durning contest, i forgot to check the values behind

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

        it happens don't worry . keep grinding

»
7 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem F: BFS with one tricky observation. In this problem, the robot will move upward only when it's in the last column. Due to this constraint, the straightforward Depth-First Search (DFS) approach might lead to Time Limit Exceeded (TLE). This optimization should help improve the performance and prevent TLE.

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

    I tried DFS, but getting WA 248632066. Any possible reason you could tell?

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

      I haven't viewed your code but I don't think DFS will work, because BFS guarantees the lowest depth when each node is first visited but DFS does not

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

        You don't need to ever revisit any cell, so it doesn't matter BFS or DFS. AC with DFS

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

          You have to revisit cells if you are doing DFS and what you have linked is BFS

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

            Whether it is a B of D FS is determined by the order of traversal, and not the function name or use of recursion.

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

              Okay, the order of traversal in your linked solution is bfs order and if it was dfs order , you would need to revisit cells
              does this satisfy your highness?

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

                No, because it's untrue

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

                  my bad. didn't realise your 'q' was not a queue but a vector

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

Can anyone tell why my code for E is giving TLE on 8th TC after applying Binary Search. 248643885

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

Can anyone try and hack my submission for F? I just did a O(n^3) BFS and used bitset to store visited. It passed somewhat comfortably but I'm wondering if there's a case where it blows up. https://mirror.codeforces.com/contest/1933/submission/248595937

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

    are u checking upward in all columns ??

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

    Hacked.

    I generated a $$$1000 \times 1000$$$ grid with all $$$0$$$'s to greedily maximize the number of neighbors of each cell.

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

    I just added a condition where I move upward only in the last column and the runtime improved significantly, I don't think it can be hacked now. I think this implementation is very interesting because you are essentially doing the n^3 bfs with one little optimization for the transitions and the O(n^3) memory being reduced by a factor of 32 with bitset making it enought to pass the limits. https://mirror.codeforces.com/contest/1933/submission/248663273

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

      bitsets are so dumb bro if u were really that good u would've figured out something easier noobie

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

        shut up bro

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

          hey friend,

          just wanted to drop a quick note to say sorry for what went down the other day. i know i messed up and i feel really bad about it. didn't mean to hurt your feelings or make things awkward between us. i hope we can talk it out and move past this. let's grab a coffee or something soon and chat about it. again, really sorry, mate.

          take care, [Your Name]

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

          Nah man , he is onto something

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

      I think with your new optimization the time complexity actually becomes $$$O(N^2)$$$, and your space complexity would be $$$O\left(\frac{N^3}{32}\right)$$$ as you have stated.

      Moreover, I noticed that with your new optimization you don't even need the 3rd dimension for the visit array, since I think you can arrive at cell $$$(i, j)$$$ only if the time $$$t \equiv i + j \quad (\text{mod } N)$$$. So, you can optimize the space complexity further to $$$O\left(\frac{N^2}{32}\right)$$$. (see https://mirror.codeforces.com/contest/1933/submission/248668841)

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

        The time complexity is still technically O(n^3/32) as I need to initialize the bitsets, however your idea fixes that issue. The 100ms saved is most likely just due to the fact that there wasn't a need for so much data to be initalized.

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

It was indeed a good round, I just hope it doesn't get unrated.

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

I almost gave up doing competitive programming. After 19 months almost I thought, let's start again. I was reading the explanation of test cases of problem B. And I Couldn't even figure out how that explanation matches the output. Suddenly I see a message popping up, saying there was an error in the explanation of Problem B. How could the problem setters or the testers miss such error I don't know. I was totally frustrated and couldn't even focus anymore sadly. Such a frustrating experience -.-

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

    You should build up your mentality for competitives

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

I hope the round doesn't get unrated.

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

really thank you It was a good math contest Just remember from now on, this is Codeforce not MathForces

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

Was this really a Codeforce contest, 4 math and number theory questions in a row

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

    Most CP problems require math on some level. Maybe try learning it?

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

      YES Most CP problems require math on some level. but all of them doesn't have math tag

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

      oh bro Now I want to teach you something very friendly In Codeforce, tags are set for many questions that show the key ideas of the solution and the algorithms necessary for the solution. So it's better to learn how to use this site before you come and comment

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

help in problem C

here L = k * a^x * b^y, so, K must be a divisor of L. Now i need to check which of the divisors can be represented in (a^x*b^y) and count them. What is wrong with this idea? i think it shouldn't give TLE. My Source Code (WA on test 2)

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

    Try putting your "k" values in a set. Maybe that helps.

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

    You can keep the K values in hashmap for quick checking.

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

    In the code, you are only considering the case where a^x==l, or (b^y)==(l/a). Instead of thinking for 'k', try to generate all the values of (a^x + b^y) and then check if it divides l. Store the value of corresponding 'k' in a map or a set if it does. To avoid overflow issues you will need to consider the values of 'x' and 'y' up to which a^x and b^y do not exceed 'l'.

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

Thanks for making the round rated.

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

Thanks for problem E, I finally learnt how to implement ternary search.

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

    What's the idea?

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

      My answer won't be perfect, but I hope you understand something.

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

A bit sad that I couldn't code the E problem in time, the prefix sum and a binary search was an obvious idea of the solution. Good contest tho, I assume that it is a perfect example of a well elaborated div3 round. Many thanks to the authors, it was a pleasant adventure!

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

Child labor... unbeliavable.

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

why trivial binary search not working on E! like lower_bound(pref.begin(), pref.end(), pref[l] + u) AAAAAAAAAAAAAAAAA!!!!

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

    i mean that's literally my ac solution so idk bout you

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

    you also need to think about the r+1 and r-1.

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

https://mirror.codeforces.com/contest/1933/submission/248653337

Why my this solution is not working for E? im checking mid and mid+1

»
7 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it
#include <iostream>
using namespace std;

int main() {
    cout << "1\n"; // End the line after printing "1"
    cout << "1000 1000\n"; // End the line after printing "1000 1000"
    for(int i = 0; i < 1000; i++) {
        for(int j = 0; j < 1000; j++) {
            cout << "0 "; // Print "0 " without a newline
        }
        cout << "\n"; // End the line after printing each row of zeros
    }
    return 0;
}

I am trying to hack Problem F using above generator. But got this Verdict "Validator 'validator.exe' returns exit code 3 [FAIL Expected integer, but "#include" found (stdin, line 1)]". Someone help me find the error.

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

    You have to find and use the "generated input" tab in the hacking interface.

    Besides that, you have to NOT print the trailing space in each line. Your test will be validated and then given to contestant, who doesn't have the obligation to work on malformed input. The validator does not fix formatting for you, it just reports that formatting is wrong (easier this way).

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

I think my code is wrong in problem D 248569476 can someone hack it

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

Thanks for keeping the round rated ❤️. It will encourage honest participants who invested their time in participating in this contest.

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

"Round is still rated"

Lets goooooooooooooooooo

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

You know u cant detect cheaters they can simply change the code u might find some but still its kinda unfair

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

really enjoyed G and F. I don't know why I wrote a dfs solution for F during contest(that was also wrong).

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

any hints for $$$F$$$?

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

    You can remove the motion of the rocks by moving your reference frame up one unit each time step. From this point of view, at each time step the robot can either stand still, move down and to the right (if there is no rock at the end of this move), or move down two units (if there is no rock at the end of the move or at the intermediate square.) This may make it easier to see which squares the robot can reach and when it can reach them.

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

Hints for G?

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

    Answer is at most 8, try to write a bruteforce for n=m=5 and observe patterns.

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

Thanks for the great problem F!

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

Thank you guys for an amazing Div3!

Wow, the system testing is earlier than usual!

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

Indian youtubers?

No, Um_nik

»
7 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

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

in Problem 'D', i used Unordered_map to save time and got TLE on testcase 30 ;(

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

my program got TLE because use unordered_map? 248557195 (problem D)

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

I think that there's a problem of rank updating ychaaibi rating ( 1406 )

Thanks in advance, also thank you for the contest.

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

1599 after rating update. :( Does the rating increase after plag check is done?

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

    Yeah the rank was updated and my rate was also increased by 3 ( 1406 -> 1409 )

    Thank you so much.

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

Thank you to the question team for providing this tournament making it possible for me to pass 5 questions during the tournament. good bye pupil , hello Specialist :)

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

Is there anyway to get editorial of the contests (when over) at one-place.

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

In Question 1933C - Turtle Fingers: Count the Values of k,

Can anyone explain why do i need to iterate the values of x from 0 to (log(l)/log(a) + 1) ? Similarly i need to iterate the values of y from 0 to (log(l)/log(b) + 1) .

Why do i need to check for the last value (log(l)/log(a) + 1) ? Because anyway a power (log(l)/log(a) + 1) will be greater than l.

why does my solution fail when i iterate only till (log(l)/log(a)) ?

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

    When you compute log(l)/log(a) using floating-point arithmetic, you get rounding errors, so the value you compute may be less than the exact value. To see this, use a custom test to run the following program, which attempts to compute $$$\log 243/\log 3$$$:

    Test program

    You will get not 5 but 4.999999999999999.

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

Where is the editorial?

»
7 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I made the same mistake using ideone.com. Next time, I will be more careful. Please, do not reduce my rating. These ratings are very important to me. Please do not block my account or impose penalties. I assure you that I will be more sincere in the future.

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

i was taking this contest in my school(not only this one) a place where lot of computers are place there were many people that were taking this contest simultaniasly
due to my strategic of taking exams and contest , i have breaks through the exam time and it includes changing my position , having some fresh air , eating something , .... i believe when i was walking outside , someone has checked on my computer for codes of contest and because there are schools property , i can not put passwords on computers for security i will be sure that nothing like that will happen again