wuhudsm's blog

Codeforces Round 930 (Div. 1, Div. 2) Editorial
By wuhudsm, 9 months ago, In English

Thank you for participation and we hope you enjoy this round :)

D2A — Shuffle Party

Idea : chromate00

Hint (for thinkers)
Hint (for observers)
Tutorial
solution

Video editorial by aryanc403 https://www.youtube.com/watch?v=lLmVzA49BRM

D2B — Binary Path

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

D1A — Bitwise Operation Wizard

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

Video editorial by aryanc403 https://www.youtube.com/watch?v=jfcx1Rs8I28

D1B — Pinball

Idea : wuhudsm

UPD: It conflicts with https://mirror.codeforces.com/contest/733/problem/E. This is a coincidence. There are no excuses. Very sorry for any inconvenience caused to everyone.

Hint1
Hint2
Hint3
Tutorial
solution

D1C — Pokémon Arena

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

Video editorial by aryanc403 https://www.youtube.com/watch?v=ysdozposXkQ

D1D — Bitwise Paradox

Idea : Psychotic_D, MagicalFlower

Tutorial
solution

D1E — Yet Yet Another Permutation Problem

Idea : wuhudsm

Hint1
Hint2
Hint3
Tutorial
solution

D1F — Grand Finale: Circles

Idea : chromate00

UPD: The TL was a bit too loose, and unintended solutions with $$$\mathcal{O}(n \log^2 (1/\epsilon))$$$ complexity passed during the round. For the sake of the problem itself, I suggest that you try to solve assuming a $$$1$$$ second time limit.

Tutorial
solution
  • Vote: I like it
  • +192
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

fast editorial

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

    ++ fast system testing

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

    kindly help me in this DIV2 -B

    int n;

    void solve(){

    cin>>n;

    string u, d; cin>>u>>d;

    string s = u[0] + d;

    string c=s;

    int cnt=0;

    for(int i=0;i<n;i++){

    s[i] = u[i];

s[i+1] = d[i];

if(s==c) cnt++;

if(s<c) c=s, cnt=1;

    }

    cout<<c<<'\n'<<cnt<<'\n'; }

    It is giving TLE -- but it is running in O(n) time

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

      哥们，string 比较大小时间复杂度很高，每次比较大小都是O（n），因此整个时间复杂度是O(t*n^2),

      so ， This code may exceed the time limit

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

        yeah. I got the same problem, so I had to switch the solution entirely. Luckily, I was able to solve it.

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

        What's this, 混合双语解答问题吗，I don't think anyone can understand this :(

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

          你不就understand了嘛qwq

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

      If in terms of string comparison, you can use a hash plus binary search, binary search to find the longest length of the same prefix, the next position is the first different position, and then compare the characters at that position, this only requires O(logn), preprocessing requires O(n). By machine translation, there may be errors,you can continue to ask me.

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

Fast Editoral

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

Fast editorial! Never seen one posted so fast after a contest.

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

Great round ! I really enjoyed solving problem B and C. Congrats to the authors !

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

I don't know if I should be happy that I solved div1A+B fast or sad that I spent over an hour on C and didn't get it!!

Either way, thank you for the amazing contest! I've just got to read the editorial for C now ^_^

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

fast editorial

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

Interesting problems, but don’t you think that the difficulty of Div.1 is A > B > C?

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

For problem F I didn't have enough braincells for solving the k=3 case so I simply used the idea from Radewoosh's blog number 5 https://codeforces.me/blog/entry/61710 (binary search for the radius + the blog for finding the intersection after shrinking circles + using golden-ratio search to optimize).

Also didn't realize the k=4 case apparently didn't exist, hopefully it's not FST due to time seed.

Edit: chromate00 idk if it was you that put that note for F, but doing binary search and ternary search while doing the rest as in the editorial seems fine to me. The expected number of retries in the algorithm is O(log^3N) I'm pretty sure, so in the end it's something like O(log^3N * log^2precision) + O(N).

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

    It should be fine if you do the rest of the blog along with one binary search. I haven't tested with two, though. The $$$\mathcal{O}(n\log^2(1/\epsilon))$$$ I was referring to was the nested golden section search where the $$$\mathcal{O}(n)$$$ is simply from calling the objective function. Do note though, that we do have a tester solution with $$$\mathcal{O}(n\log^2(1/\epsilon))$$$ complexity that passes in ~800ms.

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

      hmm I just submitted $$$O(n\log^2(1/\epsilon))$$$ and it's faster than everyone else's solutions ...

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

        I believe it is one of the $$$\mathcal{O}(n \log^2(1/\epsilon))$$$ we intended to allow. Most of the $$$\mathcal{O}(n \log^2(1/\epsilon))$$$ I meant to block were the ones that do ternary search on both $$$x$$$ and $$$y$$$, to maximize $$$r$$$. In the meantime, a tester's solution using binary search on $$$r$$$ with a clever check function passes in about 800ms.

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

          Ok.

          Ok. Btw, I tried uncommenting the first random shuffle in the model sol and resubmitting with different random seeds, and they all gave different outputs. So I assume the model sol is not correct.

          Example code (only difference is the seed):

          AC: 249100355

          WA:

          249108458

          249116485

          249116654

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

            As far as I believe, the issue is in the precision of the type itself. It can be fixed by implementing a class for $$$\frac{p}{q}+\frac{r}{s}\sqrt{t}$$$, so I will consult the coordinator about replacing the model solution with one that uses exact computations. The current version of data was cross-validated with BurnedChicken's binary search solution, which made me believe it is precise enough.

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

Is Div2B is possible by doing just simple dfs?

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

    No, it's too slow.

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

      How?Shouldn't it be 4*10^5?Or I am making miscalculation here,can you give me the tc for a bfs for the test cases?

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

        On each position in first string you will have 2 ways you can go, right and down, when you go right you do the same choice, but when you go down you have to go right to the end of the string, so in total you have O(n*(n+1)/2) time complexity, and because you have 10000 tests in one testcase you have n*(n+1)/2*10000 = 200'001'000'000'000 total operations which is obviously too much.

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

    Can you please share the approach , thanks !

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

Interesting round! Really like it when there is an interactive problem in the round

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

Div. 2 PROBLEM B (Binary Path) video Editorial : YOUTUBE EDITORIAL LINK Audio : Hindi

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

Fast editorial, and...

using namespace atcoder; is found in problem 1E !

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

This Round was really amazing. I really enjoyed this round

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

Why is the system testing frozen?

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

https://codeforces.me/contest/1937/submission/248965536

Why is this giving tle? It is nlogn

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

    You're keeping n strings in map, all of which have length more than n, so O(n^2) memory and even bigger time complexity.

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

    The first thing I can observe in your solution is that you should use unordered_map when the type of keys is string. It uses hashed keys so that the problem due to the comparison time of string values can be resolved.

    Edit: Similarly, you can use unordered_set instead of set

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

    Also you are deleting first charachter of a string and you are doing that n times so only that is O(n^2) which is too slow.

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

      But isnt deleting the character an O(1) operation?

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

        Nope, deleting character from a string is O(n)

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

        deleting the last $$$m$$$ characters is $$$O(m)$$$, but deleting the first letters is like moving the rest to the front, which is $$$O(n)$$$.

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

I love D1A = D2C. Very Beautiful problem!

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

    Why do we try step 3 in Div2 C? Do we need to find the smallest one?

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

      When you ask a question it uses bitwize or, but for answer you need bitwize xor

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

      Yes. A xor B = (A or B) - (A and B), and the candidates obtained after completing the step 2 satisfy the condition that the bit in a particular digit has a value of 1. It is because maximal value of pi or pj is 111...111(2) form.

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

        Yeah, I see. But I think when I finished the step 1, I can get the position of n-1. And then I don't understand why step 2 is needed. Assum that the position of n-1 is x. I think we can get the position of candidate that can make px^pk maximum without step 2. What is the mistake? This is my code but I got wrong answer. https://codeforces.me/contest/1937/submission/248971409 Please let me know the reason.

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

Super fast editorial

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

This is hard!

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

In Div 2 B, how to prove that if a=b, then it's optimal to move to the right?

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

    If you go right, you always have the chance to go down.There by you can have minimum among those both

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

      Thank you! I thought it won't always be optimal and therefore tried to solve it by dp

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

why is ffush giving idleness, but changing all to cout.flush() is AC

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

    Because you have "ios_base::sync_with_stdio(false);" in your code so fflush doesn't affect cout.

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

for problem D2B — Binary Path ...

you can also use dp for counting number of paths. Submission

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

    3d dp is too much to understand. I better stay away from it.

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

    also possible with 2d dp

    code

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

      The first dimension is just the combination of two arrays

      the array for visited checking dp[0] and the array for the answer itself dp[1]

      This doesn't increase the time complexity of the code; in fact, it optimizes the time complexity by avoiding the need to reassign the entiredparray as not visited for each test case. Instead, I only need to check whether theidof the current state is equal to the current test'sid. If it is, then the current state has already been visited during the current test case.

      This is why there's a difference between our time complexities of our codes

      Spoiler

      I use array instead of vector and I don't reassign it at each test case

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

Can anybody explain this bigotry.

248984409 Global Dp arrays passes easily.
248971939 Dp arrays passed by reference gives MLE.

Is pass by reference soooo bad ?????

Exactly the same solution. The little rating points that I had are now gone. :(

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

    In your submission with the DP-array passed as reference you accidentally create an n*n array instead of 2*n. :/

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

      I'll go slap myself a couple hundred times. Thanks a lot for answering.

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

F: "Using nested ternary searches does not help very much. The time complexity will be $$$O(n \cdot log^{2}(1/ϵ))$$$, but the constants are large due to multiple function calls and floating point operations" lol 3 out of 4 accepted submissions use nested ternary searches

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

    We tested nested ternary searches, but not golden section search. That was why I didn't see that coming. This is entirely my fault for not having considered.

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

Problem B can also be solved by dp. My submission https://codeforces.me/contest/1937/submission/24898172.First we create most optimal string and then apply dp for how many ways we can create this string.(Basically number of paths).

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

I used a similar approach to solve problem D2B: I'll explain it here to hopefully help someone. There are only n possibile way we can go from (1,1) to (2,n), that are characterized by the point in which it goes downward. We want to remember this point.

  1. To find the lexicographically shortest path, it is enough to choose of going downward if down = '0' and right = '1' or if we are in position (1,n), otherwise we continue on the right.
  2. To count how many path of the same type are there, startig from the point in wich it goes downward, we increment a counter until the char in position (1,i) == (2,i-1), for each decrementing i. This means that turning down before we did wouldn't have modified the path.

Time complexity: O(n).

My submission as reference: 248990348.

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

Please can somebody tell me why this is giving TLE? 

#include <bits/stdc++.h>
using namespace std; 
 
#define ll long long 
#define ull unsigned long long 
 
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
 
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n; 
        vector<vector<char>> board (2, vector<char>(n, ' ')); 
        for (int i = 1; i <= 2; ++i) {
            string s; 
            cin >> s; 
            for (int j = 1; j <= n; ++j) {
                board[i-1][j-1] = s[j-1]; 
            }
        }
        vector<vector<string>> dp1 (2, vector<string>(2, "")); 
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < 2; ++i) {
                if (i == 0 && j == 0) {
                    dp1[j][i] = board[i][j]; 
                    continue; 
                }
                if (i - 1 >= 0) {
                    if ((int)dp1[j%2][i].size() != i + j + 1) {
                        dp1[j%2][i] = dp1[j%2][i-1] + board[i][j];
                    } else {
                        dp1[j%2][i] = min(dp1[j%2][i], dp1[j%2][i-1] + board[i][j]); 
                    }
                }
                if (j - 1 >= 0) {
                    if ((int)dp1[j%2][i].size() != i+j+1) {
                        dp1[j%2][i] = dp1[(j+1)%2][i] + board[i][j]; 
                    } else {
                        dp1[j%2][i] = min(dp1[j%2][i], dp1[(j+1)%2][i] + board[i][j]); 
                    }
                }
            }
        }
        cout << dp1[(n-1)%2][1] << '\n';
 
        vector<vector<ll>> dp2 (2, vector<ll>(2, 0));
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < 2; ++i) {
                if (i == 0 && j == 0) {
                    dp2[j][i] = 1; 
                    continue; 
                }
                dp2[j%2][i] = 0; 
                if (dp1[(n-1)%2][1][i+j] == board[i][j]) {
                    if (i-1 >= 0) dp2[j%2][i] += dp2[j%2][i-1]; 
                    if (j-1 >= 0) dp2[j%2][i] += dp2[(j+1)%2][i]; 
                }
                // cout << i << ' ' << j << ' ' << dp2[i][j%2] << '\n'; 
            }
        }
        cout << dp2[(n-1)%2][1] << '\n';
    }   
 
    return 0; 
}
→ Reply
»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

There is a square-root decomposition solve for bitwise paradox in $$$O(n\sqrt{n} + qlogn\sqrt{n})$$$, assuming DSU is $$$O(1)$$$. By breaking the array down into sqrt blocks, we can merge in ascending values of $$$a_i$$$ in each block and store the maximum prefix, suffix, and subarray OR in each block for such $$$a_i$$$. We can now simply binary search for a value $$$x$$$, merging blocks from left to right, keeping track of the current longest suffix and checking if the maximum subarray OR $$$\geq v$$$. Submission: 248991851

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

    I tried same solution for Div1D, but I got some memory trouble and failed to solve within the contest time..... (I used 4 * 4 * N * sqrt(N) 8bit integers, which seems too large) My submission: 248971206

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

      I made the blocks a bit bigger so my solution would take less memory, but my solution is still very tight on memory.

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

    Same thing can be done using segment tree to reduce the memory to NlogN and complexity to NlogN 251321474

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

Can B be done with string hashing? After getting the best possible string, we can just try all possible paths in O(1) each?

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

Thanks for the organizers, hated this contest

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

At div1 C, can't you just have edge from X[rank[i]] to i with cost 0, meaning that you defeat the pokemon i?

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

The solution to problem 1D is really similar to problem 1004F.

I modified about 3 lines of code and added a ST table and got accepted :(

→ Reply
»
9 months ago, # |
← Rev. 5   Vote: I like it +52 Vote: I do not like it

For problem D1A — Bitwise Operation Wizard, we can actually reduce the number of queries needed to at most $$$2n$$$. Here's how.

From the editorial, we can see that we have $$$3$$$ steps, where the first step is finding first number (the editorial encourages us to find the maximum for this one) with $$$n-1$$$ queries, the second step is finding candidates for second number by finding maximum OR value with $$$n-2$$$ queries, and the third step is finding minimum from the candidates (since the minimum produces maximum XOR with the first number, the proof is left to the reader as exercise) with $$$sz-1$$$ queries, where $$$sz$$$ is the number of candidates and $$$sz \leq n$$$. This optimization mainly focuses on the first step.

Now, let $$$2^k < n \leq 2^{k+1}$$$ for some integer $$$k \geq 1$$$ (since $$$n = 2$$$ is pretty trivial lol). If we do our observation correctly, we'll notice that $$$p_i \oplus p_j \leq 2^{k+1}-1$$$. Funnily enough, we can reduce the number of queries in the first phase to $$$2^{k+1}-n$$$ queries. This can be done by realizing that any number from $$$2^{k+1}-n$$$ to $$$n-1$$$ are always valid candidates for the first number $$$p_i$$$, since they always have a second number $$$p_j \leq n-1$$$ such that $$$p_i \oplus p_j = 2^{k+1}-1$$$. And so, we only need to use $$$2^{k+1}-n$$$ queries to find any number that is $$$\geq 2^{k+1}-n$$$ (by knowing that the number is larger than at least $$$2^{k+1}-n$$$ other numbers).

From my calculation, from all of the possible permutations of $$$[0 \dots n-1]$$$, the third phase actually uses at most $$$n-2$$$ queries if $$$n = 2^{k+1}$$$ and at most $$$n - 2^k - 1$$$ queries otherwise, since the number of queries actually depends on the size of the candidates.

I believe the worst case can only happened at $$$n = 2^k+1$$$ and $$$n = 2^{k+1}$$$, where both only spent $$$2n-4$$$ queries. And thus, this problem is solved using $$$\leq 2n$$$ queries.

Edit: I found this during the round testing and suggested to add it as a hard version of the problem, but they refused lmao.

Edit 2: If anything seems wrong in this message, please let me know :3

Edit 3: Credit to MCYang for the concise upper bound for the step $$$3$$$ and some corrections to the comment ^w^

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

    the submission

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

    Interesting idea overall, though I think one of the steps needs some clarification.

    In the explanation of step 3, when you mentioned that "$$$m$$$ is the number of active bits in the number $$$a$$$," $$$a$$$ actually comes out of nowhere. Does it mean a number we found at step 1? If so, why do you restrict the range of $$$a$$$ to $$$2^k\leq a<n$$$ (instead of $$$2^{k+1}-n\leq a<n$$$?) If not, what does $$$a$$$ refer to? You may want to describe what $$$a$$$ means more clearly.

    By the way, I have a more concise expression for the upper bound on number of queries on step 3.

    • If $$$n=2^{k+1}$$$, there will be at most $$$n-2$$$ queries.
    • Otherwise, there will be at most $$$n-2^k-1$$$ queries.

    This also explains why the worst case of your idea happens only when $$$n=2^k+1$$$ or $$$n=2^{k+1}$$$. (Also they both only spend $$$2n-4$$$ queries. This is a resubmission of your code except that I added runtime checks on the number of queries.)

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

https://codeforces.me/contest/1937/submission/249016789 Why is this giving tle at 10th test case?

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

    you did string assigning ans = temp $$$n$$$ times, which results in $$$O(n^2)$$$ complexity since string assigning is $$$O(n)$$$.

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

      Thanks! Is there any way i can optimise that approach?

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

        hint: notice that everytime, you only need to change one character inside the temp string, which means that when you need to change ans, you can do so by only changing one character inside of it

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

          :_), yea that makes sense. Thanks edit- still tle.

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

            else if(temp==ans) x++; is $$$O(n)$$$ since temp and ans are strings of length $$$O(n)$$$. This makes your code $$$O(n^2)$$$.

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

can anyone help me in this DIV2 -B

int n;

void solve(){

cin>>n;

string u, d; cin>>u>>d;

string s = u[0] + d;

string c=s;

int cnt=0;

for(int i=0;i<n;i++){

    s[i] = u[i];

    s[i+1] = d[i];

    if(s==c) cnt++;

    if(s<c) c=s, cnt=1;

}

cout<<c<<'\n'<<cnt<<'\n';

}

It is giving TLE -- but it is running in O(n) time

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

    May be the way you are checking s<c is taking O(n) time itself for each iteration

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

    I uploaded to Youtube a video in English explaining the solution of Div2-B

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

248985883

Can you help me? I am getting TLE. But my code is supposed to be in NlogN time only.

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

can anyone prove/justify Step 3 of editorial of D2C/D1A.why minimum need to be choosen.

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

    Cause the minimum is the one that does not have any bit in common with n-1, therefore maximazing the XOR.

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

I will share my solution for D1F.

First, binary search for $$$r$$$. The maximum circle has radius at least $$$r$$$ is equivalent to the $$$n$$$ circles with their radius decreased by $$$r$$$ have a non-empty intersection. If the intersection is non-empty, the intersection is convex.

Then do binary search for $$$y$$$. For $$$y=k$$$, one of the following is true:

  1. The line $$$y=k$$$ crosses through the intersection.
  2. The intersection is entirely in the $$$y>k$$$ half-plane.
  3. The intersection is entirely in the $$$y<k$$$ half-plane.

The first case is true if and only if

  1. The line $$$y=k$$$ crosses through all $$$n$$$ circles with their radius decreased by $$$r$$$.
  2. Suppose that the intersection of the line $$$y=k$$$ and the $$$i$$$-th circle is $$$(x,k)$$$ for all $$$l_i\leq x\leq r_i$$$. Then $$$\max_{i=1}^n l_i \leq \min_{i=1}^n r_i$$$.

Otherwise, there exists two circles $$$i,j$$$ such that $$$r_i<l_j$$$. The second case is true if and only if the intersection of the circles $$$i,j$$$ is entirely in the $$$y>k$$$ half-plane. There are many ways to check this.

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

Problem D can be done in $$$O(\log V\log\log V)$$$ per query of type 1 and $$$O(\log n)$$$ per query of type 2. The idea is to maintain all minimal good intervals $$$[l,r]$$$ (good intervals such that neither $$$[l+1,r]$$$ and $$$[l,r-1]$$$ are good) in sorted order using a BBST.

  • Type 2: Query min of a range in the BBST.
  • Type 1: Erase all $$$O(\log V)$$$ intervals in the BBST crossing $$$i$$$, then find all $$$O(\log V)$$$ intervals crossing $$$i$$$, then insert them back into the BBST. To find the intervals quickly we can maintain a separate vEB tree for each bit, allowing us to find the closest index $$$j$$$ greater or less than $$$i$$$ such that $$$b_j$$$ has a certain bit set.
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My Screencast for A and B problems: https://youtube.com/live/IU6Zqy5LGB4 This was private during the contest. Hope it helps someone.

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

    Bro no one is interested in seeing you struggling in problem A, so stop spamming the commemt section under every blog post

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

      I apologize, bro. I understand that my struggle with problem A, taking 3 minutes to solve (which may seem slow to you for someone "green"), might not be of interest to everyone. I acknowledge that I need to improve, and I'll work harder in the future.

      Regarding your statement that 'no one wants to watch,' I must respectfully disagree. I get over 30 (sometimes 100) watch hours on these videos in total, indicating that there is indeed interest. However, if my content doesn't resonate with you, you're welcome to unsubscribe and find content that better suits your preferences. Criticizing someone's honest efforts without constructive feedback isn't fair or productive.

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

        why are you specifically mentinoning "green". making fun of someone's rating without constructive feedback isn't fair or productive.

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

Round 930 div 2 problem C: code -> 249045846

Idleness limit exceeded on test 1 why? what's wrong? Please identify the mistake and let me know

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

    If you read interactive problems guidelines, you shouldn't do this #define endl "\n"

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

Problem D1B Pinball can be done in O(n) time: No need to binary search for the proper endings, as they are changing monotonically as you go from one query index i to i+1. 249059259

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

In the editorial for D2B , I think the initial value of 'max_down' should be (n-1). correct me if I am wrong

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

The influence of clash of D1B is quite big. it appears just following the beginning problem and people soon finds the clash, as you can see a originally *2400 problem(733E) passed by a lot of people. my advise is just make this round unrated if possible.

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

Good idea hh

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

I am not able to understand problem D ??? Div2

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

In F I solved the 3-circle case like this: I applied an inversion at one of the intersection points of 2 circles and found a circle inscribed between an arc and 2 segments with Sawayama theorem. Unfortunately after inversion the picture becomes heavily dependant on the point configuration, and I think my code that passed doesn't quite work (though I don't understand how), as it sometimes finds no circles between the given 3 at all

Edit: Also now it works insanely fast without hypotl calls

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

How to get pupil rank?

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

For the problem D, at the end of the editorial, they said : It is not difficult to observe that we can use prefix sum to store the sum of indices, and then quickly calculate the time when the pinball moves.

And to calculate the pinball moves the precalculate two arrays: IDr[i]=IDr[i-1]+i*(s[i-1]=='>'); IDl[i]=IDl[i-1]+i*(s[i-1]=='<');

and for case s[i-1] == '<' && countright(1,p) > countleft(p+1,n), the ball should go at the end, from leftk to boundary. But the moves was got in such a way:

2*((IDl[n]-IDl[i])-(IDr[i]-IDr[k-1]))+i+(n+1) with k the last movemement before go out.

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

In D1C，why add Y node？ edge x -> Pokémon node with a value of 0？

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

Can someone please help me in finding the mistake in the following code? Here , I have first calculated the index , which means that the substring b starting from index to n-1 is lexicographically smaller or equal to the substring a from index+1 to n.

Submission

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

Can someone pls review my code and tell me in which test code my code is getting error :) https://codeforces.me/contest/1937/submission/249344544

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

Can someone please explain how do we derive the formula for Problem D? I'm so confused!

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

Problem c sucks!!

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

What is line segment tree mentioned in div 1 D?

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

Did the tutorial of Div.1 E missed some factorial notations in the final transform formulas of $$$f$$$?

For example $$$f_i = -\sum_{j=0}^{last_i} f_j \cdot A_{i-j-1}^{P_i-j-1} = -(P_i-i)^{-1} \sum_{j=0}^{last_i} f_j \cdot (P_i-j-1)$$$, I think it should be $$$f_i = -\sum_{j=0}^{last_i} f_j \cdot A_{i-j-1}^{P_i-j-1} = -((P_i-i) {\color{red}!} )^{-1} \sum_{j=0}^{last_i} f_j \cdot (P_i-j-1) {\color{red}!}$$$.

And if this is correct, how can we do D&C + FFT with $$$(P_i-j-1)!$$$ in the formula?

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

    Thx,typo fixed.

    You can read https://mirror.codeforces.com/blog/entry/18842 for D&C + FFT tricks(in DIV1E).

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

    I had the same question as you, because the editorial made me think that the formula $$$f(i) = h(i)\sum f(j)g(p_i-j)$$$ can be written in the form $$$f(i) = h(i)\sum f(j)g(i-j)$$$ somehow. This is not true. Instead, when performing the convolution step, you compute $$$F(i) = \sum f(j)g(i-j)$$$ and then take $$$f(i) = h(i)F(p_i)$$$. Note that unlike the example 553E - Kyoya and Train that wuhudsm referenced, in the convolution step you may be performing a convolution of vectors of very different sizes. Due to $$$p$$$ being an increasing function from $$$0$$$ to $$$n$$$, the time complexity works out correctly in the end (in my opinion, the editorial would be improved if it explained this part).

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

Thanks wuhudsm for the great tutorial for problem div2 E (Pokemon Arena).

However, I think there's a typo in the first line of the tutorial. It makes more sense to be like that, Then the problem is essentially finding the shortest path from $$$1$$$ to $$$n$$$ and not from $$$n$$$ to $$$1$$$ as written in the tutorial.

Please correct me if I am wrong.

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

D1E, am I right that last_i = max(j<i)(P_j!=P_i)? Or j can be greater than i?

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

Div1D can support range update and only use one segment tree if we design our node to have logV merge. See 251321474 See node in struct MinGood, it will have a bit more memory O(NlogN) (logN per node) but that still fits.

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

Solution to Div 2 problem E reminds me of the graph construction we do for proving NP-Completeness of certain problems. Can someone suggest problems to get good at thinking like this?

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

Another solution for Div1C with segment tree.

Let's say we want to process a pokemon $$$i$$$. Where could the path possibly come from? Let's assume the path comes from trait $$$j$$$, then either the path comes from a pokemon with more strength (1) or a pokemon with less or same strength (2).

If it comes from a pokemon with more strength (1) (let's say pokemon $$$p$$$), then $$$dist_i = dist_p + a_{p,j} - a_{i,j} + c_i$$$.

If it comes from a pokemon with less or same strength (2), then $$$dist_i = dist_p + c_i$$$, since we don't have to raise the stats of pokemon $$$i$$$.

But, what if the shortest path to $$$p$$$ also used trait $$$j$$$? Let's call $$$q$$$ the parent of $$$p$$$. Then our path looks like $$$q$$$ -> $$$p$$$ -> $$$i$$$. However, we could take the path $$$q$$$ -> $$$i$$$ and get a lower cost. So this case never happens. More generally, we will never use the same trait twice in a row.

But how do we consider all possible $$$p$$$ at once? To cover case 1, we want the lowest value of $$$dist_p + a_{p,j}$$$ across all $$$p$$$ where $$$a_{p,j} > a_{i,j}$$$. If we sort $$$a$$$ so that all $$$p$$$ form a contiguous segment, this turns into a range min query. To cover case 2, we take the lowest value of $$$dist_p$$$ across all $$$p$$$ where $$$a_{p,j} \le a_{i,j}$$$, also a range min query.

So we can store two segment trees for each $$$j$$$, each with size $$$O(n)$$$, to quickly determine the shortest path assuming all nodes with lower cost are already processed. All that is left is to determine processing order, and that can be done with priority queue/Dijkstra. The time complexity is $$$O(nm \log(nm))$$$.

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

did you write div1e tutorial code so that it couldn't be read by normal people

→ Reply