Vladosiya's blog

Codeforces Round #925 (Div. 3)
By Vladosiya, history, 13 months ago, translation, In English

Hello! Codeforces Round 925 (Div. 3) will start at Feb/13/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 7 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: myav, Gornak40, KwisatzCoderach and Vladosiya.

We would like to thank:

  1. MikeMirzayanov for help with ideas and Polygon and Codeforces platforms.

  2. nigus for red testing.

  3. vladmart, Gheal, KseniaShk for yellow testing.

  4. htetgm for purple testing.

  5. natalina, JuicyGrape, lockdown, kotikk for blue testing.

  6. RedDreams for cyan testing.

  7. the_Incharge, Aurora__, Longqiang for green testing

Good luck!

P.S. Happy Valentine's Day!

UPD: Let's continue streak of announces with photo of the authors :)

UPD2: Editorial

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

Comments Comments (158)
| Write comment?
»
13 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Wow, you put a lot of effort to make a lot of quality div3. Thanks for a lot good div3 round to help beginner to advances in CP.

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

Yeahhhh!!! Div 3 Letsssss Gooooo

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

Div 3 are my favourite. Lots to learn.

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

the round number and date is wrong please fix

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

speedforces let's go

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

Thursday, October 12, 2023?

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

I hope this is my last round before cyan

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

Thank WHO for red testing 😳

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

My first unrated Div3 I mog everyone

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

don't make your gf sad, prepare gift after contest

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

    cp and gf? nah man something doesn't feel right. Just don't touch grass and stay home I guess

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

I had no idea authors could be so pretty. I'm blushing (,,>﹏<,,)

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

    mmm, why?

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

      I was hoping the authors would see it and feel happy.

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

        No, I mean why you thought that authors couldn't look pretty. As far as I'm concerned they're all human beings, just like the rest of us

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

          If I became an author, I would be a good counter-example :)

          But you are correct. Everyone is beautiful. That's why its great to have pictures of the authors in the announcement.

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

so sweet post. Happy Valentine's Day. Do spend time with ur loved ones, instead of attending contests

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

I am the one in the button right on Valentine's day :⁠,⁠-⁠)

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

I don't get it,why are authors making a 'C' with their hand?

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

    May be because Mike also did the same on his picture (to hold the burger)?

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

    It's not the letter "C", it's half a heart (we tried, ahahah) We wish the community a happy Valentine's Day!

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

      Got it,that makes sense,i need to go out and meet some real people.

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

Thanks for the contest but why y'all throwing up gang signs?

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

    Bro failed to get some contribution XD

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

      Lol, at +116, even 100 upvotes on this comment won't change my contribution at all

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

Valentine's Day ? Oh man, i am CPer

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

My first unrated contest

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

They are so similar

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

why are the names of the authors written in reverse

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

Hopefully my last rated div3

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

why the solution will be out 5 minutes before the contest ends?

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

Hope positve delta for all rated participant.

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

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

Good luck to everyone.I hope to become expert on this round.

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

Hope to reach expert again

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

Disgusting problem F

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

    It's not, F is basically "Detect cycle in a directed graph".

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

      how to represent it as a graph?

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

        Code — 246203312

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

        You basically ignore the first element of each line.

        Construct a directed graph based on the other ones and detect if any cycles are present using a topological sort.

        If there is a cycle, then "No", else "Yes".

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

      Damn! I was thinking of graph but then I wrote this 246240679 wierd solution which got accepted.

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

    you can do "F" just by making first line as 1, 2, 3, ... n, and these ai changes in next k — 1 lines too.

    Then for each line just check order is maintained (i.e. curr element is less than last)

    As an edge case: ensure "1" is correct in all.

    submission

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

Got the right idea for F about an hour after the contest started but spent the next hour debugging double-hash. :(

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

    Hope no one tries to hack me after I write this comment. :(

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

please hint for C

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

    You MUST choose x as the first OR the last element.

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

    three possible ranges you will select from k to n , from 0 to n-k , or from i+k to n-k. k is the index is where there's no more duplicates from the beginning or end from the array, like [1,1,1,2,3,4,5] k is at index were ai is equal 2 , so we can make the range we select [4,7] , same from the back. i+k to n-k is when the duplicated at front is the same from the back . sorry for bad explaining

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

    You can look for the longest segment of equal elements from the start, let's call it a, and the longest segment of equal elements from the end, call that b. Now, there are two cases:

    (1)If the first and last elements are equal, you can choose the contiguous segment of elements not in either a or b. (notice, if len(a) + len(b) > n, the answer is zero. Else the answer is n — len(a) — len(b))

    (2)If the first and last elements are not equal, you choose the equal element as the element that comes in the longer segment. (notice, the answer in this case is n — max(len(a), len(b)))

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

i am annoyed i couldn't get F i didn't think it will be cycle detection at all.

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

Problem D is nice, thanks for the contest. But how to solve F?

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

I feel like idea of F was simple but the implementation was tedious. Also, loved G!

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

Any hints for G?

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

    Try reducing this problem to a stars and bars problem Try to think what are the prerequisites if we want to place the 4th block at any place same goes for the 3rd Think which blocks are the limiting factors and which we can take care of irrespective of their quantity Have a Great solve!!

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

Maybe it's just me, BUT F seemed way easier than both D and E, although didn't spend much time on E after I saw F, which I had just the right idea for. Overall very fun Contest.

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

Quick hints for all the problems before the Editorial comes out.

A: Just brute force on each index using 3 for loops.

B: As the water can't flow backward, therefore the amount of water in any prefix can only decrease or stay constant.

C: Check if all equal, else count prefix equal length and suffix equal length.

D: What if we store the remainders in pair<int, int>?

E: Replace each number by the count of its trailing zeroes, now play the game greedily.

F: We can easily create the order from the first 2 arrays given (if k = 1, then its YES). Just make sure to handle one edge case [1,2,3,5,4] and [2,1,3,5,4], basically those in which there are 2 possible orders)

G: Pieces 1 and 2 can only appear alternatively, and the pieces 3 and 4 will always fit in the between their occurences. Also, pieces 3 and 4 can be repeated, while 1 and 2 can't. Try fixing Piece 1 or 2 as the first piece in the chain, do you get some general pattern?

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

    Simple way to do F

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

      Easier way to solve F without using graph

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

      Yeah this subproblem looks way more easy and familiar, I was just hasty and went with my first thought.

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

    In F, I think the simplest way to code is model it as a graph and use topo sort. I think that makes implementation really easy with template :)

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

      F feels like AtCoder style problem, doesn't it? :)

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

        I think it's more like the first few problems of a regional.

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

    can up please tell what's wrong with this

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

    I did F after constructing the graph and checking if the number of SCC is equal to $$$n$$$:)

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

F — "Detect cycle in a directed graph."

Submission- 246203312

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

How to combine pieces in the second test case of problem G (one sample way would be enough, please)?

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

    121212121244 or 121244121212

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

      Hmm, but there are only 2 pieces of type 2 and single piece of type 1: c = [1 2 5 10]

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

        Sorry I misread it as second last test case, for the 2nd tc, here is one,

        333332124444444444 or 333332444444444412

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

          Thanks! Now I see why I could not solve the problem :)

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

I just wanna say thank you for making this contest, I was able to solve till F( can't believe I did this )

I think I have very unique solution for problem D: Problem D Solution

I used modular operations for storing single value in map

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

    I did not get the logic behind your code. int v = mod*a + b ; int fv = mod*fx + fy ; why did you do this?

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

Code editor is not working, keeps running and no result, makes the whole experience shit. Cant run test cases.

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

How to solve G: https://chat.openai.com/share/3647110d-401a-4591-9dda-840260a0317d

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

    you just calculating binomial coefficient, how is this related to solving G?

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

      Because the only thing that came to my mind was:

      • place a 3 on this group (between 1 and 2),
      • or move to the next group

      which led me to the formula: $$$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$$$, and I didn't realize that it was effectively just comb(i + j, j), so that's what ChatGPT told me.

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

https://codeforces.me/contest/1931/submission/246186250

The best solution to hack:)

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

Here is how you can choose the next type of element to add in problem G.

Two nice observations:

  • This condition must be satisfied: $$$\left|c_1 - c_2\right| \le 1$$$.
  • Think about the problem without elements of types $$$3$$$ and $$$4$$$, then try to insert them in the generated chains.
→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was wondering whether this contest gives any rating? I am 401 rated. I have participated and solved 2 problems but haven't got any rating. Can anyone tell me if i'll get any rating?

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

    ratings will be updated after the hacking phase and 100% system testings.

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

Does the following work for F?

Rearranging any of the participants except the last one cannot change the last participant from the permutation. Therefore, we can find the real permutation by checking which one has the last participant only once. Now, that we have obtained the real permutation, we can compare all of the k inputs to the real one and check.

This doesn't work when k == 2 but in that case we can simply check subsequences ignoring the first two numbers.

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

    Better Idea:

    Simply Ignore the first Position of Every observation. Take an edge pointing from v[i] to v[i+1] (1 <= i <= n-2) for Every participant observation.

    Check for the cycle in the graph, If the cycle exists then NO else YES.

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

    246262272 Maybe hashing was unnecessary, also who knows if this might get hacked.

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

Loved the beautiful Stars and Bars problem (G) Got to the solution but didn't submit earlier as I was unsure if it would be rated for me Nonetheless Here's my solution in case any one wants a reference: https://codeforces.me/contest/1931/submission/246256160 :)

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

As an expert I failed D: TLE on test 9. Here is my code: 246198274. Could anyone help me with debugging? I think this is O(nlogn).

Edit: This is O(y). Forget it

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

How to solve E? Didn't get any idea at all :(

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

    1) Ans "yes" if number of digits in the last number >= m + 1. Anna in each step tries to reverse number with maximum zeroes on the end. Sasha in each step does concatenation number with maximum zeroes on the end with any number without zeroes on the end (number without zeroes on the end is guaranteed to exist, since it either exists initially, or Anna will make it her first move)

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

    it is optimal for both of them to the choose the numbers which have most no. of zeros at the end

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

    multiset<pair<trailing_zeroes, digits>> and just model a game

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

I think you should reduce the time limit of this problem. this submission -> https://codeforces.me/contest/1931/submission/246247517 runs in 1 second. this submission should not get AC because # of testcase is 10000 and this submission is executing a for loop of 200005 every test case. that's more than 2e9 operations.

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

!What is this submission code
is he know the testcase?

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

After successfully wasting 1.5 hour on B i smashed binary search in B

can someone hack it?

246247536

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

    why would you even think of binary search . you already know that the good value is sum/n . that's the only way you can make tha array the same

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

Video Editorial for problem B (Audio : Hindi) TUTORIAL VIDEO LINK

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

Thanks to the authors for an interesting div 3 without clay and with tasks that are fun to solve. After this div and the Cognitive Technologies Olympiad, I realized that the name Gornak in the list of authors => good Olympiad/div.

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

Can G be solved using inclusion exclusion ?

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

May I ask why I passed 3 questions but didn't receive a rating in the end? Or who should I seek help from? I really want this rating, thank you.

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

    Rating appears after 1 to 24 hours from the end of a contest, and if there is a hacking phase, like this contest, then it may last up to 24 hours or less.

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

in Problem E , i wrote code which was absolutely right, the only thing i missed was, if number>=10^m then number of digits should be >=(m+1) not >=m (it was pretty close :) )

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

How to solve Problem G?

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

wow that was very cool

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

really enjoyed this contest, particularly problem D. start to see some common patterns on int-mod problem..

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

my respect to Aleksander Gornak

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

I was getting runtime error (STATUS_ACCESS_VIOLATION) in E, during contest , but after contest when i submitted same solution it got accepted . runtime error during contest code link.
accepted code after contest. Thanks

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

    The problem is this for loop here: for(ll i=vect.size()-1;i>=0;i-=2).

    In C++, the return type of std::vector::size is an unsigned integer. When vect is empty, then vect.size() - 1 becomes 0 - 1 which then overflows to UINT_MAX. This causes out of bounds error which is why your program got runtime error. (It seems that this is changed in C++20, which is why your other code got accepted)

    To fix this, you just have to convert vect.size() into any signed integer type. For example for(ll i=(ll)vect.size()-1;i>=0;i-=2). New code

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

Video explanation of Problem G (Chinese)

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

One of the best rounds I've ever participated. Thanks to all the writers and testers for offering us such a round.

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

The best div3 round contest I've ever participated!Thank you!

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

when will the rating come out?

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

    you need to wait that the system testing ends first (is around 80% right now). after that eventually the rating will be updated.

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

      Oh,Thank you.This is my first time to attend CF.(I find out my G turned out to WA,It used to be AC)

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

Can anyone tell me where have I made a mistake in these two codes? Only difference I have made from my side is making the capital N,small n? Basically I had initialised all visited array elements to zero in reset function. Thankyou in advance.

1st submission 246198873

2nd submission 246233252

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

    I don't understand why exactly gives you another answer (actually I'm more curious of how didn't get you RTE hahaha weird stuff)

    But the reason why the change works is because in the WA submission, you have the following code:

    vi g[N];
void reset(){
	fr(i,0,N){
		g[i].clear();
		vis[i]=0;
		vis1[i]=0;
	}
}

    and fr is #define fr(i,a,b) for(int (i) = (a); i <= (b); (i)++)

    So, the cycle in reset() will access to the position $$$N$$$. But the arrays g, vis and vis1 are of size $$$N$$$, I change you code putting a -1 and now it gets TLE, that makes a lot of sense, because $$$t = 10^4$$$ and $$$N=2e5+69$$$, so you will do around of $$$2\cdot 10^9$$$ operations just to reset.

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

In Question 4 this code exceeds time limit on test case 33 cant understand why its o(n) approach can someone please help me?

include<bits/stdc++.h>

using namespace std;

define ll long long

int main() { 

int t;
cin >> t;
while(t--)
{
    ll n, x, y;
    cin >> n >> x >> y;
    unordered_map<ll, ll> dp;
    ll a[n];
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        ll f = (x - a[i] % x) % x;
        ll l = a[i] % y;
        ans += dp[f*y+l];
        dp[(a[i] % x)*y+a[i] % y] += 1;
    }
    cout << ans << '\n';
}
return 0;

}

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

    Worst case time complexity of unordered map is o(n) while normal map is of o(logn) that's why it is giving Tle. I got AC with your solution by just changing unordered map to normal map

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

But may I ask why I still haven't received a rating? It should have been a long time since the hack phase ended. I really want the rating for div3 this time, thanks.

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

    You must wait for some more hours after the system test. Codeforces needs time to calculate rating changes. Just chill

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

Why there is no rating change? My rating is less than 1600

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

    It takes a while after the system test for codeforces to remove cheaters and recalculate the rating changes.

    By the way, have we met somehow before?

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

can anyone just tell me which are valid patterns in G? I can't find any for 1 2 5 10

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

    One of the valid sequences is:

    2 4 4 4 4 4 4 4 4 4 4 1 3 3 3 3 3 2

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

      Thank you... I didn’t notice self loops.

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

when it will be rated?

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

I am new to code forces this is my first contest, I have solved two questions still didn't get any rating. Did I miss anything?

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

    Don't worry too much, it will be updated soon . Within an hour, I think .

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

    Just wait bro ... A Div 3 contest usually takes more than 24 hours to give you rating change ...

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

Give me my rating pls((

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

Finally blue. Was a great experience.

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

Hello respected judges,

My code was accidentally matched with the other participants. I have no idea about this rule of the CodeForces of contests. I didn't know this before. I had no selfish intention to do this cheat of any type. That participant is my college friend, and we discussed not exactly but similar type question before this about how to solve it. But I didn't know how we both accidentally write up the same code.

So, please can you give me my rating back, in future I will take care of it and not publish my code publicly anywhere.

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

    lol

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

      Happy Birthday to your alt account, just 2 minutes before re-registering on Codeforces. And hey, you're new here, aren't you?

      → Reply