BiNARyBeastt's blog

Codeforces Round 972 (Div. 2)
By BiNARyBeastt, history, 3 months ago, In English

Good Day Codeforces!

Me and Tsovak are happy to invite you to take part in Codeforces Round 972 (Div. 2), which starts on Sep/14/2024 17:35 (Moscow time). You will be given 5 problems and 2 hours to solve them. Two problems are divided into two subtasks.

The round will be rated for all participants with a rating lower than 2100.

The problems were authored by me with Tsovak's help to solve and alter them.

We would like to thank:

Score Distribution: 750 — (500 — 500) — 1500 — 2250 — (1500 — 2000)

UPD1: The Editorial is out.

UPD2: Congrats to the winners!

Div.2:

  1. SSKMF

  2. kkkksc03

  3. achen.80

  4. cqbztl

  5. yanold

Div.1 + Div.2:

  1. jiangly

  2. aryanc403

  3. Ormlis

  4. maspy

  5. kotatsugame

On the left, you see Tsovak with TheScrasse at IOI 2024.

On the right, you see me with Tsovak at IOI 2024 (I Owe Ice Cream 2024).

1

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

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

As a tester, I

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

As a colorblind tester, what color is your Accepted?

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

As a tester tested long before, I should recall the problems to my memory.

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

As a tester, I toasted the round.

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

orz kHarsh3715

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

Does this mean C will be super harder compared to B2 ? C ~ E1 ???

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

Finally a contest after a long time .

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

after ages...

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

As a tester, I tried to get accepted with some shitty solutions.

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

nutella testing is crazy!

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

    Why don't it also be Kinder testing :)

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

As a tester,I recommend you to read all problems

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

As a contestant, BiNARyBeastt and Tsovak orz.

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

Excited for my first round as a pupil , all the best everyone .

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

This is the first and last div 2 round in September... Looking for more!

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

After a long time...

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

This one will be cool :D

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

As a Binary_Thinker, I tested BiNARyBeastt's round ;)

"BiNARyBeastt" contains 2 B's;

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

Scrasse looks nerd

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

i hope it won't become unrated like the last div 4 contest

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

Who is Tourist tester?????

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

"for wonderful double coordination and chess skills" back story?

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

    I wish I had something cool and interesting to say, like we fixed a problem using our chess skills, but I don't, lol. Scrasse was just playing in a chess tournament during testing, and I used to be a professional chess player, so I found it interesting and asked him to play some games with me.

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

As an IOIer, it's sad that I didn't know TheScrasse was in IOI

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

Oh, subtask in problem B! It must be interesting!

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

For tourist: You for participating!!

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

Score Distribution: qinmingze-(jiayiGood-applepear)-asy_01-Alexey-(Yulian0214-Yummisonflorita)

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

I was stalking the writer of this round, BiNARyBeastt. I found out that he has skipped submissions in two of the past two contests.

  1. https://mirror.codeforces.com/submissions/BiNARyBeastt/contest/1616
  2. https://mirror.codeforces.com/submissions/BiNARyBeastt/contest/1713

Does he cheated in these rounds $$$??$$$
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Yeah, it seems like he did

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

      So allowing a cheater to be a problem setter $$$??$$$
      It is safe $$$??$$$

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

        Idk, I wouldn't have done it personally

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

    Well, it was a long time ago. Not that it makes it better, but still I've participated in many rounds after that without being skipped. After checking, they are for using an alt account.

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

the "You" written in Legendary Grandmaster Style. When it will be true...

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

Remove or ban this person who posts adult photos because school Children less than 18 years of age are also practicing on this site.

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

    I was in the middle of a class when I scrolled through the comments...

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

I think problem A will be harder then B1 and B2

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

crazy speedforces it is

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

Great to see no more sex images!

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

After this, P(Codeforces banned by GFW) has increased by (IDK but quite a lot) percent

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

As a tester, I can guarantee that you'll enjoy this round, ceteris paribus.

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

orz kHarsh3715

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

chess battle advanced

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

Da ana Msr 7bibty

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

First time for me. I just started CP does it make sense to participate?

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

    of course. div 3 and div 4 rounds would be best for you, but I'd still recommend participating

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

    Yeah, it makes sense. Even as a beginner, you can learn a lot just by participating, and you’ll get points regardless of your performance in your first 2-3 contests, so don't worry. Best of luck!

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

As a tester, I have many questions (perhaps about how to deal with the AI situation). Probably too many.

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

A contest after so00 long but clashing with leetcode biweekly

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

The score distribution of this contest is really unique!

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

can anybody explain what is sub task?

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

this round going to be wild, new version of GPT available for first time in rated round in CF

to see how serious current situation is
→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solve more + correct problems this time ; aiming to become pupil before my birthday

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

Is it rated????

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

Why am I unable to register as unrated participant?

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

wish to cross 1800 rating today

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

.

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

"I Owe Ice Cream 2024", It's cute.

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

Link

Sharabi Lal is cheating alongside 100 live cheaters

Username: kya_b120

Please take action

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

    Bhai pr as per this link eska to a bhi solve nhi hua:)

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

Why is B so confusing? If a teacher is at cell 1 and David is at cell 2, then the teacher moves to cell 2 and David moves to cell 1, does that count as getting caught?

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

    That cant happen because then the teacher would catch david

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

      I mean intuitively if we picture a teacher catching students irl sure but the question still needs to be more specific.

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

        I can see where the confusion is coming from; they probably should've clarified that David being on a teacher's cell after either half of the procedure would lead to him getting caught just to remove all ambiguity from the question (David moves -> check catch condition -> teachers move -> check catch condition -> David moves ->...)

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

    first moves David, then teacher. David moves first and he ends up on the same square with the teacher and the game ends

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

    The teacher has an option to not move at all. So if David is going to move to cell 1 then the teacher will not move, whereas if David is going to not move, the teacher will move to cell 2

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

Yup just thinking about some parts of C and E1 solutions without any close full idea. just gonna eat popcorn and watch my rank go down.

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

cout.tie(NULL);????????????????

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

I'm not going to use ceil() function in my life ever again.

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

dp forces

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

    exactly and some dp time limit for C xD

    that good hoping for more FST so maybe i be CM this round :o

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

one of the Worst A in cf history.. could be the worst(est)

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

    It worths 750 points, so it is expected to be harder than normal

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

      what is the solution for A?

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

        First, notice that you can avoid making palindromes by greedily making the string as "aeiou" repeating (Which is "aeiouaeiouaeiou...").

        But in this problem, a palindrome can be formed by a subsequence, so there are also palindromes that can be formed by characters that are in between 2 similar characters, like "aea", "aia", "aoa".

        So the second thing to notice is you can move all letters 'a' next to each other, then all letters 'e' next to each other, and so on. Now just print the string in this order and it is the correct answer. (Obviously you can't avoid the palindromes that are of the form "aa", "ee", "ii" so this is the optimal answer).

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

        first observe that if we place similar letters apart then, we would be increasing the number of palindromic sub-sequences. Hence, we should present similar characters together, also observe that we should have many different characters as possible with lower frequency. So, at first distribute the powers using n/5 to each, then remaining would be n%5 which would be given only to the characters with i<(n%5).

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

      got 5 WA for me it still 400

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

    Got my a** handed to me in A itself

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

is C standard problem? how to be good at problem like C, I've been staring problem C for 90mins and still have 0 clue 😥

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

    You can begin to understand this problem by observing what the answer for the case with N-1 strings means for the case with N strings. Problems like such generally are solved using DP. Try to understand what concatenating a new string to the end means for the final answer.

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

Problem C is dp, right?

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

B ruins my mood for other problems (I sorted the teachers' position BEFORE accepting the input)

cooked

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

    This was LITERALLY THE MISTAKE I DID. To top it off, after printing the answer I was returning the function instead of using continue, query question disaster :(

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

      At one point I thought if 2 teacher move at the same time, it will add 2 instead of 1 for the final answer :)

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

    I got tle because I sorted it in every query…

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

Oh my god C took 100% of my brainpower, just logged off after solving it

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

why did u steal David's homework-?! sobs

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

Again this happend

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

Anybody got tips or good problems to help train for math questions like B?

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

    B isn't related to math

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

    Atcoder problems ig

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

    B1, B2 are simple Binary search, to find the lower bound, thereby finding in which part david is 1. start-first teacher 2. in between two teachers or 3. teacher — end

    → Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
My prob C history

:joy: problem C was a lot of fun

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

Yep, should've just attended the Leetcode round today.

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

Can someone tell me what is wrong with my C submission?

The idea is that each string has "type", which is the ending it can be completed to. So na = type 1, naaare = type 4 etc.

Then I use DP[i][j] = the best composite string you can get of type j, using the first i strings.

In each DP[i][j], I store the string itself. But because those strings can get quite long, I remove the "used up" characters, and keep track of the "total score" of that string, and the "hidden score" of that string.

https://mirror.codeforces.com/contest/2005/submission/281250930

I really feel like this should make sense, but for some reason my code get WA on testcase 2.

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

For problem B, Am I the only idiot who took that b1<=bi<=bn would satisfy throughout. Apparently it doesn't satisfy this condition. I solved b1 in 13 minutes, but due to this dumb error, I made 6 wrong submissions before finally figuring it out

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

    same bro same I though array will be sorted always due to which I made 4 wrong submissions

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

DP in C was harder than the DP in E1 for me

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

what to do in A and C . Plz expalin senior coders

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

    in a , i guess u needed to eliminate this kind of palindrome "aea" etc .. as aeiouaeiou will have this palindromic subsequence but aaeeiioouu wont have , so just repeat this vowels sequence till < then sort the string in the end

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

      i think for n==6 both "aaeiou" and "aeiouu" should work

      similarly for n==9 both "aaeeiioou" and "aeeiioouu"

      Am i wrong?

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

        yes

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

          then why did i get WA on this submission 281241976 i know the approach is not very good , but it does the exact same thing .

          can u tell me some test case it fails

          → Reply
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it 
                            for(int i=y-1 ; i>=0  ;--i)
                    cout << s[i];

            this string at the end in if(n%5) is not sorted

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

              Why they need to be in sorted order ?

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

                read my first cmnt all same character should be together

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

    refer this https://mirror.codeforces.com/blog/entry/133206?#comment-1198302

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

(sorry my English is poor.) I have a question: if I submit once before, and past the pretests, and I submit a new code later, as the rule says, I will get -50 scores, but when I viewed the standing during the contest, my score of E1 changed from 944->802, and my rank fell nearly 100rks. Is this normal?

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

    But you also resubmitted the problem 14 minutes later which means you got a lower score for the problem in the first place in addition to 50 pts penalty.

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

    when you submitted second code.it will -50 during that time score.like your first code get 944.bt when you submit 2nd code that time the score was 852.That's why you got 802

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

Beautiful problems! I expecially loved C and E1. As and OI-style enthusiast I loved the subtasks :)

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

note that if Narek fails to complete the last occurrence by finding all of the $$$5$$$ letters, then all of the letters he used are counted in ChatGPT's score $$$score_c$$$, and Narek doesn't get any points if he doesn't finish finding all the 5 letters.

Even with this reminder in the statement of problem C, I still forgot to handle this case ;)

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

(Maybe)Worked out E2 after contest 3 minutes, and lost 900 pts.=(

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

What wrong in my recursive dp solution for C 281249632

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

AryanDLuffy likely cheated using GPT for this contest, look at his submissions and compare to previous contests. His template and coding style completely changed. Also he solved E1 in 8 minutes while writing like 50 lines of comments that a human would never do and somehow failed B2 at the same time.

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

    Kinda funny how in the very first contest that applies the strict rules of using AI tools, he is using it so blatantly lol.

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

misunderstanding of problem C makes my contest to be interrupted, feeling sad.

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

Crazy contest. I solved A, B1, B2 and somehow still got expert performance.

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

Can someone please help me understand why I got TLE on B2 on this submission?

https://mirror.codeforces.com/contest/2005/submission/281216208

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

    We have similar solutions, mine passed. I did not use a set though, just vectors

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

    Since your v is a set, you must use v.upper_bound (Not upper_bound(v.begin()...)) to achieve logarithmic time complexity

    For why upper_bound(v.begin()...) isn't logarithmic in this case, you can refer to this link (On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.)

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

Why did my E2 solution get TLE on TC24? My solution complexity is O(n * (m + l) * log(n * m)). Is std::map too slow or do constraints of the test cases and statement contradict?

My submission: 281237867

I would be delighted if somebody helped with my problem.

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

    I'm not sure, but what if $$$\sum n = 3\times10^6$$$ and $$$m$$$ is very small among all testcases? Looks its time complexity will hit $$$1500\times 3\times 10^6$$$. I believe if (n > m) swap(n, m) will resolve this issue.

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

      But the sum of array lengths across all test cases is bounded with 1e3.

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

        Yep, but there's no constraint on $$$n$$$ and $$$m$$$, only $$$l$$$ and $$$n\cdot m$$$.

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

          from the problem statement

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

          No,in the statementsays that n and m is bounded by 1500 for each testcase.

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

            Yeah but I believe there could be more than one testcase?

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

              According to the statement sum of L is at most 1500 so it is impossible that my code executes 1e6 operation in each testcase.

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

                Yep $$$\sum l$$$ is small. But according to the statement, $$$\sum n$$$ is at most $$$3\times 10^6$$$, not $$$1500$$$, as $$$m$$$ can be $$$1$$$. It's true the math expression of constraints in the statement is a bit confusing tho.

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

                  I couldnt got your point. So you say that my solution gets tle when T = 1e3 and for each testcase N=1e3,M=1,L=1. Still my code executes total number of 3e6 * log(3e6) operations and it shouldnt get TLE. You can also check my submission history.

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

                  it's super interesting to see it failed on $$$n,m,l=1500$$$..If so, I guess it may indeed be a map's issue and the TL is too tight. I constructed the data and found your code takes ~2300ms at that case on my local computer. That's really close! :(

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

                  Oh no :(( Did I get TLE only because of the 300 ms extra? It is pretty sad to hear. Btw, I changed the array of maps with only a single map and it has got AC now. I could get many more plus delta :( Anyway, thank you so much for your help :blobheart:

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

      You are correct. Swapping solves the issue of time limit.

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

        There are 3 constraints in the E2 statement. Constraint 1: N,M,L <= 1500 for each testcase. Constraint 2: Sum of N*M over all testcases is at most 3 × 1e6. Constraint 3: Sum of L over all testcases is at most 1500.

        I think you should check the testcases of E2.

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

In problem B I thought teachers and David moves at the same time, and was solving this version of problem), and it was quite annoying version of the problem)

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

    but they do move at the same time right? if n = 5 and teachers are at 1 and 2 and david in 3 then david will move to 4 and teacher at 2 will move to 3 at the same time making the ans 5 -2 = 3 right?

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

      No, Statement says David moves first, and only after David moved Teachers will move.

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

        Yeah but does that make any difference? I mean they are at distinct cells in the first place..so whether david makes the first move or they make the move together the scenrio is same cuz at one point teacher and david will take position side by side and david cant move and the teacher will make a move and catch him

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

          it makes very big difference.

          consider the case:

          teachers positions = [2, 100000]

          David's position = 1

          and if teachers and David moves at the same time:

          • if Teacher 1 moves to position 1, then David moves to position 2
          • if Teacher 1 stays at the position 2, then David stays in position 1

          so we will have to wait for second teacher in position 100000, to help us. So it's very important to know for teacher if either David moved or stayed, and u can't know that if they move at the same time.

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

            David will move first, and upon that move, the teachers will move optimally to catch him

            so, with your test case, if David moved (to the only cell he can move to, the cell 2), the teacher in the cell 2 will stay in that cell and catch David

            and if David didn't move, then the teacher in the cell 2 will move to cell 1 and catch him

            and as mentioned in the problem: Everyone sees others' moves, so they all act optimally.

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

              Yes, I know it. I just explained other version of problem, and why it makes difference.

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

                If they move the way you interpreted tbe question i.e. moving at the same time then they can never catch him cuz if they land on david cell david will move to their cell and if they dont move david will also not move so it will be impossible to catch him in that scenerio but yeah i get your point

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

                  it's pretty possible in all cases where we have at least 2 teachers, and we really do have at least 2 teachers in this problem.

                  the tactic is simple, u just will make 2 teachers adjacent pos = [i, i + 1], and will move towards David with this two.

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

                  Oh nice i missed the part where the two teachers will corner him in one of the two endpoints of the room and finally catch him... Thanks for elaborating the difference

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

I think that this time the problems are so hard

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

    Don't worry, One day you will find them Easy.

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

    If you need any help, I am happy to help you upto my level.

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

I sincerely hope to enhance CF pretest.(like C)

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

I hate dp very much

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

Why does this exceed the time limit for C https://mirror.codeforces.com/contest/2005/submission/281250159

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

    Any loop with N^2 could possibly go over time limit, since N^2 isn't bounded.

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

dp contest(C,D,E1)

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

    D was not really dp at first. All testers solved without dp except 2 of them. However, AI was also able to solve it. We literally changed the problem minutes before the start with Scrasse barely finishing the solution to the new version in time. The new hard version was already solved by dp.

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

      in contest time i had dp idea but didn't implement it because i thought it would give tle.after the contest i find it accepted.But good problemset

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

      What was the first version, and if you can, could you publish?

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

        it was simply not asking for the amount of ways to get the gcd. You had to output only the max gcd.

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

          Many solution of D was hacked after the system testing..Will you consider it?

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

new version of GPT now capable of solving div2E, it's over, seriously.

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

nice contest

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

cute round

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

This was a really fun contest!

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

Thanks for the contest!

Problem A was fun as a first problem. Great job!

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

Such a nice contest!

  1. I did not notice any lags (thanks Mike!). Like, no lags at all. I have not seen this level of stability in any contest ever
  2. Some problems are split in two parts. I think this problem-splitting approach should be continued in future Div. 2 contests to make newbies (like myself) lives more comfortable
  3. All of the problems that I looked at (A, B, E1) are incredible. What I especially like about them is that they do not reveal any tactics in the examples

HUGE thanks to everyone who made this contest possible! This is the best contest in my life.

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

After a long wait a specific country is back with all it's telegram channels..

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

I'm not allowed to see the Editorial !?

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

Reading wrong constraints in problem C and wasting 45 minutes thinking how to solve 🥲

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

281289823

Hey guys! Pls check my submission for problem C:

I am pretty sure the time complexity is O(n*m) , still TLE :(

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

    NVM , had to optimize the implementation

    Accepted submission: 281307789

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

A bit low-quality

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

I finally got CM!

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

did you consider whom submission was hacked after the system test?

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

Noone tourist-tested it?

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

congratulations aryanc403

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

Why does a submission of dp memoization gives TLE on C ? but when i simply tabulated it, it got accepted. as far as i could interpret, the TC for memoized solution would be O(10^3 * 10^3 * 5) + O(2 * 10^3). am i wrong here? MY SUBMISSION : 281229405 it contains both memoized rec function and tabulated solution.

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

    You initialized dp array with -1. And it is possible for some state the optimal answer is -1. So here it is recalculating its value again. Initialize your dp array with something else like INT_MIN, it will work.

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

      ohh! thanx. It got accepted. i have got a habit of initializing the dp array to -1. It was such a silly mistake, costed me 100 points and reaching expert in the contest.

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

Can anyone please help me understand why my Java 21 code is getting TLE for problem B? (I tried storing teachers' position in a TreeSet, as storing them in ArrayList and then sorting it was still giving TLE):

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt(), n, m, q, curQ, ans;
        Integer l, r;
        TreeSet<Integer> tSet = new TreeSet<>();

        while (t-- > 0) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            q = scanner.nextInt();

            // Taking teachers position in sorted fashion (works because each position should be unique)
            for (int i = 0; i < m; i++) {
                tSet.add(scanner.nextInt());
            }

            // Running queries
            for (int i = 0; i < q; i++) {
                curQ = scanner.nextInt();

                // Finding lower bound and upper bound teacher positions for current query
                l = tSet.floor(curQ);
                r = tSet.ceiling(curQ);
                if (l != null && r != null) { // Case: between  teachers
                    ans = (r - l) / 2;
                } else if (l != null) { // Case: Only 1 teacher on the left
                    ans = n - tSet.last();
                } else { // Case: Only 1 teacher on the right
                    ans = tSet.first() - 1;
                }

                System.out.println(ans);
            }

            tSet.clear();
        }
    }
}
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Looks fine to me... is Java too slow? Try Java 8 instead?

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

      Sorry for the late reply. It worked with Java 8 as you had suggested! Does this mean we should avoid using latest JDK for competitions, and stick to Java 8? Why is Java 21 slower than Java 8? Thanks again for your help!

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

        I wasn't sure. Your algorithm looked fine, and I guessed java 8 maybe faster or slower than java 21, so maybe worth a try.

        newer versions maybe faster because it includes more optimizations, or it maybe slower because it has more features. so it was really just guessing from my side.

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

Question on B2:

I was expecting a Runtime Error for 281319760 because b[-1] and b[m] are called in some instances but it went through as AC.

However, this 281170767 got a RTE that I was not expecting.

Also, I thought 281319760 and 281318600 have the same time complexity but I got a TLE for the latter.

Could someone please explain, thanks.

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

Would someone be able to tell where this submission is going wrong: https://mirror.codeforces.com/contest/2005/submission/281415974 -- it's almost identical to the tutorial, but I just have dp[i][j] equal to the max score for us using the first i strings. Can't see where it's going wrong, but it seems to be missing something.

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

For problem C, my python submission aligned with the given constraints, but failed because of TLE on test 17. By the way, after the contest, I submitted the exact similar code in C++, and it got accepted.

After the contest, I noticed that every python submission for problem C failed because of TLE on test 17 or test 19.

I personally believe given time constraints aren't enough for Python, and that there's no solution in Python that could get accepted. Isn't it the organizers' responsibility to make sure that this situation doesn't arise?

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

Can anyone please explain me why is my code giving TLE on problem C. Lazy Narek. It is O(N*M) implementation only. Link: https://mirror.codeforces.com/contest/2005/submission/281438234 Thank You!

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

    Resolved, The DP array is typically initialized with -1 out of habit :(

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

MikeMirzayanov Kindly resolve the code match plag I got on my submission 281204323 with the submission of 281203234 as I believe the question was not that tough, and this was just a normal implementation problem, and the code part that matched was pretty standard and not something extraordinary and I received a few WA aswell before the final AC submission, more so is the history with this corresponding user doesn't match with mine as I am unrelated to them. Kindly look into this as my contest is skipped without me being at fault. Thank You.

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

MikeMirzayanov In this round, I got a message that my solution for C coincides with Tashrif2001 which is THIS and with that of puneet_73 which is THIS.

For the coincidence with Tashrif, I do think the solution idea might be similar but the implementations of me and him are radically different. The only thing that might have confused the algorithm here is using similar variable names which are pretty standard variable names. Even if I assume we were connected in some way and changed our code structures then it doesn't really seem plausible to keep the same variable names. So in this case, having similar variable names suggest more of originality than cheating because a cheater who would change the implementation structure wouldn't keep the variable names same.

For the case of Puneet, I do see a similarity on both the idea and implementation. I do want to bring it to your notice that my submission was done before him and if he copied my solution it might be the case that he could have gotten access to it via someone who hacked mine. Here is a screenshot of my conversation with him regarding this matter. So either it is a coincidence or it got leaked to him somehow via hacks because it is hard for me to accept that some so old on this platform doesnt know about hacks. That might as well be a coincidence though.

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

    I also have the same issue, I don't know how even your template is so same both for @Tashrif2001 and @naivedyam. Probably in my room someone had leaked solution could be the case, I am not exactly sure how it is so similar. Regarding the chat and thing u mentioned 'I don't know about hacks...' I just don't want to do pointless discussions with you since you already have some 4-5 contests already skipped which tells the real deal.

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

      I don't think I have 4-5 contests skipped check my profile once again. You are the one with 3 skipped. Last div 4 was unrated that's why it's grey. That's not skipped. One old div 2 did get skipped because of a similar issue (and one isnt equal to 4).Your baltant open lie further strengthens my claim. Moreover looking at the submission timings you were the one to submit after me!

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

        I don't want to run into comment fighting here . This has happened many times tho, someone from room takes code and sends, most of time issues got resolved atleast for me when coordinators looks into deep properly to find who did copying.

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

          If it gets resolved then why 3 skips still? And how come your submission happened after me? It's not possible to get codes that aren't locked from your room and codes can only be locked after you get AC. Which you clearly got after me seeing from your submission time.

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

            2 are div4 skips which weren't even rated so I don't see any point of discussion.

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

              The point of discussion is how is your code leaked from your room when it was submitted after mine?

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

one day i will Qualified to IOI

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

Your solution 281238690 for the problem 2005B2 significantly coincides with solutions rizzler007/281200968, YogeshJangir001/281211809, avanishraj/281212129, Muhammad11/281215249, danger_24/281215997, adambenkhalifa1/281216923, second_acc/281218833, Guddu_100904/281219304, quantumsk/281222916, noman_/281226916, equilibriumionic7/281234512, akp1403/281236473, Abdulrahman_Gaball/281238690, verma_001/281249409. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

[contest:Div2 (Round 972)] i'm so tired from the site every round i lose my rete because your system doesn't fair please i need help for this nonsense . or give me my points again

→ Reply