Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

BiNARyBeastt's blog

Codeforces Round 972 (Div. 2)
By BiNARyBeastt, history, 3 weeks 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
  • +426
  • Vote: I do not like it

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

As a tester, I

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

    codeforcessniper

    → Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    I?

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

As a colorblind tester, what color is your Accepted?

→ Reply
»
7 days 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
»
7 days ago, # |
  Vote: I like it +52 Vote: I do not like it

As a tester, I toasted the round.

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

orz kHarsh3715

→ Reply
»
7 days 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
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally a contest after a long time .

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

after ages...

→ Reply
»
7 days 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
»
7 days ago, # |
  Vote: I like it +9 Vote: I do not like it

nutella testing is crazy!

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

    Why don't it also be Kinder testing :)

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

As a tester,I recommend you to read all problems

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

As a contestant, BiNARyBeastt and Tsovak orz.

→ Reply
»
7 days 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
»
7 days 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
»
6 days ago, # |
  Vote: I like it +1 Vote: I do not like it

After a long time...

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

This one will be cool :D

→ Reply
»
6 days 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
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Scrasse looks nerd

→ Reply
»
6 days 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
»
6 days ago, # |
  Vote: I like it +47 Vote: I do not like it

Who is Tourist tester?????

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

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

→ Reply
  • »
    »
    6 days 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
»
6 days 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
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

For tourist: You for participating!!

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

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

→ Reply
»
6 days 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://codeforces.net/submissions/BiNARyBeastt/contest/1616
  2. https://codeforces.net/submissions/BiNARyBeastt/contest/1713

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

    Yeah, it seems like he did

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

        Idk, I wouldn't have done it personally

        → Reply
  • »
    »
    6 days 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
»
6 days 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
»
6 days 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
  • »
    »
    6 days 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
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem A will be harder then B1 and B2

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

crazy speedforces it is

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

Great to see no more sex images!

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

orz kHarsh3715

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

chess battle advanced

→ Reply
»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Da ana Msr 7bibty

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

A contest after so00 long but clashing with leetcode biweekly

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

The score distribution of this contest is really unique!

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

can anybody explain what is sub task?

→ Reply
»
4 days 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
»
4 days 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
»
3 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Is it rated????

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

Why am I unable to register as unrated participant?

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wish to cross 1800 rating today

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

.

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    That cant happen because then the teacher would catch david

    → Reply
    • »
      »
      »
      3 days 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
      • »
        »
        »
        »
        3 days 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
  • »
    »
    3 days 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
  • »
    »
    3 days 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
»
3 days 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
»
3 days ago, # |
  Vote: I like it +37 Vote: I do not like it

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

→ Reply
»
3 days 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
»
3 days ago, # |
  Vote: I like it +14 Vote: I do not like it

dp forces

→ Reply
  • »
    »
    3 days 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
»
3 days 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
  • »
    »
    3 days 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
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is the solution for A?

      → Reply
      • »
        »
        »
        »
        3 days 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
      • »
        »
        »
        »
        3 days 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
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got 5 WA for me it still 400

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

    Got my a** handed to me in A itself

    → Reply
»
3 days 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
  • »
    »
    3 days 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
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is dp, right?

→ Reply
»
3 days 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
  • »
    »
    3 days 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
    • »
      »
      »
      3 days 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
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got tle because I sorted it in every query…

    → Reply
»
3 days 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
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Again this happend

→ Reply
»
3 days 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
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B isn't related to math

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

    Atcoder problems ig

    → Reply
  • »
    »
    3 days 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
»
3 days 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
»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 days 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://codeforces.net/contest/2005/submission/281250930

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

→ Reply
»
3 days ago, # |
  Vote: I like it +7 Vote: I do not like it
Meme
→ Reply
»
3 days 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
  • »
    »
    3 days 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
»
3 days 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
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 days 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
    • »
      »
      »
      3 days 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
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes

        → Reply
        • »
          »
          »
          »
          »
          3 days 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
          • »
            »
            »
            »
            »
            »
            3 days 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
            • »
              »
              »
              »
              »
              »
              »
              3 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Why they need to be in sorted order ?

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

                read my first cmnt all same character should be together

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

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

    → Reply
»
3 days 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
  • »
    »
    3 days 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
  • »
    »
    3 days 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
»
3 days 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
»
3 days 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
»
3 days 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
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What wrong in my recursive dp solution for C 281249632

→ Reply
»
3 days 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
  • »
    »
    3 days 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
»
3 days 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
»
3 days 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
»
3 days 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://codeforces.net/contest/2005/submission/281216208

→ Reply
  • »
    »
    3 days 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
  • »
    »
    3 days 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
»
3 days 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
  • »
    »
    3 days 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
    • »
      »
      »
      3 days 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
      • »
        »
        »
        »
        3 days 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
        • »
          »
          »
          »
          »
          3 days ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          from the problem statement

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

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 days 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
              • »
                »
                »
                »
                »
                »
                »
                »
                3 days 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 days 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 days 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 days 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
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 days 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
»
3 days 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
  • »
    »
    3 days 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
    • »
      »
      »
      3 days 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
      • »
        »
        »
        »
        3 days 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
        • »
          »
          »
          »
          »
          3 days 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
          • »
            »
            »
            »
            »
            »
            3 days 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
            • »
              »
              »
              »
              »
              »
              »
              3 days 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
              • »
                »
                »
                »
                »
                »
                »
                »
                3 days 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 days 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 days 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
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that this time the problems are so hard

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

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

    → Reply
  • »
    »
    3 days 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
»
3 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate dp very much

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

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

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

dp contest(C,D,E1)

→ Reply
  • »
    »
    3 days 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
    • »
      »
      »
      3 days 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
    • »
      »
      »
      3 days 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
      • »
        »
        »
        »
        3 days 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
        • »
          »
          »
          »
          »
          3 days 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
»
3 days 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
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

nice contest

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

cute round

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

This was a really fun contest!

→ Reply
»
3 days 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
»
3 days 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
»
3 days 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
»
3 days ago, # |
  Vote: I like it +8 Vote: I do not like it

I'm not allowed to see the Editorial !?

→ Reply
»
3 days 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
»
3 days 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
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    NVM , had to optimize the implementation

    Accepted submission: 281307789

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

A bit low-quality

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

I finally got CM!

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Noone tourist-tested it?

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

congratulations aryanc403

→ Reply
»
3 days 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 days 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 days 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 days 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
  • »
    »
    32 hours 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 days 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
»
45 hours 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://codeforces.net/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
»
43 hours 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
»
37 hours 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://codeforces.net/contest/2005/submission/281438234 Thank You!

→ Reply
  • »
    »
    37 hours 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
»
31 hour(s) 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
»
31 hour(s) 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
  • »
    »
    30 hours 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
    • »
      »
      »
      30 hours 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
      • »
        »
        »
        »
        30 hours 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
        • »
          »
          »
          »
          »
          30 hours 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
          • »
            »
            »
            »
            »
            »
            30 hours 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
            • »
              »
              »
              »
              »
              »
              »
              29 hours 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