mainyutin's blog

Codeforces Round 938 (Div. 3)
By mainyutin, history, 3 weeks ago, translation, In English

Hello! Codeforces Round 938 (Div. 3) will start at Apr/08/2024 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

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

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

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

Problems have been created and written by our team: mainyutin, vmanosin7, ssor96 and ZergTricky.

We would like to thank:

  1. Vladosiya for help with ideas and great coordination of the round;

  2. FairyWinx, sevlll777 for red testing;

  3. ace5, Nickir, senjougaharin, vladmart for yellow testing;

  4. natalina for blue testing;

  5. bitthal04 for cyan testing;

  6. Alequisk, Mohamed_Hesham for green testing;

  7. MikeMirzayanov for Polygon and Codeforces platforms.

Good luck!

UPD: There was an issue with the validation of hacks for problem G, but it has now been resolved. All successful hacks will be rejudged. Pretests were not affected by the issue and remain unchanged.

UPD2: Editorial is out.

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

»
3 weeks ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

yay div 3!!!

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

    do just rating++)

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

    spoiler hopefully i get 1200

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

      i am new here , i participated in this round and my current rating is around 800 , but now this contest is showing as unrated on my profile . i dont get it , it clearly says -"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."

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

        It will take some time for ratings to change

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

        Don't worry! The rating calculation hasn't been completed yet. And there seem to be some issues with Problem G, so the rating update for this round may be further delayed.

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

authors pic??

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

mainyutin orz

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

No pics with pizza.

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

Experts be like: I'm out of competition (つ▀¯▀ )つ

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

I appreciate the creators' effort on this div.

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

Is that a gan cube :o

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

Let this be the round where i shall become Pupil under the Heavens .

It's divine Conviction that i shall fulfil.

In the name of all mighty Behelet behold my Pupil Rank

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

Good luck to everyone! I'll sadly have school but I'll find a way to participate since cf >>>>>>>> school

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

i think it's time to give it a try to change my color

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

Very Saaaaaaaaad
I am not participating :(

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

Hope to be pupil after this contest

Good Luck!!!!!

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

    i am new here , i participated in this round and my current rating is around 800 , but now this contest is showing as unrated on my profile . i dont get it , it clearly says -"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." , can you please explain what am i missing.

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

Hope to be specialist after this contest

Good luck to everyone!

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

Authors' photos again!

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

Hope I can get back to my real rank of pupil

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

hi everyone, mwah. i love yall. happy contest day! wish you good luck. mwah. (please downvote me)

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

should i participate or nah?

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

OMG! Another mainyutin round ...

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

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

Back to Expert

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

    Bro did a manifestation

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

      lmao

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

      Bhai it's IQ 69. If you have a bad performance in div2 and you are becoming a specialist from Expert and the next contest is div3. Let the rating fall. At least div 3 will be rated.

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

Why ppl are lately participating comparitively less in contests? I remember seeing 40k registered_participants and 30k actually_participants! (not a long ago) But nowadays it's hardly 20k ppl

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

    Well I bet some people had spring break last week, this week they're back to school.

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

Queue is too big.

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

queuedforces :noo:

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

long queue

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

The site is unusable for today's round,i have been waiting for 10 min to submit,it keeps loading.

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

I am sorry but The queue is too annoying today.

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

    then just switch to another problem

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

      That doesn't affect the fact that the queue was still too long

      Also being able to get feedback that your answer is correct/wrong in a short amount of time is important in a format where speed is necessary, since it overpenalizes answers that fail the tests since you could be working on a different problem only to return to see that you WA'd on the problem you left

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

        well then check the solution yourself before going to another problem

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

hope rated

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

this comment is in queue

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

For once, I won't believe that my poorly optimized G could survive, so guys, please hack my G submissions till TLE XD

Nice contest overall. I was infuriated by H at first since I skipped a crucial line in the statement, yet after that the problem was really nice, huge kudos to its setter.

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

    My inexperienced self tried pretty hard, but sadly could not even get close. :(

    Actually, isn't the worst case a highly composite number like $$$720720$$$ or $$$360360$$$? Then how did it get so close to TL (your solution passed my worst case test in about 1.5 seconds)?

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

      Honestly I couldn't think of anything better than what you just stated. This is weird.

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

        Maybe since a lot of numbers are the same in my testcase, the compiler magically optimizes stuff away? Or another reason might be that the server is slower during contests as opposed to during the hacking phase (I'm probably wrong about this one, if anyone knows about what difference there is, please enlighten me)?

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

          Your first theory actually made sense, since caching, in regular cases, could be considered a CPU trait, and that would help speeding up if your testcases are identical.

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

    Nice idea, I believe most of the time is wasted on (re-)allocation of visited, if you make it static I believe it would be a massive speed up.

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

      Just duct taped my code again and it actually worked: 255770022

      Thank you, another thing to remember for future implementations.

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

        Not as massive as I expected. This is more like it should be :)

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

          Is there an explain for this solution?

          Edit : Got it 255813710

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

          Just got the time to have carefully reworked my codes. Putting stuff to global static, queueless the BFS, etc.

          This should be good now, and the runtime is already covering some hacks.

          255814613

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

      how come there is such a big gap between this two implementation? (reallocation and looping reset visited) Isn't both operations O(n^2)?

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

nice problems

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

Ahh! I just figured out how to optimize my solution for E.

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

    same man just did D, uploaded the file and submitted with 40 secs left,the submit didnt even register somehow!

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

    can you explain your solution please

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

      Given the constraints of the problem statement, it suffices to code a solution that works in O(N^2) per test case. So, we can brute force over all n to find the largest possible k that can change the characters to 1's.

      How do we find out whether this can be done for some k?

      If s[i] is '0', then we must flip s[i...i+k-1]. From i=n-k to n-1, we can't create anymore flipping segments. Therefore, after performing some operations, we can check whether s[n-k...n-1] is only 1's. Iff so, then k works.

      Of course, flipping each s[i...i+k-1] is O(k), which is slow. Instead, find out how many times s[i] has been flipped. Let this be flips. This can be done using a deque D: whenever s[i] is '0', flip everything from i...i+k-1 (increment flips) and push i+k to D. If i is in D, decrease the current number of flips (decrement flips).

      For the remaining k values, check if s[i] = '1'. We follow a similar procedure as before. To check if s[i] is '1', check if flips is even or odd. If it is even, then s[i] did not change. Otherwise, it clearly changed. If i is in D, then decrement flips (as this was an endpoint like other flips).

      I hope this explanation makes sense.

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

RIP python users for F

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

    Why?

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

        Spoiler

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

          Tell other method pls

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

            Hint 1

            Hint 2

            Hint 3

            Solution

            Code

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

              Thanks broski for writing this, I appreciate it.

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

Can anyone please give a test case where my D solution will fail?

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

    How do you handle this case?

    1
4 3 1
9 9 9 1
4 3 9
    Your code answer
    The right answer
    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this giving a runtime error? My code works when I test it myself

Submission: 255757485

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

    You have an out of bounds array access on line 30

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

B is harder than F.

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

    I guess not, just do what is asked, nothing tricky is there.

    only need to be careful about the conditions that matrix you form should be consistent from every path you choose to build it from.

    update: corrected a typo

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

    Think out of the box and B would be really easy.

    Take the minimum element of $$$b$$$ is a new $$$a_{0,0}$$$, then construct $$$a$$$. Sort $$$a$$$ and $$$b$$$, and we'll now only need to check if two sorted lists are identical.

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

    Trying to compare B and F is so weird because they're so different since B is a "just code it" problem and F is a logic problem, but I definitely agree with this opinion since F is guess forcable and one of the integers isnt even that relevant (namely 4)

    If they increased the integer maximum to be 8 I'd think that would make it a reasonable F problem

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

I think F should come before D. He's too easy in that order!!!

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

    how to solve F, i have some idea, but was afraid of lot of case work solution so did not went ahead with my intuition

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

      int main() { int tc; scanf("%d", &tc); while(tc--) { int a0, a1, a2, a3; scanf("%d%d%d%d", &a0, &a1, &a2, &a3); int ans = a0/2 + a1/2 + a2/2 + a3/2 + (a0 % 2 & a1 % 2 & a2 % 2); printf("%d\n", ans); } }

      Check this solution.

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

      I just followed the instructions step by step 255749602 (Maybe I'll get hacked).

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

        you actually did what I was afraid of during contest, hats off.

        how to be confident when writing casework solution, How to let go of this fear what if i miss some condition...

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

          Apart from the computable parts (like time complexity) the rest is up to luck, I keep missing some condition which leads me to 8 WAs in C and E.

          I'm not sure if I've got the right answer. I can't prove that my solution is comprehensive anytime soon, I just pray that he is.

          Confidence is something that is affected in many ways, with Codeforces Round, just code what comes to mind, short time don't allow to think too much, you should think about the comprehensiveness of the solution at the end of the round.

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

      you can just do dp[201][201][201] for first 3 numbers and 4th number is independent so just add d/2 in answer.

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

Can someone explain why 255755491 gets TLE for problem D. It should be O(nlogn),right?

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

    Briefly reading your code, I see that you used multiset::count.

    However, a quick google search shows that:

    The time complexity of the multiset::count() function is O(K + log(N)), where K is the total count of integers of the value passed.

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

      That could be it. However, I submitted the same code(255759509) with C++20 and it passes now in 452 ms. UPDATE — Read the comment below

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

      Thanks for the help.multiset .count() was indeed the problem ,i replaced it with multiset.find() and it passes now. Code- 255761397

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

Video Solutions for all problems:

Video for A-D: Video for E-F: Video for G-H:

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

what a intresting problem H, sadely could not solve it,

can someone share the hints for it?

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

    First, lets try to solve an easier version of this problem:
    Ignore "However, each $$$r$$$ can only be used for at most one tower."

    Solution

    Going back to the main problem:

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

      I completely missed that little detail about unique radius, but wasn't in time anyway.

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

      You can just do bitmask dp in O(nm2^13)

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

      did not know about this hungarian algorithm, will definately learn about this

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

Is the intended solution for G not this: Brute for all factors of gcd(a[0][0], a[n-1][m-1])?

If it is, why is the TL so annoyingly tight?

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

    I also tried that and got absurdly close to TL. I even thought that I might have made some idiotic implementation error to have the execution time ramping up...

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

      Fr it was so annoying, I submitted G, confident that it passes, and started coding F. 5 mins later I go back and see, tle on 24 🤡. Then I do some changes, submit, come back and see tle 🤡 Then finally I get it too pass, but it takes close to 2900ms and will get hacked 🤡

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

    I was doing bfs using queue and for some reason it was taking a lot of time. Changing it to simple dfs made the runtime to only 296 ms. For your case however, i think your precomputation of factors is taking a lot of time.

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

    I think that is the intended solution — 255735337

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

    My $$$O(nm\log^2(A))$$$ solution uses 1/10th of TL

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

    My this solution passes in TL easily

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

contest shows how many problems with greed code that i can't write XD

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

Is this solution to G hackable. I stored all possible values of the gcd at cell $$$(i, j)$$$. I think it should work because there are at most $$$\log A$$$ values of the gcd on a path. Code:255759157

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

Can H be solved using maximum weight bipartite matching? I also used the observation that no tower would have $$$r > 20$$$, was this a wrong assumption?

Update: After looking at some other comments, I think I got the issue with my solution.

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

A nice competition!

I enjoy it!

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

https://codeforces.com/contest/1955/submission/255756584

could anyone tell a counter test case where this fails for D

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

Nice contest. Problems were good. Thanks for the round mainyutin vmanosin7 ssor96 ZergTricky and all testers.

Also, congrats Geothermal on back-to-back wins!

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

div 2.33

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

Was the statement for problem A silently modified during the contest? More specifically, was the word "exactly" added or did I just miss it.

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

    Dude I can swear there wasn't the word "exactly" when I first read it, maybe I just missed it...

    Also I was mistaken at the term "a promotion", I thought that it can only be used once, but turns out I can use it multiple times. Got 2 WA on problem A lol

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

      Seems like we just missed it... I checked a video and it did say exactly from the beginning. The only difference was that it wasnt bold.

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

Using a segtree on problem E be like

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

    What's the solution for problem E?

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

      Basically since $$$O(N^2)$$$ passes, you can test every possible $$$K$$$ from $$$N \rightarrow 1$$$ and return the first one that works. This step runs $$$O(N)$$$ times. The question is now: how do you check if operations of size $$$K$$$ can turn a string to all 1s?

      First, notice that since this is just an XOR these operations are both commutative, associative, and their own inverse. So there's no point in applying the same operation to the same substring more than once.

      With that, notice that if $$$s_0 = 0$$$, there is only 1 operation we can and must perform: invert {$$$s_0 ... s_{k-1}$$$}. Inductively, it is sufficient for us to apply the operation only when the first element in the operation is zero. This step runs also in $$$O(N)$$$, bringing our current total to $$$O(N^2)$$$.

      The final step is figuring out how we can apply the operation very quickly. If we prefer typing or templates to critical thinking and reasoning, we can just use a range update / point query data structure like a Segment Tree, Fenwick Tree, Sparse Table, etc. I did this in during the contest 255770625 and made sure to statically allocate my segment tree instead of using std::vector so I didn't get hacked. I also manually coded this because I enjoy a nice hand-crafted segment tree (brainrot).

      However, instead of that beautiful solution, we can do it intelligently by inverting in $$$O(1)$$$ on the fly by keeping track of whether or not we are inverting, and then setting a reminder $$$K$$$ indices ahead to remember to start un-inverting. I did this after the contest 255903468.

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

Problem G and H are enjoyable. Enjoyed how there was such a simple solution to G if you made the appropriate observation. And problem H was very interesting, I implemented a dp bitmask, but some reason still getting WA on test case 4. I think I may have small bug, but I think the approach is correct.

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

can someone please tell me why this 255705783 is WA test 1 when I run it locally it gives me the correct output, furthermore when I switch the compiler to c++17 it gives TLE test 3 this time, maybe it's smth abt c++20 that I don't know ?

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

255760248 Why does this submission exceed TL ? I think the complexity is $$$O(n\cdot(n\cdot \log n))$$$

I realise this is most probably not the intended solution. But if it helps to understand the submission, I have just tried to go over all possible $$$k$$$.
Used PBDS for calculating if a current position has been previously flipped an even or an odd number of times.
For each $$$k$$$, considering all previous operations that have modified a position, I have never flipped a position that is currently a $$$1$$$ and always flipped a position that is currently a $$$0$$$.

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

    IMO $$$\mathcal{O}(n^2 \log n)$$$ is a very dangerous complexity for $$$n = 5000$$$, and I would not gamble on it even with 3s TL.

    Used PBDS for calculating if a current position has been previously flipped an even or an odd number of times.

    You could actually improve this part by using a queue instead of a PBDS.

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

      My $$$\mathcal{O}(n^2 \log n)$$$ solution got AC and ran in under a second with Fenwick Tree. 255763784

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

      Thanks for answering. I was also guessing that PBDS is going to cause TLE even if $$$O(n^2 \log n)$$$ could have squeezed past the TL. Thanks for the queue insight too. I realised I know nothing about queues :)

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

        The only thing I could suspect is that PBDS is already a high-coefficient $$$\mathcal{O}(\log n)$$$.

        For the queue stuff, just imagine this assuming we're trying length $$$k$$$: store the starting points of all flipping segments in the queue, then when investigating index $$$i$$$, any starting indices up to $$$i-k$$$ has no value. Why a queue? We're iterating indices in ascending order, and added index would later be invalidated in that same order as well, which fits the FIFO nature of a queue.

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

          Yeah, makes much more sense now. Thanks a lot and welcome back to CF contests.

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

    I used PBDS for calculating if the current position has been previously flipped an even or odd number of times. Here's my submission.

    I later realized we insert indices in a monotonically increasing fashion in the data structure we maintain. So we can also use vector/queue. With vectors we can use lower_bound and with queue we can pop the indices that are at a distance k of far than current k.

    Vector solution: here Queue solution: here

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

      All submissions you've linked are in queue at the moment lol.
      But, yeah lesson learnt. Don't be lazy and use sets everytime you want a sorted list.

      I later realized we insert indices in a monotonically increasing fashion in the data structure we maintain

      Now that you have put it this way. Its baffling how obvious this was and yet I missed it.

      Want a sorted list. Want integer-positions. PBDS. TLE. Die.

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

        Yeah it was pretty obvious but even I wasn't able to come up during contest so I did it using ordered set. It was only after contest when I realized it can be accomplished using vector.

        And as AkiLotus mentioned, queue can be used to eliminate the logarithmic factor and achieve a linear solution.

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

can anyone explain the idea to solving D?

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

    Sliding window. Just check for every segment of length m if there are atleast k elements in that segment that are present in b. Count can be maintained using a map.

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

I failed to see the key observation that GCD must be a divisor of both top-left and bottom-right corners, so I ended up solving a more general version of the problem which finds maximum gcd for each path from top-left corner to cell (i,j). Tbh it was a good problem to practice some prime optimizations although it was not intended.

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

bro my computer crashed during the contest and my coding software was deleted (dunno why) and any custom invocation would take more than 7min (dunno why) so i just had to randomly code on the submission site ToT

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

    I usually use the one from AtCoder, it runs the code and gives the result faster than Codeforces most of the time.

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

    use online compiler like online GDB or other there are many options and they are fast

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

what's wrong with my c ? pls check[submission:255762443]

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

F should be in place of B didn't read it during contest

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

Extremely easy problem F!!!!! -_^

include

int main() { int tc; scanf("%d", &tc); while(tc--) { int a0, a1, a2, a3; scanf("%d%d%d%d", &a0, &a1, &a2, &a3); int ans = a0/2 + a1/2 + a2/2 + a3/2 + (a0 % 2 & a1 % 2 & a2 % 2); printf("%d\n", ans); } }

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

Spent half contest time to implement the simulation for problem C, couldn't make it but still a great experience.

Thank you guys for a nice contest!

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

I just realised problem G is but a simple BFS ToT

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

I have an ask for harder version of $$$G$$$ , same constraints , just your starting cell can be any cell inside the first row and finishing cell can be any of the last row , then how to solve it?

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

    How is that any different? Just run dfs from every cell in first row instead of first and check if any cell is visited in last row instead of only bottom right.

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

Problem G is the same as https://community.topcoder.com/stat?c=problem_statement&pm=16140&rd=18085. Of course, it's not as big of an issue as Div 3s are supposed to be educational anyway, but just putting this out here :D

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

Can binary search be applied in E to make TC roughly NlogN

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

    No, because function is not monotonic. For example, s=000 k=3 is possible, while 2 is not.

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

    I don't think the function is monotonic

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

Why using qsort (C/C++) in B can be easily caused by Quicksort hack halyavin.cpp to cause TLE (e.g. 255659588) ?

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

    It's the nature of quicksort algorithm itself to have $$$\mathcal{O}(n^2)$$$ worst case time complexity, thus as long as you know the sorting was a pure quicksort and you know how the pivot was chosen by the library, you could always counter it.

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

How to E

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

    bruteforce + greedy

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

      How to check if k is valid

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

        well you have to choose some subarrays of size $$$K$$$ to invert and subarrays do have a unique starting index and so you put inversion on an subarray starting from a particular idex at most $$$once$$$ so you start from the beginning , on your current index the value of the character in string is fixed so you can choose that index as starting point of a subarray or not(which is a certain choice), so if you do inversion the cost of that ends $$$K$$$ indexes later and if it's valid it will be at $$$\le n +1 $$$ and if valid you move on to the next index to check validity again otherwise invalid proved

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

Can anyone suggest a tc where this fails for problem D :(255769513

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

    1 4 3 2 1 1 2 2 2 2 2

    Output should be 1

    Spoiler

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

can anyone explain this solution to problem E? i fail to understand how we are checking if integer k is valid or not.

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

submission1 submission2 Why they are giving different answer? The only difference is in the solve() function only. Is this a CPP Bug or I missed anything? mainyutin

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

    It may not be a reason actually, but most likely it is because you are not clearing your dp after/at the start of the next testcase

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

Can anyone tell me why my code of problem C 255769305 is giving TLE on testcase 3. I thought deletion in deque is O(1).

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

    The time complexity of your code is O(min(s,k)), s = sum of durability of the ships. As s and k might be too large (k <= 10^15, for example), it would give TLE.

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

    your solution time complexity is min(sum of all the element, k) which in worst case can go upto 2e14 like your are just simulating the process which is not optimal

    required optimisation — in the while loop of q.size() and k

    take the min of q.front() and q.back() if 2*mn <=k do this {

    then reduce mn from front as well as back of deque then if q.front==0 do pop_front() and if q,back()==0 do pop_back()

    } else break;

    now if d.size() is greater than 0 check can we remove the first element (value should be <= (k+1)/2 if yes pop_front() do same for last element if it exist (<=(k/2))

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

I spent really a lot of time during the contest trying to make my E solution faster, even though it should have O($$${n^2}logn$$$) complexity, which is with n <= 5000 should pass the 3 second limit. The only thing that helped me was changing long long to int, but even so, it's still very slow. Does anyone have any idea why my E solution is so slow (below is the final one)? And a similar question is about D as well, because I can't see any clear reasons why it is so slow:

E: 255741981
D: 255675779

Edit: Sorry about how code in E looks like, I don't know why it shifted, because for me it was totally normal when I was sending it.

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

.

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

    I too felt the cheating happened in this contest a lot, my rank was around 160ish before 1 hour end of contest, and i could not solve anything further was only able to solve 5(A-D and G) but somehow so many other peoples solved problems that my rank went to 700+, i was thinking maximum i can slide is around 300-400 but 700+ did not feel organic... I might be wrong but this is what i feel.

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

      I feel like especially in the last 8-10 minutes, the spike of "AC'd" submissions shot up.

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

      Bro this is common if you cant solve good problems , you solve the easy questions fast it doesnt mean that the people below you cant solve the tough one faster than you that happens everytime , the people who have much more knowledge will eventually occupy the rank

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

pray for me to reach pupil ^_^

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

Great Contest!!! Very nicely framed

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

does unsuccessfull hack have panalty in this round,

I tried to hack some solution, but failed will my score be affected by this?

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

Was the cpp's hash function mechanics of unordered_map changed recently ?

cause i can't seem to hack solutions using the default unordered_map like before .

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

Can someone tell How can we solve G using bfs I was first storing the factors of the last number and then I was doing dfs and each time i find a new pair of gcd between two colunms then I am checking it to be divisible by a factor of last number . Help needed !!!

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it
    1. store the factors of gcd(matrix[1][1], matrix[n][m])
    2. do dfs / bfs
    • check if (current_number % factor != 0) return false;
    • else complete checking the next till reaching matrix[n][m]
    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Getting a tle by applying this on 35th testcase

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

problem D first I used map for frequency and I got TLE I removed the map and I used a simple global frequency array but with t 1e4 and the frequency array being 1e6 it is not possible so what should I use here in this case?

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

    you can use same frequency array but you zero it at the end of a testcase using only values in a and b . or you can use an map with custom hash

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

      thanks the first one worked, I actually used a multiset for array m and used count() many time so maybe that's why I got TLE the problem is not in using map here because many people used map and it passed

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

Toooo many hacks for G.

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

you may want to rejudge G with a higher time limit, except you had a better intended solution

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

    No I believe intended solution was O(d(maxA)*n*m) ,where d(n) is number of divisors of n , which easily passes the time constraints .

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

Many people were hacked on G.

Poor pretest.

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

My 320 hacks on G were about trying to achieve maximum number of possible GCDs for as many cells as possible, so that solutions that hold all GCDs using a slow data structure such as std::set will insert a lot of elements. My test made it more than a million elements per test case, and since we can have 20 of 100*100 tests in a single file, these solutions tried to insert more than 20M elements in total, leading to TLE.

But it seems like there are far more intense cases, as even my possibly more optimized solution couldn't pass, as well as several LGMs' solutions, and now with all the Unexpected Verdicts we can assume even testers' solutions are hacked...

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

It seems that E is more difficult than F.

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

Can someone hack my solution in E? 255743941

it's O(n³) with an optimization

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

G is so humorous!!!

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

what a sight. seeing Geothermal losing and regaining his high ranking after the contest

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

It seems that the validator for problem G is wrong. The problem said that the sum of n * m cannot exceed 2 * 10^5, but it can be hacked with such data.

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

    can you give a submission for a reference?

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

      Try mine, it will RTE#2226 in cases of violation.

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

        hey, also look at mine, it's gonna FST https://codeforces.com/contest/1955/submission/255724529

        The authors should change 2e5 to 1e5, and almost everyone with a logn factor passes

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

          FST for sure, see this comment for countertest ideas. There are better solutions than that.

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

            idk, why the testors had to make the problem so tight, and if yes, then they should have added this in pretests, i had a better solution in mind, but as this one passed, I wasn't bothered to submit another

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

              I don't know either, strict TL isn't a first-time thing. I also got TLE on another "better solution" as well, and that was because of suboptimal alloc. Though, on hindsight, 2e5 usually is a vanilla constraints, so I do feel like them brushing it off is a normal instinct.

              By the way, your earlier one won't pass, I just resubmitted to check and make sure — it still fails a test within limit.

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

                yeah, as i said, it's because of the log factor, if the constraints are relaxed, mine might pass.

                btw, yours is working?

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

                  Yeah, kinda — see the link I left on the first comment of this chain.

                  (I won't count tests from 36 and beyond as they breached the $$$2 \cdot 10^5$$$ limit for sum of all $$$nm$$$.)

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

Validate is wrong. cpp #include <bits/extc++.h> using namespace std; int main(void) { ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr); size_t constexpr T=30; cout<<T<<"\n"; for (size_t t=0;t<T;++t){ cout<<"100 100\n"; for (size_t i=0;i<100;++i){for (size_t j=0;j<100;++j) cout<<114514<<" \n"[j==99];} } return 0; } This passed the check.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it 
    #include <bits/extc++.h>
using namespace std;
int main(void) {
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    size_t constexpr T=30;
    cout<<T<<"\n";
    for (size_t t=0;t<T;++t){
        cout<<"100 100\n";
        for (size_t i=0;i<100;++i){for (size_t j=0;j<100;++j) cout<<114514<<" \n"[j==99];}
    }
    return 0;
}
    → Reply
»
3 weeks ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

What is this ? I precalculated divisors for all elements upto 1e6 ( in MlogM time where M = 1e6 ) and solved the overall problem in (approx) cuberoot(1e6) * 1e5 time , still hacked ? solution

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

The time complexity for the Python judge is not being properly set.

I got TLE at test 3 for my submission in python (submission no — 255718411) I got accepted for same code in Pypy 3.6 (submission no — 255806654)

Due to this , I have made additional 2 negatives. It's NOT FAIR If you want you can check in my recent submissions

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

    Your Python submission and PyPy3 submission have different code. What are you complaining about? The Python one uses list.insert that is $$$O(n)$$$, and it's $$$O(n^3)$$$ in total, so I think TLE is the correct verdict.

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

      Just go to my profile and click on submissions and just click on show unofficial submissions and then check last two submissions (255848468 and 255848184)

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

So qsort is a poor way to solve cf problem? Since it can be hacked easily. I did not even imagine that qsort in stdlib have a O(n^2) situation, I thought it should have some method to prevent it from happening because it is in Standard Library! Forcing me turn to a cpp programmer? My rating is gonna drop for this ridiculous reason. ahhhhhhhhhh X(

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

    But I think write C in C++ is not a big deal.

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

    You can implement your own sort and copy it if you're committed to using C .

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

    It's not stdlib's fault. It's the algorithm's fault itself, as it has slow worst cases, but average cases being so fast that it is commonly used; yet in an environment where hack is allowed like Codeforces, worst cases actually matter.

    Perhaps making your own sort next time? IMO implementing something like merge sort isn't even much more difficult.

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

Can anyone explain G? I thought this is a simple standard Dijkstra algo to keep track the GCD for each path with PriorityQueue?

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

    Any path must start at (1,1) and end at (n,m) , therefore the gcd of the path must be a divisor of both. Simply check for each divisor if it could be the gcd using dijkstra or bfs.

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

    Your approach is wrong though. A greater GCD on a node won't guarantee greater GCD at the end, in case that GCD was a large but obscure number, which would quickly get diminished later on, while the smaller GCD prevailed.

    An example:

    1
3 3
684 342 18
228 19 6
12 6 684

    If you take $$$19$$$ as the GCD to go for cell $$$(2, 2)$$$, two $$$6$$$ on both possible ways onward from it will delete them all and result in a GCD of $$$1$$$ at the end.

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

      Sorry I still not get it. https://codeforces.com/contest/1955/submission/255758743 is mine.

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

        I did give a bad test to straight-up testing honestly.

        Found your counter test though, and it looks even weirder.

        1
2 2
84 84
56 48

        How come it outputted $$$4$$$? (supposed answer is $$$16$$$).

        I have a feeling that your code overwrote GCDs in a weird manner, leading to only one GCD being chosen and it's hard to tell when it's optimal or not.

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

      When 684 342 19 6 684 then the tracked GCD becomes 1 and stay in the bottom of PQ. And other higher GCS in the other path can be considered in the next run.

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

Firstly I would like to acknowledge the contest author's effort and thank them. Now I can began my issue with the contest.

I think the statements for problems could have been more clear considering this is a Div 3. Also the explanations for the samples wasn't there or was not even helpful at all. I know that the author is not duty bound to explain the samples but with poor statement explanation I think this should have been done.

I did quite bad in the contest and to check whether I was feeling these issues because I did bad, I slept this off. Now even in the morning I feel the statements could have been better with better sample explanations.

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

It is so surprising to see so many G solutions are hacked. Given that my rather standard DP solution https://codeforces.com/contest/1955/submission/255745682 is accepted just fine, now I wonder whether I have missed something important, like a more advanced approach that usually works better.

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

    The moment bro drew attention to himself...

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

    Lmao

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

    this can also be hacked sadly, I wrote similar solution and many more similar solution is hacked already.

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

      Now it makes more sense. It appears that the hack used 200 tests of 100x100 matrix, with the sum of n*m being 2000000 which is 10 times of the limit as specified in the problem statement. So it is likely an invalid hack.

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

    Hacked :)

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

      There are tests added by hack, like Test #50, contains 800 sub-tests each with 100x100 input, with a total sum of n x m 8000000, which is 80 times of the upper limit as promised in the problem. Now the whole thing become less interesting due to these invalid hacks.

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

Very good topic, each level is easy to difficult. Thank you

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

Can Someone Please Try to hack this: https://codeforces.com/contest/1955/submission/255768412

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

The problemset was good no cap. but it's really sad to see so many solutions being hacked. There's a lot to improve in testing.

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

so，is it rated？

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

fvck G

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

Wow... with what happening in G, I feel quite disappointed.

I could accept my code TLE'ing due to bad implementation caught in stresstesting, but allowing hacks to let loose because of validators going nuts?

Please, problemsetters, be extremely keen in validator writings. Crosstest and add various validator tests if possible. This is not even the first time in a long while this happened, and this problem even has pretty standard constraints that one shouldn't excuse of difficulty in writing conditional checks, so why letting the issue prevail?

I don't really want to disrespect the authors, the problems themselves are fine, but this time the underneath preparation has an absurdly critical hole that I feel like I need to raise my voice.

Proof that hacks go out of problem statements' defined boundaries, solution RTE with exit code 2226 is my personal indicator when that happens.

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

    The bad thing for me in the contest is, that I solved G directly after D, a similar solution like Geothermal, yet got hacked. The good thing is I participated in VC :)

    still I think the contest should be unrated as people who solved G directly after D would be paying prices otherwise :(

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

      I think this will depend on what actually had happened underneath. The best cases would be that only hacks having those breaches, thus those tests could be removed, relevant hacks reverted, and contest rated as usual.

      If even the original testset had limit breaches, then nope, unrated for sure (though as I quicktested the original testset was fine).

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

        If we can remove those hacks and solutions can be rejudged then why not, that would be better

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

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

unrated

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

How come this test case passed for Hack

*******************************
*** The hack uses generator ***
*******************************

** Command line arguments **
no arguments

** Generated test **
999
100 100
100000 99998 99996 99994 99992 99990 99988 99986 99984 99982 99980 99978 99976 99974 99972 99970 99968 99966 99964 99962 99960 99958 99956 99954 99952 99950 99948 99946 99944 99942 99940 99938 99936 99934 99932 99930 99928 99926 99924 99922 99920 99918 99916 99914 99912 99910 99908 99906 99904 99902 99900 99898 99896 99894 99892 99890 99888 99886 99884 99882 99880 99878 99876 99874 99872 99870 99868 99866 99864 99862 99860 99858 99856 99854 99852 99850 99848 99846 99844 99842 99840 99838 9983...

** Generator source **


t = 999
n, m = 100, 100

print(t)

for k in range(t):
    x = 0
    print(n, m)
    for i in range(n):
        for j in range(m):
            if (j == m-1): print(100000)
            else: print(100000 - x, end = " ")
            x += 2

This is 1000*100*100 well beyond limits

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

Any idea why this code gets TLE on problem D ?

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

    the time complexity of multiset::count is $$$O(n)$$$, not $$$O(\log n)$$$

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

      To elaborate on the above comment, it is $$$\mathcal{O(k + \log n)}$$$ where $$$k$$$ is the number of occurences of the sought number in the multiset. So if the frequencies of your numbers are small enough, you can use multiset::count. But, in general if you want to only check whether a certain number exists in the multiset, multiset::find is strictly better, because it's exactly $$$\mathcal{O(\log n)}$$$, which is always better than $$$\mathcal{O(k + \log n)}$$$.

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

        Yes, this is more accurate.

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

        How to write that equation or the formula O(K+logn) sir? If you dont mind can you explain a little bit with an example.

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

          $$$\mathcal{O(k + \log n)$$$ (not actually three dollar signs, only one, but it's like this because if I don't put the backticks on either side, it just renders as $$$\mathcal{O(k + \log n)}$$$).

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

            $$$( O(K + \log n)) $$$ Thanks master. But how can I properly write this equation- $$$( O(nk^2/w$$$ + $$$k^3/w))$$$ can you tell me please.

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

              $$$\mathcal{O}(\frac{nk^2}{w} + \frac{k^3}{w})$$$

              This gives you $$$\mathcal{O}(\frac{nk^2}{w} + \frac{k^3}{w})$$$ (actually, I think your way ($$$\mathcal{O}(nk^2/w + k^3/w)$$$) looks better than this one, but you can use whichever one you think looks better). By the way, if you're interested in learning about LaTeX, this is a good place to start: https://artofproblemsolving.com/wiki/index.php/LaTeX:LaTeX_on_AoPS.

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

                Thank you Master. I was going to asking you about LaTeX . Thanks!

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

        thank you!

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

How was problem C guys? I was struggling to solve to solve it? But Finally I solved it.

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

A-find if 2*a<=b if so you can buy all ns with a, else buy (n/2)*2 with b and if n is odd add 1 B-sort the matrix and find the first number and then insert it in a vector, add d n times and find the value and insert them all in vector, then add c to the initial value of the matrix row and do this n times too C-Kraken attack (k+1)/2 shots from the start and k/2 shots from the end, just iterate over the array from the start and from the end and decrease the value as much as possible, if it becomes 0 add it to the answer D-store the values of b in map, and the values of first m elements in map, while doing that check if the values is second map were smaller than the value count in first map , if so do matched++, now iterate over the other values of a buy keeping an l(left) remove the left and add the right, simultaneously updating the map ,and updating the matched values as explained. E-Just iterate over all values of length to be the ans, then just reverse the length k segment whenever you find 0 in the string, at last if all are 1s this k is possible, hence find the maximum of such k F-first of all ans is a/+b/2+c/2+d/2 because their xor will be zero as the same value repeats twice, secondly is one of the a,b,c is absent then no further action is required as they wont add to the ans because of the placements of 1's in their binary representation, but is a,b,c are odd that means 1 ans can be extracted out of these 3 values hence ans++

rest ask from a higher rated coder,thanks :-)

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

Why so many Hacks on G? Even mine is hacked. Whats ideal expected TC for G? Is it better than O(n*m*100). Rating of G has gone from 1900+ (yesterday) to 2500+ (now) on clist :(

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

    The validator is incorrect, so tests which are above the limits can pass as hacks. But a fraction of the solutions are TLE even with a correct validator.

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

      ohhh right thanks, then maybe I will wait till system testing :)

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

    The test validator is wrong.

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

Can someone explain to me how to approach problem F. I can only think when count of all 1,2,3 and 4 is even and when cnt(4) is even and count 1,2,3 is odd. These could be the 2 cases when bob can win. Unable to code the solution. thanks in advance.

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

    $$$cnt(4)$$$ is independent from the rest, so calculate it separately.

    For $$$cnt(1)$$$, $$$cnt(2)$$$ and $$$cnt(3)$$$, I prefer splitting into two cases:

    • Start from a state with all three values being odd, then subtract $$$2$$$ from each, add $$$1$$$ into answer each time.
    • Start from a state with all three values being even, then subtract $$$2$$$ from each, add $$$1$$$ into answer each time. Do not add $$$1$$$ at $$$(0, 0, 0)$$$ cases though, as there are no cards to play.

    Pick the better case out of the two, then add $$$\lfloor \frac{cnt(4)}{2} \rfloor$$$ in for the final answer.

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

    4 has independent bit compare others(1, 2, 3).

    So you can try O(N^3) DP on one, two, and threes.

    just calculate dp(one, two, three) + four / 2

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

255713576 Hey this is my first contest ever and only one of my submission got accepted. The thing is on running the same code for B , C and D I'm getting the required output but here on site it displayed otherwise. I understand that writing in python would slightly impact the time execution but probably shouldn't be the case up until i reach a way higher rating. So it would be great if someone could point out the logical errors if any or if there's way i should be submitting my code, thus providing me with pointers for the same. Thanks

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

    Also in regards to my rating, given the rules i should be eligible to participate and this should be treated as rated for me but it is still shown as unrated.

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

    I like your clean code, but you should optimise it a bit: 255745156

    It's normal to perform poorly in first contests, with practice it will get better

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

i think it's time to give it a try to change my color

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

The time limit and constraints for G are so stupid

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

I am curios to know why I got TLE on test 35 in G: 255703960

It is simple, try all divisors of $$$a_{1, 1}$$$ with $$$O(nm)$$$ dp.

We will have maximum 240 divisors (from 720720).

So maximum $$$<5 \cdot 10^7$$$ operation. std::vector construction can be strange but time limit is 3 seconds, it allows use nearly $$$10^9$$$ operation I think.

So how could I gotten TLE?

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

    Some people with the exact same idea still pass for some reason. Very weird constraints and time limit.

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

    I almost have the exact solution too and it TLE'd in test 35. Then, I changed vectors to global regular arrays and it passed.

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

      This is not making sense, this is not testing the coder's ability to code

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

      Yes, I see. But I think it is foolish, 20 times slower than expectation.

      As I said, std::vector construction shouldn't affect very much.

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

    Even Jiangly wrote same solution as yours and got TLE,

    this solution is so obvious, I did similar, but what I did I precomputed the the divisors till 1e6 in log2(1e6)*1e6 time.

    still I have no clue how the hell my solution got TLE.

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

    Take my words with a grain of salt, but my suspect is that the alternating testcases here was not for show, but a deliberate attempt to cause cache misses and thus slowing down any time a "true" test begins, making it work with a worst-case speed every time.

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

    I also encountered this situation, and later I changed vis from a local vector to a global variable and it passed. I guess the 2D vector initialization in C++is very slow

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

    std::vector construction involves dynamic allocation (allocating from the heap). It is not a cheap operation. When $$$t = 10^4$$$ and $$$a_{1,1} = 720720$$$, you are doing it $$$240\times 10^4\times n$$$ times (times $$$n$$$ because you allocate for each of the rows). Which is significantly slower than just constructing once.

    Also, the nested std::vector<std::vector<...>> is not fully contiguous in memory, so you also get potential cache misses when you access the next row.

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

      Same code works fine locally though.

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

        By locally do you mean your own computer or codeforces custom invocation?

        Anyway, my point is that the difference between using a nested vector and constructing it many times, vs using a global array, is not subtle. And this could be a determining factor when the time limit is tight.

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

      can you please tell why vector::assign works faster than just creating it everytime with constructor?

      with constructor : 255927707, TLE

      with vector::assign : 255927628, 734ms

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

        Well, I believe that when using vis.assign(n, vector<int>(m)), you are only allocating one size $$$m$$$ std::vector (vector<int>(m)). While your code using the constructor, it is allocating $$$n$$$ vector of size $$$m$$$.

        When you use the vector::assign, it just tries to copy the second argument (vector<int>(m)) to each of the rows of the nested vector vis. Because initially every row of your vector vis had already allocated memory that could at least fit $$$m$$$ elements (you had constructed it outside the lambda with size $$$n\times m$$$), for each of this copy assignment, it doesn't require allocating any more extra memory.

        tldr: so you are allocating $$$n$$$ times less.
        number of heap allocation, worst case:
        constructor: $$$t\times d(720720)\times n$$$ = $$$10^4\times 240\times 20$$$ allocations
        vector::assign: $$$t\times d(720720)$$$ = $$$10^4\times 240$$$ allocations

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

H is interesting

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

=

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

Looks like CF have problems with allocation, this solution(https://codeforces.com/contest/1955/submission/255842530) works 11s on test generated by this code:


t = 10000

print(t)
for i in range(t):
    print(20,1)
    for i in range(18):
        print(720720)
    print(1)
    print(720720)

But local run is 2s... When I removed allocation of used in check -- it passed with 0.8s on cf.

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

when will rating changes come out ?

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

    During the next ~12 hours (I don't remember exactly, most likely even less) after the system testing ends

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

Because of your terrible hacking in this round, it's fair for you to receive a large number of downvotes.

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

    Be rational at what you are criticizing.

    If there would be anything to blame, the most critical would be the absurdly tight TL on G, and even that wouldn't be generally agreed — tight TL isn't the end of the world most of the time.

    Hacking due to loose validators is worth criticizing, but not downvotes. Main tests didn't breach it, hacks did, so nothing went wrong within the round. They are also reversible (and already been so at one point, as most of the hacked solutions have been rejudged with a proper testset). What more to blame?

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

      Well, I downvoted cos I can see solutions I have the same complexity with pass for G, while I get TLE. Plus, you're everywhere :D

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

        Can say I am having quite a lot of free time for now XD

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

          why is this contest not showing on my profile rating graph? It's not in all sections either.

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

            System testing underway, still a long while until rating updates, be patient.

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

              okay but I solved 4 questions during the contest and now it shows that I solved only 2, is it also due to system testing? Sorry for too many questions, kinda new here :)

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

                In system testing, all Accepted solutions are rejudged. Your other two are probably still in the queue and not yet rejudged.

                We can only wait.

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

                  okay, that makes sense. thank you!

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

                  system testing is complete, but the contest is still showing as unrated for me. my rating is 826, so this contest should be rated for me, right ??!

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

      Actually, I do think the problem G itself is created badly. I think a good problem should focus on examining the complexity of time or space, rather than optimizing constants, especially for a Div3. In that case, I think the data range should be at least 1.5 or 2 times looser than the optimal solution.

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

        I think it served that purpose normally. Judging that the original testset had nothing too strict in particular, I would say even the judges haven't really considered to stretch the constant optimizing, and only until a legit hack attempted to stress greatly into it, the complete revelation of contestants' bad implementations would begin.

        I think the data range should be at least 1.5 or 2 times looser than the optimal solution.

        Well, they did, kinda. You could compare some "good" implementations with the "bad" ones — and we only consider the "formal" solution i.e. BFS with all candidate divisors. Sometimes the difference go up to like 5-6 times, signifying the gravity of the issues which, in my opinion, have gone beyond planning.

        At this point, to blame the authors or not is pretty much a gray zone. Perhaps the integer constraints should have been $$$10^5$$$, but normally who would put that awkward limit for an array element in a number theory problem?

        I, however, believed that FST'd participants would take some responsibilities as well instead of fully diverting the blame. Cache misses and similar memory issues are actual things, and its nature is actually included in some fundamental teachings in computer science. It will be relevant if you wanted to pursuit this career later on, nonetheless.

        So perhaps we might be agreeing to disagree. It's fine that way though. I would only hope that we wouldn't bring down our judgment recklessly based on short-lived emotion bursts.

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

      Since it has already been rejudged, I'll retract some of my criticism from this incident.

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

Can anyone tell what might be the reasons of showing correct answer in compiler and wrong in codeforces?

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

    Most of the time due to undefined behaviors (UBs), and as your compiler/machine/etc. isn't fully identical to that at Codeforces, UBs will have different effect on different places.

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

      see my last code g wrong on test case 1. I have defined each variable

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

        Now I'm confused, like your WA1 submission is of an obviously wrong idea. I wonder how could any env give correct output with that...

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

          Check for undefined behaviour.

          I have defined each variable

          Peak Codeforces moment.

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

Will the submissions to problem G that only fail on invaild tests be rejudged? Like this submission and this submission

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

https://codeforces.com/contest/1955/submission/255667514 Why is my solution giving TLE, can someone please tell(problem B Progressive Square)?

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

too many downvote :)

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

Why are you downvoting this post so much? I think even with the problem G's issue it was a great contest

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

    F should be before C

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

      Should be before D for me. I agree F is too easy but C is just implementation

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

Yesterday, it told me during the contest that my solution for problem B was accepted and it was shown in th rankings too. Today, it says that my submission for problem B is still "in queue". And the rankings don't show that I solved problem B either. Why is this? Can someone please help me out.

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

    This is known as system testing phase. Your solutions are being checked again and if they run correctly you will be given the points... Don't worry

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

Is it because a lot of Problem G solutions are getting TLE which is slowing down systest? The testing progress bar only went up by 2% in 30 min...

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

    probably not only problem G...

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

      It would've been nice to wake up to positive delta. Now I need to worry about whether my submissions for D & E will pass systest or not... :(

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

guys fst is your skill issue please stop downvoting

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

    I believe people are downvoting because of the problem G mess, not cause of fst.

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

Can anyone help me figure out why my solution to D got TLE? Seems $$$O(n)$$$ to me.

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

how this code got accepted with 2999 ms in problem G

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

    The time limit is 3000 ms, and it took 2999 < 3000, so it passes. :)

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

      there are a code with less time complexity with TLE like this code

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

HELP HELP How to know when not to use Unordered Maps? or should i use just Maps always? Got TLE in 'B' bcuz of this BS

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

Problem D ; RIP python users, most of the solutions got TLE for test case 11. My solution as well got TLE for test case 11 (sad face). Please look into this if possible

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

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

Can anyone help me to understand why am I not rated in this contest even though I'm eligible.

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

This has been my second contest on here, but why is it showing up as unrated? "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." — doesn't this mean it should be rated for me?

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

    Rating hasn't been updated yet. Wait for a few more hours until it's calculated.

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

A<B<D<C<F<E

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

Problem D — Python

Directly create a dictionary with key as integers from array — TLE -> 255910556

Converted the integers in array to strings and then created the dictionary- AC — 255910798

Why??? :((

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

Why is this submission 255757792 for problem G giving TLE on test 35, but when using the same test on custom invocation, it finishes under 2 seconds. Don't the judge and custom invocation use the machine????

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

    My bad, I was using 1000 test cases instead of 10000.

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

      use global vector<vector>

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

        Does allocating memory from the heap take that much time?? because even if I declared it as global, I would still have to clear the vector at the beginning of each iteration.

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

          You reallocate it $$$100$$$ times. The time limit is too tight, so it got TLE.

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

absurd checking, i was waiting to become specialist today, but -4 i get

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

EID MUBARAK to all muslim brothers !!

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

.

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

Eid Mubarak to Every coder

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

this comment is in queue

→ Reply