null_awe's blog

By null_awe, 5 weeks ago, In English

Thank you for participating! We put a lot of effort into this contest. Special thanks to TheScrasse for contributing to these problems.

Rating Predictions

Also, check out this video editorial for problems A through C2 by one of our testers! https://www.youtube.com/watch?v=hS8Z3k57f6Q

Solutions

1984A - Strange Splitting

Problem Credits: buffering
Analysis: buffering

Hint 1
Hint 2
Solution
Code (C++)
1984B - Large Addition

Problem Credits: flamestorm
Analysis: null_awe

Solution 1

Hint 1
Hint 2
Hint 3
Solution
Code (C++)
1984C1 - Magnitude (Easy Version) and 1984C2 - Magnitude (Hard Version)

Problem Credits: buffering
Analysis: null_awe

Hint 1
Hint 2
Solution (Easy Version)
Solution (Hard Version)
Code (C++)

1984D - ''a'' String Problem

Problem Credits: le0n
Analysis: null_awe

Hint 1
Solution
Code (C++)

1984E - Shuffle

Problem Credits: null_awe, thanks to wavelets for helping with brainstorming
Analysis: null_awe

Solution
Code (C++)

1984F - Reconstruction

Problem Credits: buffering
Analysis: buffering

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)

1984G - Magic Trick II

Problem Credits: null_awe
Analysis: null_awe

Hint 1
Hint 2
Solution
Code (C++)

1984H - Tower Capturing

Problem Credits: flamestorm
Analysis: flamestorm

Hint 1
Hint 2
Solution
Code (C++)
  • Vote: I like it
  • +294
  • Vote: I do not like it

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

Judge solutions are currently being posted. Please enjoy the analyses in the meantime.

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

    Thanks for the fast editorial and challenging contest!!

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

    All judge solutions have been posted.

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

What's MIS?

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

    I was gonna ask the same question!

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

    Maximum Independent Set ?

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

    Maximum independent set (a set containing the maximal amount of vertices where no two are adjacent). The abbreviation is explained in the editorial now.

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

Why the codes not presented?

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

E is nice

»
5 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

very fast editorial! problems are also really interesting, thank you for the round

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

super fast editorial with super fast system testing !!

»
5 weeks ago, # |
Rev. 3   Vote: I like it +103 Vote: I do not like it

F can be solved in $$$O(n \log n)$$$ time: consider the same DP, and sweep the sum over all possible values. All that changes when the sum changes are transitions PS (valid when B[i] + B[i+1] == sum) and transitions SP (valid when sum - 2*M <= B[i] + B[i+1] <= sum + 2*M). Thus, you can store the transition matrices of the DP in a segment tree and do a sliding window sweep over the sum.

H can also be solved in $$$O(n \log n)$$$ time using fast Farthest-Point-Delaunay-Triangulation: the triangles we're allowed to pick are exactly those in the FP-Delaunay Triangulation. There are algorithms for this in linear-time after computing the convex hull.

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

H is doable in $$$O(n \log n)$$$. It's a fun problem to solve in that time, but takes more effort for sure (but still definitely doable from scratch within contest time)

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

    Can you tell more details about the $$$O(n\log n)$$$ solution? I'm very curious about that.Thx

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

      I do not know where to find any description of FP triangulation, but it indeed relies on the correspondence between them. I want to find the partition of the plane into regions such that every region has one of the input points (which I assume form a convex polygon) as the furthest point (as points where three such regions meet are points determining a triangle whose circumcircle contains everything else). All of these regions are infinite and the only two infinite rays for regions $$$R_i$$$ are bisectors between consecutive pairs of points $$$(P_{i-1}, P_i)$$$ and $$$(P_i, P_{i+1})$$$. It is a good start to understand when a region consists of these two rays only — if I'm not mistaken, that's just a local check for intersections of these two and two neighboring bisectors. When you find such a pair then you can remove both of these bisectors from the set of "active bisectors" kept on a cyclic set and insert bisector between $$$(P_{i-1}, P_{i+1})$$$ and continue in a similar manner

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

        Omg, I get it. It's so magical. Thank you.

        I think it works as this :

        We use a priority queue to maintain a set of radii of circumcircles formed by every set of three adjacent points. Each time we take out the one with the largest radius, it can be proven that this circle definitely covers all the points.

        I have come up with a way to prove it, and the general idea is as follows:

        First, we prove a lemma: The circumcircle with the largest radius can always be taken at three consecutive points on the convex hull.

        After proving this, we prove that the circumcircle with the largest radius definitely contains all points, which can be done using proof by contradiction.

        I apologize for my poor English; the above text was translated by AI.

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

        265618123

        I make a submition. It's accepted.I think it's completily correct! Thank you!

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

          Nice, glad to hear that and congrats :)! I am actually not 100% sure about my own claim about local check for when I can commit a triple, but looking at it your way with the radius of the circumcircle certainly sounds convincing :)

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

    Oh , I see it(Farthest-Point-Delaunay-Triangulation) in another comment. Thank you.

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

What was problem E asking for. Was it saying you recursively are doing the step 1 and 2 until you can't anymore and that is considered as doing the shuffle exactly once. I know I'm not understanding because I don't know how they get 6 for example 4 in the sample test cases.

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

    Same. I solved without doing it recursively and it was wrong, so I solved the sample case by drawing it then guessed the solution from it.

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

    My understanding for example 4 in E:

    Choose 5 as root, change (5,8) to (5,1)

    change (1,8) to (1,7)

    change (1,10) to (1,6)

    and you have 6 leaves now (includes 5)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Edit: Nvm!! I made a blunder

    I couldn't even get test case 2.
    My approach:
    Let's choose 5th node: 1->2->3->4(root 1),5(root 5)
    Then choose 4th node: 1->2->3(root 1), 4(root 4), 5(root 5)
    Then choose 3rd node: 1->2(root 1), 3(root 3), 4(root4), 5(root 5)
    Then choose 2nd node: ...

    Let's connect back
    root 2 is connected to 1: 1->2
    root 3 is connected to 1: 1->2,1->3
    root 4 is connected to 1: 1->2,1->3,1->4
    root 5 is connected to 1: 1->2,1->3,1->4,1->5
    ans: 4

    correct me if I am wrong.

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

super fast editorial, thanks but i sleep now. Farewell!

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

I solved D without Z-algo or hashing, with time complexity of $$$O(m \cdot sqrt(m))$$$ by only brute force. Don't know it is legal or not but it passed the system testing anyway with 93ms (pretty surprised).

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

    Can you link your submission, so I can try to hack it?

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

      Here is it: 264957961 (That account of mine has been locked commenting for 48 hours, that's why I use this account to comment. I know using multiple account is considered bad, but I didn't join any contest from this account for a long time to avoid this bad behaviour).

      If it is legal, I hope you could explain why this time complexity could pass.

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

        Can u explain ur approach ?

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

          Store all indices such that $$$s_i \neq 'a'$$$. Let the number of such indices be $$$m$$$ and the vector store those is $$$a$$$. Now, if $$$m$$$ is $$$0$$$, then the answer is $$$n - 1$$$, you can see it in the sample case $$$1$$$. If $$$m$$$ is not $$$0$$$, then there will be at least $$$1$$$ character $$$\neq 'a'$$$ in $$$s$$$. The problem makes us to partition the vector $$$a$$$ such that indices of each part in $$$a$$$ forms equal substrings in $$$s$$$.

          For example, consider $$$s = abcadaaabcadaa$$$. Then we can take $$$bcad$$$ or $$$bcadaaabcad$$$ as a valid string $$$t$$$. It can be easily seen that each partition need to be the same size, so we iterate all the divisors $$$i$$$ of $$$m$$$, and check if we can divide $$$a$$$ into $$$\frac{m}{i}$$$ equal substring. The checking part could be done by brute force (corresponding indices must be the same character, and the gap between character of each partition must be the same). After checking that the current partition is valid, we need to pad some character $$$'a'$$$ to the left and right of the substring we found then add it to the answer.

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

            i am sorry but can you explain a bit why $$$a$$$ has to be partitioned into equal sized parts.

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

      https://mirror.codeforces.com/contest/1984/submission/264965359

      I have also done in the (O(n.sqrt(n))) passed in 62ms

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

    This was our original intended solution. It is supposed to pass.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It would be really helpful if you could explain your appraoch a bit

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

Super fast editorial.

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

can anyone explain why i can't hack? there is no button

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

    You can't hack after contest in normal Div. 1 and/or Div. 2 rounds (except for Educational rounds). There's a thing called uphacking, but it's available only for Candidate Masters and above.

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

Wow, the solution to C turned out to be clever, I have a more general solution that doesn't use the fact we only need to use op2 once, rather it's just brute force + dp:

Solution

The solution for C2 is the exact same, maintain $$$cnt_{2, n}$$$ array where $$$cnt_{i, j}$$$ is the number of ways to get to $$$dp_{i, j}$$$, the rest is just case handling to check which one took the place of the current dp and updating the $$$cnt$$$ accordingly

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

    plz share your solution of c2.

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

      check my comment, I'll be glad to help you:)

      dp solutions for C1 && C2 (tap)

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

        I read that already. I got what you said but was not able to understand your code.

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

      I haven't coded it but I can try to explain it.
      Assume that $$$dp_{0, i+1}$$$ was equal to $$$|dp_{1, i} + c|$$$(the max of those values is this). then the N.O.W you can reach the state $$$(0, i+1)$$$ get's increased by the N.O.W you can get to $$$(1, i)$$$ meaning: $$$cnt_{0, i+1} += cnt_{1, i}$$$

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

    u can just do dp[0][i] = dp[0][i-1] + c bcz it s obvious that others both are greater than it

    https://mirror.codeforces.com/contest/1984/submission/264912921

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

      I don't think so, maybe abs(dp[1][i-1] + c) be greater

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

        i mean dp[1][i] for smallest one not the biggest one

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

    dp1,i+1=min(dp1,i +c,|dp0,i +c|,|dp1,i +c|), why we need |dp1,i +c| for minimum? As |dp1,i +c| >= dp1,i +c. I think this is not needed

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

      we only need dp[1][i] = dp[1][i-1] + c for minimum

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

      tbh I just copied the dp[0] one and edited it, yes correct

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

    Somehow I also end up writing similar solution 266791621 but couldn't prove why taking care of only min and max value of C is correct. Do you have any idea for it?

    Update: I got the proof

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

      I don't have a super mathematical proof, I'm just gonna say my reasonings:
      When will You use operation 2? When the value is negative and the addition with C will not increase it. So when the value is the minimum possible, assume that You wanna use operation 2 at the current stage, thus, You should know what was the minimum achievable value till now, to check if this will be beneficial, so keeping the minimum value is mandatory.

      The same can go for Op1 but it's a bit more obvious so ! gonna explain it

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

DP solutions for C1 and C2:

C1: let dp[i][0] be minimum score when we made i operations, dp[i][1]maximum score

C2: let dp[i][j] be amount of times we can get score j after i operations. as we can look only at max and min values, let's clear useless conditions after every step, then there will be only O(1) new values every time, so total complexity is O(n) if u use hash table, O(nlog(n)) — if BST (for e.g. std::map)

C1 code: 264967072

C2 code: 264965726

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

    You don't need a set/map or hashtable for coding c2, use IF brother, but this made the implementation way more clear

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

      of course, u are right, but such structures were made to make our lifes easier)

      the simpler the code, the fewer errors=)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        actually no need u can update dp based on just i-1. Here are my submissions C1:264932150 C2:264949789 Overall complexity is O(n), and the code stays simple

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

          liked your code it's similar to what I was thinking but you made it so much shorter

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

    Thank you. Really neat code!

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

    How did you come up with keeping only minimum and maximum did not get that

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

      To achieve the final maxima, there are two ways: either keep making the value a positive integer as large as possible, or keep making it a negative integer as small as possible (then apply absolute operation to it at the end). Hence their intuition to keeping only min+max.

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

    can u explain more c2 bro ?

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

      of course, I'll try

      have you got my c1 solution?

      since we can keep only max and min score on every step(you can find prove by AkiLotus upper), let's do it on every step of our DP. we have 2 conditions and from every condition we can chose 1 of to 2 different actions, which means there will be not more than 2 * 2 = 4 new different scores. let's count each of them. but as we said earlier, we don't need to save all of them — we just need to save max and min score. okay, now let's count amount of times we can reach score we saved. initially, dp[steps = 0][score = 0] = 1, because we starts from score = 0. further we can go from score to score + a[i] or to abs(score + a[i]).

      for e.g.: cur_max = max(dp[cur_step]), mx_times = dp[cur_step][cur_mx] then dp[cur_step + 1][cur_mx + a[cur_step + 1]] += mx_times and dp[cur_step + 1][abs(cur_mx + a[cur_step + 1]) += max_times, for minimum score we do it in same way

      if yours dp is vector<map<ll, ll>>, then u can write it as I did it higher. but y also can use dp as vector<vector>, but IMO my variant is simpler

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

        correct me if m wrong ,

        u are calculating for each index the 4 possiibles values ( in the next dp ) ( and count the ways to achieve them ) and u are only storing the maximum and minimum of them in ( in curr dp )

        and so on ?

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

          yep, I calculate no more than 4 new values and store no more than 2 of them(sometimes min == max, so we have to store only 1 value)

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

        great approach. I was finding the dp approach. Thanks

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

        Here is a simplified code

        void solve() {
            int n;
            cin >> n;
            vl arr(n);
            in(arr, n);
            map<ll, map<ll, ll>> dp;
            dp[-1][0] = 1;
            for (int i = 0; i < n; i++) {
        
                ll mx = LLONG_MIN, mini = LLONG_MAX;
                for (auto &j : dp[i - 1]) {
                    mx = max(mx, arr[i] + j.first);
                    mx = max(mx, abs(arr[i] + j.first));
                    mini = min(mini, arr[i] + j.first);
                }
        
                for (auto &j : dp[i - 1]) {
        
                    if (arr[i] + j.first == mini || arr[i] + j.first == mx) {
                        dp[i][arr[i] + j.first] += j.second % MOD;
                        dp[i][arr[i] + j.first] %= MOD;
                    }
                    if (abs(arr[i] + j.first) == mx || abs(arr[i] + j.first) == mini) {
                        dp[i][abs(arr[i] + j.first)] += j.second % MOD;
                        dp[i][abs(arr[i] + j.first)] %= MOD;
                    }
                }
            }
            ll mx = LLONG_MIN;
            for (auto &i : dp[n - 1]) {
                mx = max(mx, i.first);
            }
            cout << dp[n - 1][mx] % MOD << endl;
        }
        
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I scrolled into the comments looking for a $$$dp$$$ solution just like this! Thank you.

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

can sm1 tell me what are the 3 strings that match in this tc , problem D , abbaaaabbb output : 3

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

    1- abbaaaabbb (whole string)

    2- bbaaaabbb (whole string except first character)

    3- b [ it's clear :) ]

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

    nvm got it : { b , full string , bbaaaabbb }

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

Wow these editorials were fast. Thanks!

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

First solve for H was from rainboy.

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

Anyone solved C using dp,it was kind of more obvious for Easy version then u just add another state to dp for num_ways to make a value,nice contest, i really like the C1 and C2

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

    can you please explain c2 ?

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

      i think coin change on cses is very similar to c2 .c1 was very similar to knapsack

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

        yeah, it is knapsack dp cause u are kind of fillinf container,adding based on just the previous state,i still that was nice problem, we really need such high quality tasks in codeforces rounds.

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

      first i assume u understood how C1 is done using dp,now lets call dp[i][0] minimum value of c up to index i element and dp[i][1] maximum value,first we compute it using smae formula of C1,now count number of ways to do it,now at every step we have four choices either use the minimum value of i-1 or max value of i-1,both with or without abs value,we just update number of ways,however we need to be careful as if minimum value equals max value for index i-1 we only consider two choices with or without abs value(as the two others are same and we would be double counting),u can check my submission for implementation details.

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

        can you please elaborate on the last point, I couldnt understand

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it
          I wrote clean code based on his idea and it AC's. Hope it helps
»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

in E MIS was a big hint, is MIS very standard in many problems? when I heard MIS problem became relatively very easy, proving MIS (excluding root) is the answer was also not difficult, but how would someone think that MIS could be the answer, is it just more problem-solving of a similar type?

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

    what is mis

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

    I got there by exploring specific cases. Like, first, I noticed that you can make the answer $$$\frac{n}{2}$$$ on a bamboo, but $$$n - 1$$$ on a star. Then I wondered if I could make at least $$$\frac{n}{2}$$$ on any graph. The two specific types made me think of bipartiteness, since the vertices that become leaves belong to one part in them. So I tried to show that you can take the larger part and make these vertices leaves. Got the construction and figured it's actually only necessary for any two chosen vertices to not be adjacent, which is exactly a MIS problem.

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

      okay, you tried many things narrowing down the answer which is no two chosen vertices are adjacent. basically not even knowing what is MIS one could have solved this, thanks!! i think i just did not try hard enough!

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I got there by naturally considering when a node can become a leaf.

    Well, either it already was a leaf and got chosen in the first operation. Or, it got chosen as a root after all its neighbours. The second condition obviously gives rise to MIS

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

      Proving that these 2 conditions are sufficient is not hard. If the set of leaves we want is an independent set, then we are guaranteed to find a node we do not want to become a leaf in any tree of size >= 2, thus just choose it and recur till we are left with trees of size 1.

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

        Can you plz explain the problem E's implementation?? Like what is the dp states and how are transition happening?

»
5 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

The sample for F is such a garbage.

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

G is similar to this problem

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

why c2 : Thus, we have the choice of using option 2 or option 1 at any index j<i where the prefix sum is non-negative

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

Can someone help me explain this solution for C2? I just guessed a conclusion during the contest

my submission

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

Both C1 and C2 are akin to the knapsack problem in dynamic programming, correct?

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

Hey, in problem 2 can anyone help me that what is the problem in this logic it's throwing wrong answer on 392nd token test 2

https://mirror.codeforces.com/problemset/submission/1984/265022174

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

Hi, I got tle for C1 (easy). I tried dp (memorisation using maps)

https://mirror.codeforces.com/contest/1984/submission/264928809

Would be great if someone could give me insights on this and share a dp solution that got accepted for C. Thank you!

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

we are told constantly in our college not to use global and static variables, is it a good a practice?

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

Hey Guys I solved C1 (not in the contest) using dynamic programming using two dp

dp_max: the max sum we could create till i taking ith 
dp_min: the min sum we could create till i taking ith

Transitions:

if(arr[i] < 0){
            dp_max[i] = max(dp_max[i-1] + arr[i], abs(dp_min[i-1] + arr[i]));
            dp_min[i] = dp_min[i-1] + arr[i];
        }
        else{
            dp_max[i] = abs(dp_max[i-1] + arr[i]);
            dp_min[i] = dp_min[i-1] + arr[i];
       }

with base case dp_max[0] = 0, dp_min[0] = 0 (---1 based indexing)

This solution got accepted now can anyone tell me how will I use these transitions to build the count array which will count all possible ways to acheive this maximum ?

Ps I guess it should be solved using the same way we find all the LIS, or All the min paths in Dijkstra algo. Pls help

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

In Problem C2, I am using below code to calculate power of 2, but this is giving stack overflow error. Any idea why?

using ll = long long;
 
long long power2(int n) {
    if (n == 1) {
        return 2;
    }
    long long p = power2(n/2);
    if (n & 1) {
        return p * p * 2;
    } else {
        return p * p;
    }
}
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    overflow. you need to use mod. Also, too many recursive calls will give stack overflow.

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

      Where?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        Using Mod

        Also, note that if you are calling this function multiple times for large values of n and are not caching the results, it will give stack overflow error.This is because very large number of function calls will be made. So, its better to cache the results.

        Using cache
»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

jiangly must be tired of getting second place to tourist. Anyways, their consistency is insane.

»
5 weeks ago, # |
Rev. 5   Vote: I like it +7 Vote: I do not like it

Another approach for B problem: As all the digits are large, the sum is bound to increase by 1 digit, so if $$$x$$$ is large and has $$$n$$$ digits, then $$$a$$$ and $$$b$$$ must have $$$n-1$$$ digits.

What is the largest large number with $$$n-1$$$ digits?

Answer

After that, I subtracted the largest "large" number of $$$n-1$$$ digits from $$$x$$$, resulting in a number say $$$y$$$.

Now, we have to ensure two conditions:

  1. $$$y$$$ has a length of $$$n-1$$$.
  2. $$$y$$$ doesn't contain any digit as $$$0$$$ (why?)
Proof

Hopefully, this is easy to implement and you can see my submission here: 264891168

Please let me know, if there is some fault in the solution, or any other clarification is required?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think I have a far simpler answer that does require any integer conversions and works purely with strings, thus it can be used for very very large numbers:

    Basically, for any number to be right, 4 conditions must be met:

    • Number must not be a single digit.

    • The first digit must be a '1'.

    • The last digit must not be a '9'.

    • All remaining digits must not be a '0'.

    Please let me know if there's any holes in my logic.

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

      Yeah, its precisely the same :) I just wanted to write a formal proof ><

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I am struggling with a testcase right now on Problem B, the judge is saying that it expected an answer of YES on the number 793, which I believe should be a no.265101056

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

    You might have read it wrong. 793 was the 17th testcase. You got a WA at the testcase on the number 1460 instead.

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

      Thank you very much! That indeed helps, although I found out that my approach was flawed :D.

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

In C problem, Why we need to choose second operation only once. Can anyone give any testcase ?

»
5 weeks ago, # |
Rev. 10   Vote: I like it 0 Vote: I do not like it

How can I fix the memory limit exceed for my solution for C2 ? 265166920

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

    The way you utilized the queue was actually a bruteforce, which will not work. Take this test for example:

    1
    40
    -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36 -37 -38 -39 -40
    

    Answer is just $$$1$$$, but due to constant doubling, you'll quickly MLE/TLE yourself.

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

      Ohh,I get it. Is there anyway I can optimise it ? Or should I scrape it think of something else ?

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

        I can only advise you to read the tutorial. Your current solution is practically an exhaustive search, and there are a lot more corners to prune with some mathematical intuitions.

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

Can someone elaborate on how implementation works for E ? Proving the MIS lemma is easy, but I can't figure out how to implement the dynamic computation. Like what is the dp formula ? I've been trying with rerooting and dp on edges as well

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

    Okay I figured something out, the implementation was harder than what I expected at first. Still, this problem is lovely, I don't regret wasting 2 hours on it instead of solving D during the contest !

    Basically my idea was to implement is to root the tree at a none-leaf node (exists if n > 2). Then I compute the MIS for going up and down the tree, starting at a given node (with dp). For going down, it's easy dp, it only depends on doing down for subvertices that are lower. But I need to store the state that I chose for each child when going down, that I will use for going up.

    Indeed, when going up from node i, whose parent is p, I need to add the value of going up with p, plus the value of going down with p (maybe minus one if p is set to be in the MIS), minus the value of going down with i, whose state is set by what I chose when going down with p.

    It would be clearer with maths formulae but I wanted to keep my comment short since idk if anyone will require my hindsight.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For me I root the tree at a leaf node. a = MIS if choose root
    b = MIS if not choose root
    If a<=b, return b+1
    Else we check if the MIS containing the root also contains all the leaves. If MIS also contains all the leaves, return a, else return a+1 (because we can root the tree at that leaf).
    I use DP from a node to each of its children, state (a, b, a_spare_leaf, b_spare_leaf)
    Solution https://mirror.codeforces.com/contest/1984/submission/266256460

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

Can anyone help me with the problem C2? i am getting WA on test 2. I could not really think of where i am wrong. Thank You here is my submission

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For A, if the array isn't [1, 1, 3, 3] also impossible? Hint #1 and the solution code show that it is impossible only if all elements are equal.

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

    Try to color the first 3 elements red and the last one blue.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My code for problem D is failing for test case no.83 , can anyone please explain if double or multiple hashing is the only way to avoid this 265689130? i used first time polynomial hashing with mod 1e9+9 and prime 31 only 28 test cases passed , then later using 1e9+9 and prime as 53 it passeD 83 test cases. Is it possible that there exists a more better prime for this to pass with single hashing ? le0n null_awe

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

    Not actually sure — I don't remember ever using string hashing, so I don't have experience with hacks and string hashing. I think I've heard people say to randomize primes so nobody can reverse engineer hack test cases (if you want to stay single hashing).

    Again, I don't know string hashing very well, so not sure if this is a robust solution.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem ratings are out, you can maybe update the prediction table? null_awe

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div-2 D
I think a much simpler solution can work,
We will try to find candidate $$$t$$$ where the first and the last characters are non-$$$a$$$
Such a $$$t$$$ must start from the first non-$$$a$$$ character. we will iterate over the endpoint to check for validity.
To check if we have a valid $$$t$$$ we will check for all non-$$$a$$$ characters if the number of characters in $$$t$$$ are divisors of the frequency of corresponding alphabet in $$$s$$$, and all of them leave the same quotient.
There will be at most $$$O(\sqrt[3]{n})$$$ such $$$t$$$, which will be even lower in practice.

And you can check the validity of this $$$t$$$ in $$$O(n)$$$.
Also you can compute how many prefix and suffix $$$a$$$ can be added to this $$$t$$$ and still result in a valid $$$t$$$.

Submission — 265896129

  • »
    »
    4 weeks ago, # ^ |
    Rev. 9   Vote: I like it 0 Vote: I do not like it

    Yeah did the same but used string hashing for faster check too, I believe my solution is just $$$\mathcal{O}(n + \sqrt[3]{m} * log{(m)})$$$ where $$$m$$$ in the number of non-a characters, 265886340

    if my time complexity is incorrect lemme know the correct one

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello , can someone help me with my doubt in Ques D) Magnitude(Hard version) , it would be great great help. My solution is giving a wrong answer on this far test case.

This is the code that i have ---->

https://mirror.codeforces.com/problemset/submission/1984/268592519 PLZ PLZ PLZ HELP ME , AM STUCK AT THIS

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is checking adjacent elements only sufficient for F?