Codeforces Round 930 (Div. 1, Div. 2) Editorial

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

D2A — Shuffle Party

Idea : chromate00

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

D2B — Binary Path

Idea : wuhudsm

D1A — Bitwise Operation Wizard

Idea : wuhudsm

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.

D1C — Pokémon Arena

Idea : wuhudsm

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

D1D — Bitwise Paradox

Idea : Psychotic_D, MagicalFlower

D1E — Yet Yet Another Permutation Problem

Idea : wuhudsm

D1F — Grand Finale: Circles

Idea : chromate00

UPD: The TL was a bit too loose, and unintended solutions with complexity passed during the round. For the sake of the problem itself, I suggest that you try to solve assuming a second time limit.

• 2 weeks ago, # ^ | ← Rev. 2 →   +16 ++ fast system testing

  • 2 weeks ago, # ^ | It seems like it's forzen right now...

    • 2 weeks ago, # ^ | Why it,s frozen? Do you have any idea ?

• 13 days ago, # ^ | 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

  • 13 days ago, # ^ | 哥们，string 比较大小时间复杂度很高，每次比较大小都是O（n），因此整个时间复杂度是O(t*n^2), so ， This code may exceed the time limit

    • 13 days ago, # ^ | yeah. I got the same problem, so I had to switch the solution entirely. Luckily, I was able to solve it.

  • 13 days ago, # ^ | 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.

• 2 weeks ago, # ^ | if we don't mention um_nik's editorial

  • 2 weeks ago, # ^ | Haven't tried his rounds yet

    • 2 weeks ago, # ^ | ← Rev. 2 →   0 It was this contest that he accidentally published his screencast 40 minutes before the end of the contest.

• 2 weeks ago, # ^ | 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 I was referring to was the nested golden section search where the is simply from calling the objective function. Do note though, that we do have a tester solution with complexity that passes in ~800ms.

  • 13 days ago, # ^ | hmm I just submitted and it's faster than everyone else's solutions ...

    • 13 days ago, # ^ | I believe it is one of the we intended to allow. Most of the I meant to block were the ones that do ternary search on both and , to maximize . In the meantime, a tester's solution using binary search on with a clever check function passes in about 800ms.

      • 13 days ago, # ^ | 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 249108458 249116485 249116654

        • 13 days ago, # ^ | As far as I believe, the issue is in the precision of the type itself. It can be fixed by implementing a class for , 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.

• 2 weeks ago, # ^ | No, it's too slow.

  • 13 days ago, # ^ | 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?

    • 13 days ago, # ^ | 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.

• 13 days ago, # ^ | Can you please share the approach , thanks !

• 2 weeks ago, # ^ | ← Rev. 2 →   +2 I am not sure but I think because the problem D1B — Pinball is conflicting

• 2 weeks ago, # ^ | Issue from the server side.

• 2 weeks ago, # ^ | ← Rev. 2 →   +2 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.

• 2 weeks ago, # ^ | ← Rev. 2 →   0 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

• 2 weeks ago, # ^ | ← Rev. 3 →   0 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.

  • 2 weeks ago, # ^ | But isnt deleting the character an O(1) operation?

    • 2 weeks ago, # ^ | ← Rev. 2 →   0 Nope, deleting character from a string is O(n)

• 2 weeks ago, # ^ | Why do we try step 3 in Div2 C? Do we need to find the smallest one?

  • 2 weeks ago, # ^ | When you ask a question it uses bitwize or, but for answer you need bitwize xor

  • 2 weeks ago, # ^ | ← Rev. 2 →   0 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.

    • 2 weeks ago, # ^ | 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.com/contest/1937/submission/248971409 Please let me know the reason.

• 2 weeks ago, # ^ | If you go right, you always have the chance to go down.There by you can have minimum among those both

  • 2 weeks ago, # ^ | ← Rev. 2 →   -12 Thank you! I thought it won't always be optimal and therefore tried to solve it by dp

• 13 days ago, # ^ | Because you have "ios_base::sync_with_stdio(false);" in your code so fflush doesn't affect cout.

  • 13 days ago, # ^ | Thank you for replying, I didnt know that.

• 2 weeks ago, # ^ | 3d dp is too much to understand. I better stay away from it.

• 2 weeks ago, # ^ | also possible with 2d dp code

  • 13 days ago, # ^ | 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

• 2 weeks ago, # ^ | ← Rev. 2 →   0 In your submission with the DP-array passed as reference you accidentally create an n*n array instead of 2*n. :/

  • 2 weeks ago, # ^ | I'll go slap myself a couple hundred times. Thanks a lot for answering.

• 2 weeks ago, # ^ | 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.

• 2 weeks ago, # ^ | 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

  • 2 weeks ago, # ^ | I made the blocks a bit bigger so my solution would take less memory, but my solution is still very tight on memory.

• 12 days ago, # ^ | Spoiler, it does work: (used kactl hashing) 249355708

• 13 days ago, # ^ | Interesting idea overall, though I think one of the steps needs some clarification. In the explanation of step 3, when you mentioned that " is the number of active bits in the number ," actually comes out of nowhere. Does it mean a number we found at step 1? If so, why do you restrict the range of to (instead of ?) If not, what does refer to? You may want to describe what means more clearly. By the way, I have a more concise expression for the upper bound on number of queries on step 3. If , there will be at most queries. Otherwise, there will be at most queries. This also explains why the worst case of your idea happens only when or . (Also they both only spend queries. This is a resubmission of your code except that I added runtime checks on the number of queries.)

  • 13 days ago, # ^ | thanks man, will fix it :3

• 13 days ago, # ^ | you did string assigning ans = temp times, which results in complexity since string assigning is .

  • 13 days ago, # ^ | Thanks! Is there any way i can optimise that approach?

    • 13 days ago, # ^ | 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

      • 13 days ago, # ^ | ← Rev. 2 →   0 :_), yea that makes sense. Thanks edit- still tle.

        • 13 days ago, # ^ | else if(temp==ans) x++; is since temp and ans are strings of length . This makes your code .

          • 13 days ago, # ^ | Fixed that, got AC. Thanks!

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';

• 13 days ago, # ^ | May be the way you are checking s<c is taking O(n) time itself for each iteration

• 13 days ago, # ^ | I uploaded to Youtube a video in English explaining the solution of Div2-B

• 13 days ago, # ^ | Cause the minimum is the one that does not have any bit in common with n-1, therefore maximazing the XOR.

• 13 days ago, # ^ | Bro no one is interested in seeing you struggling in problem A, so stop spamming the commemt section under every blog post

  • 13 days ago, # ^ | 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.

    • 13 days ago, # ^ | why are you specifically mentinoning "green". making fun of someone's rating without constructive feedback isn't fair or productive.

      • 12 days ago, # ^ | I was talking about me... i am green so it will take time to solve.

        • 12 days ago, # ^ | oh, I thought you were teasing me. Sorry

• 13 days ago, # ^ | If you read interactive problems guidelines, you shouldn't do this #define endl "\n"

• 62 minutes ago, # ^ | ← Rev. 2 →   0 Thx,typo fixed. You can read https://mirror.codeforces.com/blog/entry/18842 for D&C + FFT tricks(in DIV1E).