awoo's blog

Educational Codeforces Round 170 [Rated for Div. 2]
By awoo, history, 6 weeks 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!

UPD: Editorial is out

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

»
6 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

It feels really good to be the first comment

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

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

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

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

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

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

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

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

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

Two contest on same day for me.

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

Two contests on my birthday! Cool!

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

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

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

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

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

Hope to become pupil after this round :p

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

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

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

pupil in this round In shaa Allah!

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

yesss

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

    How did you do D?

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

    its a very trick observation don't worry

    → Reply
  • »
    »
    6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 5   Vote: I like it +7 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i did this and TLEd. unlucky ig

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

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

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

      wow thats fascinating

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

      How did you calculate time complexity? I think my solution is same with yours, they have close time, but I can't find what time copmlexity of my solution is. 285897223

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

        It's the same complexity $$$\mathcal{O}\left(M^2\log_2\left(\frac{N}{M}\right)\right)$$$. In the worst case, all $$$N$$$ checks are split evenly among the $$$M$$$ sections.

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

          Then, isn't the time complexity $$$O(NlogN + M^2log(\frac{N}{M}))$$$? And it's ~$$$2.6 × 10^8$$$(TLE?), but I don't now if we have to include $$$NlogN$$$, if don't it won't be TLE. Or is it $$$O(Nlog(\frac{N}{M}) + M^2log(\frac{N}{M}))$$$, if so it won't be TLE(?).

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

            You're actually not sorting the entire $$$N$$$ checks in a go, but instead section by section too. Without this consideration, it seems like your complexity right, but consider this: If the first part is $$$\mathcal{O}(NlogN)$$$ (ie all checks are in the same section), then the second part is actually going to be $$$\mathcal{O} (M^2+MlogN)$$$ which is quite fast. But if all checks are spread evenly, you get this (slower) complexity instead: $$$\mathcal{O}\left(N\log_2\left(\frac{N}{M}\right) + M^2\log_2\left(\frac{N}{M}\right)\right) \sim 2.3 × 10^8$$$ operations.

            Constant factor is important too. TL is also 2.5 secs, so it won't TLE.

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

    you can use difference arrays to optimize dp

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

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

    UPD: nevermind, it's about C.

    → Reply
  • »
    »
    6 weeks 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
  • »
    »
    6 weeks 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
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just keep a suffix sum of the number of times a check with value x occurs after the ith point you get. Total time complexity is O(m^2 + n) 285984080

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

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

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

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

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

      Sorry i mean O(m^2)..

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

        If $$$O(m^2 * log(n))$$$ can pass how does $$$O(m^2)$$$ not?

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

          Don't know..Maybe create new variables for 5000 times is too slow for this.

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

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

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

    Same here, please post test case if you find it

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

      Please try this: 5 4 0 4 0 0 0

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

        AC, wasn't handling transitions propperly.

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

        This is supposed to yield 0 right?

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

          yes of course. I just hacked myself with this small case to pass test #8, but it seems that #8 is just generally stronger than the previous ones to detect various mistakes

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

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

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

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

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

            You can draw the grid on paper and see how it goes. As in how Pascal's triangle is calculated, same for this one.

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

explain E clearly please :(

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

How to solve E?

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

      Detailed. Thx.

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

        Okay finally I solved it.

        You can see that if on the first time, you have x cards with suit 1, then when you go from suit i to suit i + 1, if you have to "pay" j cards suit 1 to beat j cards on suit i + 1, so the transition is f(i, x) ----> f(i + 1, x — j)

        Let's define ways(i, j) is number of ways when you have i cards and after distributing, the number of cards in first set more than the number of cards in second set j ones. I define j is the different between number of cards in first set to number of cards in second set because j is "free", you can use j to beat another cards

        The formula of ways(i, j):

        ways(0, 0) = 1, ways(i + 1, j — 1) += ways(i, j), ways(i + 1, j + 1) += ways(i, j)

        the formula of f(i, j)

        f(1, j) = ways(m, j)

        if we use x of j cards to beat x cards which suit i + 1: f(i + 1, j — x) += f(i, j) * ways(m, x)

        Final result is f(n, 0)

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

          In fact, $$$f(i, j)$$$ can be seen as $$$ways(i, j)$$$.

          You can solve it bracket match. The first player's cards are (s, the second player's cards are )s. For suit 1, each prefix must satisfy (s are no less than )s. Now $$$f(i, j)$$$ means that we concider first $$$i$$$ suit 1 cards and the first player has more $$$j$$$ cards than the second player. So the fisrt part is as you said.

          Let's see how it works on suit $$$2 \sim n$$$. We know that each suit satisfies the second player has each suit no less than the first player. If $$$f(i, j)$$$ means the first $$$i$$$ cards (s match )s, and the second player has more $$$j$$$ cards than the first player. Note that if we replace the excess (s to )s, it's completely identical!

          So for suit $$$2 \sim n$$$ cards we can use convolution. Let $$$g(0, x) = f(m, x)$$$, calculate $$$g(i, k) = \sum_{x + y = k}g(i - 1, x) \times f(m, y)$$$. After $$$n - 1$$$ rounds, $$$ans = \sum_{i = 0}^{m} f(m, i) \times g(n - 1, i)$$$. Because the more $$$i$$$ )s should be matched by $$$i$$$ (s.

          Here's my submission 285980588.

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

            This is an interesting solution, can you tell me where to learn more about the concept you mentioned towards the end?

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

              Oh, we refer to this form $$$h(k) = \sum_{k = x + y} f(x) * g(y)$$$(* can be any operator) as the convolution. It has the same form as normal convolution. Because it is $$$O(n^2)$$$, an algorithm can solve this form with $$$O(n\log{n})$$$, like NTT and FFT. Generally speaking, in this problem we don't need to use NTT or FFT, because $$$n \le 500$$$, $$$O(n^3)$$$ is enough.

              As for what I mentioned at the end is to multiply many of the same things together. We consider $$$g(i, k)$$$ means that, for first $$$i$$$ suits the second player has more $$$k$$$ cards unmatched. $$$g(i, k) = \sum_{x + y = k}g(i - 1, x) \times f(m, y)$$$ means the $$$i - 1$$$ state how to recursive the next state. Because for first $$$i - 1$$$ suits the second player has more $$$x$$$ cards unmatched. For $$$i$$$ suit the second player has more $$$y$$$ cards unmatched. Then for first $$$i$$$ suits the second player has more $$$x + y$$$ cards unmatched. This is why it comes up.

              Note that convolution is just a form of calculation.

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

                Thankyou very much YipChip

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

      It's hard to believe that my $$$O(N + M^2)$$$ submission 285907904 was nearly TLE.

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

        You are not using fast IO (ios::sync_with_stdio(0)). I'm pretty sure these problems are made considering the answer will have that line of code.

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

          True. It runs in < 1s with this one line: 286094496

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

          Right, I've found many people have this line in their code. Does it matter?

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

            Well, as you can see from sarodesparsh's test, it kind of matters. It desynchronizes C's IO with C++'s IO (aka using cin/cout mixed with printf/scanf may have unexpected behaviour). That synchronization had a cost, and when you stop it, you gain a performance boost. By the way, since we are talking about IO, if you have to print a lot of lines, using '\n' instead of endl is also a good performance boost (because it flushes less often).

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

              Thank you very much, I will try it next time.

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

      You know what, it makes sense. Though some of them do pass due to small constant I suppose. For me, I genuinely had no further ideas beyond binary search and it seemed elegant enough (massive pitfall lol). Hopefully editorial explains prefix sum idea as well.

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

    I don't think binary search should be used at all. I could get it working by simply using maps. Run time < 1s: 286091048

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

285925069

Why is this giving TLE? (C)

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

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

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

      no

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

              thats not how it works, lil bro

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks 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
              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks 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 weeks 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://codeforces.me/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 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    based cache utilization enjoyer

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

Great problem set!

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

      Makes sense, thanks. The constraints were too tight for any overhead.

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

G is cool

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

    U are cool

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

      I don't think it's a well known problem, this is the first time I encountered something like this. Took me a while to came up with the solution during the contest.

      My solution uses:

      Your observation about the answer is correct btw.

      → Reply
»
5 weeks 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 weeks 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://codeforces.me/contest/2025/submission/285946605 thanks in advance !!

→ Reply
»
5 weeks 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 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

nvm

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

My post contest discussion stream

Hints blog

→ Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

285955590

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

    Your solution is O(N + M*M)

    It is impossible to be faster than O(N), you need at least that time just to read all inputs.

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

      m = 5e5 , m^2 = 2.5e7 >= N = 2e6 so we can ignore that ( + N )

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

i have solved two problems and initial my rating was 460 but in this contest it is not showing any rating change, what could be the issue please help me !!

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

    It will update in a while.After the contest ended, there was a hacking phase for 12 hours. Now it has also concluded. Ratings will be changed after system testing. Thanks :)

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

guys, why it isn't rated for me?

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

Hi I submitted a solution for C after contest had ended (during the open hacking phase probably).

And it showed TLE for 6th or some TC. But now in the final standings it shows -1 for C problem, but that was not submitted during contest time. So is this -1 normal ? or some error ? I am new to this platform.

@awoo @adedalic

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

I was randomly checking other people's submission and came across This Submission . This code fails for the following testcase:

16 1
0 1 1 2 2 2 1 2 2 1 1 1 1 1 2 2

Correct Output: 8

Actual Output: 0

Can someone explain why this code was Accepted?

UPD: The author of that code told me that, the continue statement used in his code caused it to fail in my given testcase.

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

Dp_forces

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

Tabulation DP worked in D, recursive gave TLE, same logic in both.

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

Are there a system test soon?Or I'll get my rating later?

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

Can anyone tell me why "re on test8"

285930355

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

    d[sum+a[j]+1]--

    here sum+a[j]+1 could exceed the bound

    you have put a semicolon(;) instead of comma(,)

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

when will rating points be awarded?

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

I solved two questions in yesterdays contest , A and C

both of them showed as accepted during contest

but now its showing that only A has got accepted and submission of C is showing as "In Queue"

Can please anyone explain it?

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

    The submission are being rejudged after open hacking phase against the test cases from hacks and system tests.

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

    After contest 12 hours of hacking phase takes place which is already done for this contest after that System testing takes place. which is going on rn. Your submitted goes thru more test cases during this phase. You can click on problem section you will see there written system testing x% done. during this phase your submitted code will be In Queue (that is being tested)

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

      Ohh got it!

      Thank you sir!!

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

      I solved three questions in yesterday's contest: A, B, and C. If system testing is already done and my problem C fails, my result will be two questions solved, even though I had solved three before.

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

    System testing now

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

Problem E1 and Problem E2: I saw the tutorial done using number of connected components. But does this handle the case of impossible?

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

Hi guys, I am a bit new in CF, please answer my few questions.

If I can solve some easy DP,greedy,Data Structure,Graph/Tree Problem,prefix sum... but can't solve for most hard algorithm (or just know it and can solve very simple problem about it), is div. 2 fit for me?

And how can we increase our rating fast? Is it really hard for me to get to Specialist by only two contest?

And when have the contest with different time? Randomly? or some special type of contest? (Usually the CF rounds are near my sleep time)

Thx for you guys' answer.

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

Problem D recursive dp submission 285916779 2499ms I submitted anathor solution with vector inplace of array dp

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

Problem C: Why did i get TLE test 10?

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

When will rating get changed???

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

    Already Changed I thought, at least mine.

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

Why I get 1900,but still have a blue title?

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

    Maybe it didn't update immediately, like what happend before.

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

Published explanation to Problem E (which I haven't solved in time, but shortly after) https://codeforces.me/blog/entry/135152

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

I submitted solution 285915907 in a contest which shows accepted during the contest and now it is showing runtime error on test 8. When I resubmit the same solution it shows it as accepted.Can anybody please help me out

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

    It seems to me, you search for lower bound in vs[-1], when indx = 0

    // Fill DP table iteratively
    for(ll indx = m &mdash; 1; indx >= 0; indx--){
        for(ll intel = 0; intel <= indx; intel++){
        	ll str=indx-intel;
            ll cti = lower_bound(all(vs[indx-1]), intel + 1) - lower_bound(all(vs[indx-1]), 1);
            ll cts = lower_bound(all(vs[indx-1]), 0) - lower_bound(all(vs[indx-1]), -str);
    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, but don't how it got accepted

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

        Well, it's undefined behaviour. Given that index = intel = str = 0, this two lines look like:

        ll cti = lower_bound(all(vs[-1]),1) - lower_bound(all(vs[-1]), 1);
ll cts = lower_bound(all(vs[-1]), 0) - lower_bound(all(vs[-1]), 0);

        Compiler might optimize this code, checkin the conditions that arguments to the function are the same, and not perform lower_bound calculation and subtraction at all (less likely).

        Or, more likely, lower_bound from a location in memory that is garbage pretending to be a vector, yields some result, which is garbage, but consistent for the same arguments of lower_bound. So you get your cti = garbage — garbage = 0

        Until at some point, lower_bound(all(vs[-1])) fails because you try to attempt some restricted area of memory

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

Can someone help me understand why this got hacked for TLE? 285966035

I'm assuming there's something python specific which I'm doing inefficiently, but I'm not sure what.

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

    You should use pow(a, b, mod) instead of (a**b)%mod.

    This explanation might be wrong, but my assumption would be that in (a**b)%mod, since a**b can get giant, it's slow to work with and leads to TLE on larger test cases. When using pow(a, b, mod), the number stored internally in the pow function never gets above the modulo value, so it isn't as slow to work with

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Oh no... Starting in midnight AGAIN (UTC+8) T^T

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

my solution 285887003 got blocked, i used this site for alg

https://stackoverflow.com/questions/67664402/python-speed-up-powbase-exp-mod-for-fixed-exp-and-mod-or-with-vectorization

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

Can anyone help me to find what's wrong with my D solution Solution.Failing on TestCase 19

→ Reply