awoo's blog

Educational Codeforces Round 170 [Rated for Div. 2]
By awoo, history, 33 hours ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos. They offer a BSc in Computer Science and AI with JetBrains Scholarships. Gain cutting-edge skills in AI and machine learning, preparing you for high-demand tech careers. Curious? Check out the CSAI curriculum now. Limited scholarships available — don't miss your chance to study in Europe for free!

Are you looking to sharpen your skills and increase your chances of getting a scholarship? Join the free clubs for high school students from JetBrains:

On Oct/14/2024 17:35 (Moscow time) Educational Codeforces Round 170 (Rated for Div. 2) will start.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Aleksandr fcspartakm Frolov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Please note that the problems of this round partially intersect with the problems of the Qualification stage of the Southern and Volga Russian Regional Contest. If you took part in the qualification, please refrain from participating in the round.

Good luck to all the participants!

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

»
32 hours ago, # |
  Vote: I like it -20 Vote: I do not like it

It feels really good to be the first comment

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

    it feels better to be the first reply of the first comment

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

    funny how almost similar comments but the better color dude has much higher upvotes

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

      or maybe "first" comments are stupid, so people upvote comments making fun of "first" comments

      → Reply
»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How much +(Plus) will I get if I solve A-B-C within 1H??

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

    It depends on many things like other peoples performance, your accuracy etc. So hard to tell.

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

Two contest on same day for me.

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

Why the recent Educational Rounds were removed from Harbourspace?

I thought that there had been a logo on the top-left of the page.

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

Two contests on my birthday! Cool!

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

As a problem writer, I feel it is important for me to mention that problem D is going to be an interactive binary search tree problem.

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

Well what's the score distribution? Can you please update the post and add score distribution?

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

    as a writer, its 69 — 69 — 69 — 69 — 69 — 69

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

    its standard icpc, there is no score. Every problem is worth 1 point and tie breakers are resolved by looking at penalty time

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

Hope to become pupil after this round :p

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

As a joker, I'll get lower rating!!!

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

Last night/Early Morning contest Messed up my sleeping pattern. I desperately want to participate, but at the same time my mind is sleep deprived.

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

pupil in this round In shaa Allah!

→ Reply
»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

yesss

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

I solved D but not able to solve B and I end up with 7k rank.

I won, but at what cost?

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

    How did you do D?

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

      Lets do DP. Let N be the number of 0's.

      Define dp[i][j] as: we are at the ith 0, and we already have j intelligence points.

      Now the current point can be an intelligence point or a strength point.

      If we take intelligence point, we will have (j + 1) intelligence points and i — 1 — j strength points. Now find how many rounds you can win (you can do this by storing the positive and negative numbers from current 0 to next 0 and upper_bound over it).

      So the transition becomes dp[i][j + 1] = max(dp[i][j + 1], dp[i — 1][j] + wins)

      Or if I take the current 0 as a strength point, we will have j intelligence points and i — j strength points. Again find how many rounds you can win (same way as before).

      Again, transition is dp[i][j] = max(dp[i][j], dp[i — 1][j] + wins)

      Finally, ans = max(dp[last_0][intelligence_achieved])

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

        can you explain how you calculated wins in more detail please?

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

          First, for every ith 0, store all the positive and negative numbers from ith 0 to the next 0 in a list. Call it cnt[i][0] for positive numbers and cnt[i][1] for negative numbers (take absolute value of the negative numbers and store)

          Later, when you do DP, at ith 0, if you have x intelligence points and y strength points, you can upper_bound over cnt[i][0] for x and see how many rounds you can win. Same for y, upper_bound over cnt[i][1].

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

            what if we can also win some more rounds after the i+1th 0?

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

              We don't know what point we will take at the i+1th 0, when we get there, based on our calculated DP states we will decide what to do.

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

        This is exactly same of what I thought, but the implementation was a bit difficult for me. Bad luck!

        → Reply
      • »
        »
        »
        »
        5 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I implemented the same idea but it failed on test case 18 my answer was +1 wrt to the original, can you help me debug, please?
        → Reply
  • »
    »
    7 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    its a very trick observation don't worry

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

    you needed to observe the pattern, took 30 mins away from my clock :(

    → Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the soln for D ? i tried DP but TLE'd 285921797

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

    DP optimized with binary search 285875242

    UPD: If you TLE'd, you probably didn't split the Attribute Checks into sections. If you split, you get worst case of $$$\displaystyle \mathcal{O}\left(M^2 \cdot \log_2\left(\frac{N}{M}\right)\right)$$$ instead of $$$\mathcal{O}(M^2\log_2N) $$$

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

      i did this and TLEd. unlucky ig

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

        same i also dp + BS but tle how can we further optimize??

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

          Don't really need binary search, can just go over all positions, update dp only at zeroes and keep count of each check level to the right from the current position 285916481 so it's O(n + m^2) total.

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

        Did you write recursive DP?
        My code with same approach using recursive DP (285888018) TLEd, but with iterative DP (285891738) got Accepted!

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

          i wrote iterative dp :(

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

          My iterative dp + binary search failed while iterative dp + prefix sums passed :(

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

      Nice one. I did exactly the same but failed to implement :(

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

      wow thats fascinating

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

    I did with Fenwick tree, a dp would need to loop $$$m \times n$$$, which shouldn't be fast enough.

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

    It is DP only.

    For each Incrementing Point ( where a[i] = 0 ) , check what gives you most benefit ? Whether to take this as strength increment or intelligence increment.

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

    You can store the indices of values in lists (like $$$list[arr_value] = indices$$$) and use a pointer to keep track of how many have passed since the pointer will always be increasing.

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

    you can use difference arrays to optimize dp

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

    you can compress data and use simple prefix sums for calculation.

    UPD: nevermind, it's about C.

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

    I did just two suffix count arrays of sizes m+1. Then i do dp on each zero and if I take +str count number of elements with new str on suffix and calculate new values for suffix.

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

    You can store the positive and negative numbers from every 0 till the next 0 in a list, and for a fixed no of intelligence and strength points, you can upper_bound on the list to find how many rounds you will win.

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

F is the same as https://mirror.codeforces.com/problemset/problem/405/E .

→ Reply
»
7 hours ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

I was thinking about this problem when solving F, but F has multiedges Even Outdegree Edges

Upd: easy to adapt and worked for this F too, almost the same code I made for the above problem, just try to define the direction greedily in DFSTree, if outdg is 1 for the current node, change edge to its parent and update the outdg of parent node. if orientation is 0, then choose xi, else, choose yi. 285931982

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

Can someone pls help me understand why my code for (C) gave WA on test 2? Not able to figure it out. Thanks!!

285922242

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

O(n^2) can't pass Problem D easily and need exhausting optimization. Time limitation tooooo strict.

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

    You need to write O(n log m + m^2) for D instead of O(n^2)

    O(n^2) can't pass 2*10^6 for sure.

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

      Sorry i mean O(m^2)..

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

[https://oeis.org/search?q=1+2+1+2+4+1+2+4+8+1+2+4+8+16+1+2+4&language=english&go=Search]

→ Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the intended time complexity for D? My O(m^2logn) passes.

→ Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it
code

I tried to make an vector of vectors srs where all the continous segment are present and did the sliding window to check the max I can pick with k distinct, can any one point out where Its failing. thanks

→ Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/2025/submission/285927740 anyone knows why this TLEs?

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

Was about to get excited until Wrong answer on test 8 on D, well fml then I guess

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

In problem E, I wrote the solution such that:

I started on first suit and define if I take first j cards, so number of ways if C(m, j) * ways[m — j][(m — j) / 2] which ways[i][j] is number of ways to divide i element to 2 parts

When I took the transition of the dp, on next suit, if I had j cards from first suit, I can use x of them to beat any x cards so I have to mul C(m, x) * ways[m — x][(m — x) / 2]

So the transition of f[i][j] from i to i + 1 is: f[i + 1][j — x] += f[i][j] * C(m, x) * ways[m — x][(m — x) / 2]

Did I make a mistake ? I can't find

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

    I guess C(m,j) is binomial coefficient. But some of those combinations are not valid. Actually, you want Catalan numbers or "number of valid parentheses expressions of size $$$m$$$".

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

question B is cancer, Took 45 minutes to just guess 2 power k.

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

    Can you please explain the logic of this problem, I was struck the whole time :(

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

      there is no logic. just do a brute force and guess the pattern

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

        There is a logic. Let's imagine a grid NxN. According to the formula C[i][j] = C[i-1][j]+C[i-1][j-1] and C[i][0] = 1, C[i][j] is the number of ways to get from the cell (i,j) to any of cells (0,0), (1,0) ... (N,0) when only following steps are allowed 1) (y,x) -> (y-1,x-1) 2) (y,x) -> (y,x-1) Since each time x is decreased by 1, we move exactly j times. Since j < i, it is always possible to chose any of 2 steps. For (n , k) there will be k steps, and two variants for any step, which leads to the result 2^k.

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

          sure ig. what i meant is, in this type of problem you shouldnt look for logic. guessing is the way to go

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

      in the wrong formula, C(n,k) = C(n,k-1) + C(n-1, k-1)

      As is stated that n > k for all n,k , you can see that for every K, you will have 2 branches of K-1 until it gets to k = 0, which the result is 1. Which means, C(*,K) = C(*,K-1) + C(*,K-1) = C(*,K-2) + C(*,K-2) + C(*,K-2) + C(*,K-2), that is, 2^k (considering that when k = 0, it returns 1)

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

    I knew it would be some kind of pattern otherwise it will be too hard for div2 B so i generated sequence using that wrong formula given and search the sequence on enclyopedia of interger sequence and got formula ,

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

    Could have just manually solved for n = 1, 2, 3, 4, 5. It was easy to see the pattern after that.

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

explain E clearly please :(

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

How to solve E?

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

    I think it is dynamic programming. dp(suit number, remaining cards of suit 1). then you just have to solve the one dimensional problem for a specific suit number. This is rough idea, still haven't solved it. This should solve it in O(N^2M) time complexity I believe.

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

      I treated the one-dimensional case as a balanced bracket sequence (there can't be a prefix where player 2 has more cards), then the transitions are basically counting balanced bracket sequences with fixed prefixes which is a known problem

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

    Maybe I need to explain why n = 3, m = 6 's result is 1690 :(

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

    Consider one suit. Define $$$a_k$$$ is the number of valid ways such that the difference between the number of cards of two players is $$$k$$$. You can use either dp or combinatorics to solve this. Note that player 1 must have no less suit 1 cards and no more suit X cards than player 2, so we have $$$k_1=\sum_{i=2}^nk_i$$$. The number of ways for the other suits is a convolution of $$${a_k}$$$, and given $$$n,m\le500$$$ you can use either brute froce or NTT.

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

Memoization gave TLE on D :(

converted into iterative soon after contest got over :(

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

I don't even get that D is a dp problem lmao, 1hr on the problem and I don't have a single clue. I need to do more dp exercises

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

I think the submissions for Problem D should be rejudged... My O(m^2logn) solution did not pass, and even after rewriting to O(m^2+mlogn) it barely passes...

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

    Do u think there is a specific reason for TLE when memoizing ?

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

      the constraints are too strict. everything TLEs if not done carefully, not just memoization.

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

      Unsure, but it is true that binary searching at each state is not the most optimal solution. I don't think it warrants a TLE in this situation, however, because some solutions like this passed (I'm not sure why mine is so slow actually).

      I was able to pass by fixing iterating over sum and fixing i and j and updating the number of passed checks by iterating forwards and backwards, reducing the need to binary search at every state, and now I only do it at each index.

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

        I fixed My Binary Search approach using prefix sums on frequency for each interval 1 min after the contest was over :(, sad to see some binary search solutions getting passed while mine failed :(

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

    $$$\log_2(2\cdot10^6)\approx21$$$ so $$$m^2\log n$$$ exceed $$$5\cdot10^8$$$. It is very normal that $$$O(m^2\log n)$$$ doesn't pass.

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

      While this is true, language/implementation differences allow some of such solutions to pass while others do not.

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

285925069

Why is this giving TLE? (C)

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

    isnt it bc of the loop from 0->n mapp.find?

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

      no

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

        I didnt read your whole code, buy anyway, u solved it in O(n^2), you have to solve in O(nlogn)

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

          i think this is O(nlogn) only, thats what im asking.

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

            its not, for every start 0->n you create a new window from scratch, which makes it n^2

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

              thats not how it works, lil bro

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

                Try an input of all the same number such as 1 1 1 1 1 1. You can see that it is $$$O(N^2)$$$.

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

                It literally is, you can prove it with induction on paper. For that reason ur getting TLE

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

If you complaint about the tl in D being too strict, that probably because you lack proper optimization skill lol https://mirror.codeforces.com/contest/2025/submission/285928139:

1) The most efficient data structure to store data is the one that has all the memory as close as possible: an array/vector.

2) If you ever use a 2D vector to store the dp, you have to wonder if you can optimize it to 1D. This is a huge leap, not for the memory, but for one important thing: Cache.

You can see my submissions for thought process

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

    based cache utilization enjoyer

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

The one contest I decide to skip has an easy problem A, sigh.

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

Great problem set!

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

For problem D

My first solution had used an ordered set for the splitting the indices into segments and storing in a sorted order which gave me a TLE. The TC for the solution should be O(m^2logn) as to my knowledge please correct me if I'm wrong. 285893834

Code

I used the exact same logic but replaced the ordered set with a vector and sorted the vectors and used upperbound for my final submission which should be of the exact same time complexity and got AC. 285923230

Code

Could anyone help me out in understanding why is it so that upper_bound solution works but set doesn't?

I tried to use the same logic with a regular set and had the same issue. Adding the else if(abs(x)>cnt) continue; line in the ordered set solution did not work which is the bit of logic changed in both the implementations.

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

    my approach was similar with your vector approach... still I got a TLE :(

    since u r using recursive approach too , I don't think it matters..

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

    Yep, complexity is right, but constant seems quite higher, since you store pairs and ordered_sets are quite slower than a normal set/map/multiset. Notice you don't update (erase) the sets, so yo can use vectors and use binary search (upper_bound).

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

In E, I just didn't realize that in a suit i(>1) 1st player can't take extra card when the current state of suit is already a tie (assuming we select the card from small to large in the suit). Since all previous card matched with a 2th player's card, if 1st take this card, it cannot beat any card (but you cannot let this happen, it will leads to the lose in global).

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

I'm really glad that ki<=ni in problem B Imagine it's not and that it would pass the system tests

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

G is cool

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

    U are cool

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

    How to solve G? I see, that the answer is $$$\sum{a_i} + \sum{\min{(a_i, b_i)}}$$$, where $$$a_i$$$ are heroes and $$$b_i$$$ are artifacts, and they are matched greatest-to-greatest. Is it some well-known problem?

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

there seems to be some issue. On "Standings" page, even after un-selecting the "show unofficial" checkbox, contestants having rating greater than 2100 are included in the ranklist.

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

for Problem c , can anyone tell why this solution is giving wrong answer on test 4 (i used binarysearch to solve this): https://mirror.codeforces.com/contest/2025/submission/285946605 thanks in advance !!

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

how to hack in codeforces for the first time ? my generator gives

Validator 'val.exe' returns exit code 3 [FAIL Expected integer, but "/**" found (stdin, line 1)] close this error as invalid input

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

nvm

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

My post contest discussion stream

Hints blog

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

Anything wrong with this solution to E, or just python tax? Runs in about 10 seconds on my machine. 285917083

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

TC is super strict on D. I think it cost me to write my own bsearch and use extra variables within the dp function (recursive of course). I kept debugging thinking there's some way to optimize further, but I'm just dumb. My brain during the round:

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

Solution of D in O ( M * M ) using prefix sums !

285955590

→ Reply