schrodingerstom's blog

Codeforces Round 1097 (Div. 1, Div2, Based on Zhili Cup 2026) Tutorial
By schrodingerstom, 3 weeks ago, In English

2224A - Zhily and Array Operating

Tutorial
Implementation

2224B - Zhily and Mex and Max

Tutorial
Implementation

2224C - Zhily and Bracket Swapping

Tutorial
Implementation

2224D - Zhily and Barknights

Tutorial
Implementation

2223C - Zhily and Signpost

Tutorial
Implementation

2223D - Zhily and Cycle

Tutorial
Implementation

2223E - Zhily and Permutation

Tutorial
Implementation

2223F - Zhily and Colorful Strings

Tutorial
Implementation
  • Vote: I like it
  • +26
  • Vote: I do not like it

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

Sorry, the implementation might be unauthorized, we're solving it...

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

https://mirror.codeforces.com/contest/2224/submission/373788886

The java implementation for 2224D solution 2 got TLE with Fenwick tree, but it passed with merge sort. Wondering why...

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

The solution for Problem $$$\textbf{Div2}$$$ $$$C$$$ is not clear!!

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

    It may be more intuitive to apply the greedy algorithm to verify whether the value of the number of left parentheses minus the number of right parentheses in the two strings is valid.373672904.Hope it will help.

    → Reply
    • »
      »
      »
      10 days ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Hi, thanks for the implementation. It was really easy to understand. I dont understand, why does this greedy work? If you could just tell me the intuition behind it, that would be a great help. Thanks

      → Reply
      • »
        »
        »
        »
        10 days ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        Because when the number of right brackets in a prefix exceeds that of left brackets (the value becomes negative), the bracket string is definitely invalid. Therefore, we traverse each position i from left to right. If the brackets at a certain position differ, we greedily place the left bracket at the position with a smaller value (the smaller difference between the count of left and right brackets). This approach is always optimal, as we keep raising the minimum value to prevent right brackets from outnumbering left ones. If this cannot be achieved, the string is bound to be invalid, just as I mentioned earlier.And if everytime the value is valid,just check if it is 0 in the end.Hope it help!

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

    We are changing a new version of it. Hope it will help.

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

I created video editorial for D. Zhily and Barknights

I created video editorial for E. Zhily and Signpost.

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

can someone pls point out the mistake in this? (the function full of comments is taken from gfg)

→ Reply
»
3 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it
Specifically, we have Mv=lcm(Mu,du). Then m≡Ru (mod Mu) implies m≡kMu+Ru (mod Mv), k∈[0,gcd(Mu,du)−1]. By enumerating all k and computing the corresponding r, we can obtain the congruence equation for su,r. If some r is not obtained, then the congruence equation corresponding to su,r has no solution.

Should not $$$k$$$ range over $$$[0, \frac{d_u}{\gcd(M_u, d_u)} - 1] $$$ ?

EDIT: I got it. $$$k \in [0, \frac{d_u}{\gcd(M_u, d_u)} - 1]$$$ if the modulus is $$$d_u$$$

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it +14 Vote: I do not like it

    My mistake. We will correct it immediately :(

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

      System of equations is exactly a statement of Chinese Remainder Theorem. Can't CRT be used here to solve the equations instead of iterating k?

      → Reply
      • »
        »
        »
        »
        3 weeks ago, hide # ^ |
         
        Vote: I like it +13 Vote: I do not like it

        Of course you can. But iterating k is easier and faster I think.

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

I'm new here. Can somebody tell me why the source in the implementation shows "N/A"? Is my viewing permission sufficient?

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

can someone please help me figure out why my submission resulted in rte for preblem C? i used a binary searching like technique on centroid

https://ideone.com/OYXng2

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it -66 Vote: I do not like it

slowEditorialForces

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

Is problem (div2)D solvable in Python without getting TLE?

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

Solution of problem B can be implemented easily by using mathematics if we observe pattern in the optimal answer when $$$max(a_1, a_2, ..., a_n) \geq mex(a_1, a_2, ..., a_n)$$$ and when it's not.

Check out this submission

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

    I tried to simplify it, become $$$\text{ans} = n \times (m + k) - \frac{k(k - 1)}{2} - \min(m, k)$$$

    ans = n * (m + k) — k * (k — 1) / 2 — min(m, k); //m=max,k=mex

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

The fastest task analysis this year!!!

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

Anyone else tried solving 2E/1C using binary search?

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

Hi, I am not able to see the code in the submission given under implementation. Does it have anything to do with this being my first contest? How can I fix this? Appreciate anyone's help.

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

Also, can someone tell me where I went wrong in my solution for Problem B, Div 2?

Edit: Got it, LL conversion error.

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

I think Div2 problem C is much simpler than Div2 B.

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

weird contest

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

C is easier than B...

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

For problem div2 E/div1 C, i suggest an alternative solution using binary search on centroid decomposition tree. Though i will not go much into explaining it, the way it works is check whether a node u in the centroid tree is reachable from 1, if it is then the answer must lies inside the subtree of u, then compute the next normally. If not then it can be seen that the answer is not inside the subtree of u, so we find go to the parent of the node u in the original tree and its centroid, note that we always move to a centroid with higher depths in the centroid decomposition tree.

I wonder if this technique caa be extended even more though, as centroid decomposition is almost like DNC on tree, so maybe we can extend it even further?

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

    Edit: I forgot to put the code xd. Here is the code for problem E: https://ideone.com/YacS7r

    Also, can someone dig more into this topic? I would love to personally do it but i currently have to work on other projects so i can not spend much time on this.

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

in question A there is written we have to find number of positive number in array, is 0 not a positive number??

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

any help, my submission submission got different wrong answers for different c++ versions , i.e : in c++23 it got WA on test2 case 9 , in c++17 got WA test2 case 6 , in c++20 got WA test2 case 11, what's the issue despite i submit the SAME code && the "failed" testcases as codeforces saif got the correct output Locally but different output on codeforces

→ Reply
»
12 days ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Can anybody explain whats the proof of greedy in div2 C?Like why is it that balancing the difference in A & B is optimal?What if A has more open brackets so we can have its diff less than B and give more open brackets to B before while ensuring that no one has diff<0 at any point?I have the intution on why greedy is working but i just cant prove it

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

i had a different solution to 2224C (zhily and bracket swapping). the basic idea is to alternate between setting $$$a_i$$$ as '(' and $$$b_i$$$ as '(' at all entries $$$i$$$ such that $$$a_i \neq b_i$$$. then, just check if the resultant strings are valid. it is easy to prove this is correct by noticing the max discrepancy in open and closed parentheses this creates is one.

for an example, if indices 4, 6, 9, and 10 differ between strings $$$a$$$ and $$$b$$$, set $$$a_4$$$ as '(', $$$a_6$$$ as ')', $$$a_9$$$ as '(' and $$$a_10$$$ as ')'. then, check if $$$a$$$ and $$$b$$$ are valid.

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

    weird solution honestly, it seems impossible to proof the choice of starting with ( , ) not with ) , ( for setting x[i] and y[i]. The same thing for swapping all different pairs , how can you proof that swaping all pairs works ?

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

in $$$D$$$ let $$$d = a * b$$$ then answer is just $$$\frac{inv(d) - n * (inv(a) + inv(b))}{n (n - 1)}$$$ where $$$inv$$$ is the number of inversions.

$$$\; \; a * b = [a_0 \times b_0, ..., a_0 \times b_{n- 1}, a_1 \times b_0, ... ]$$$

→ Reply