awoo's blog

Educational Codeforces Round 188 Editorial
By awoo, history, 6 weeks ago, translation, In English

2204A - Passing the Ball

Idea: BledDest

Tutorial
Solution (BledDest)

2204B - Right Maximum

Idea: fcspartakm

Tutorial
Solution (BledDest)

2204C - Spring

Idea: BledDest

Tutorial
Solution (BledDest)

2204D - Alternating Path

Idea: BledDest

Tutorial
Solution (awoo)

2204E - Sum of Digits (and Again)

Idea: BledDest

Tutorial
Solution (BledDest)

2204F - Sum of Fractions

Idea: adedalic

Tutorial
Solution (adedalic)

2204G - Grid Path

Idea: Roms

Tutorial
Solution (Neon)
  • Vote: I like it
  • +48
  • Vote: I do not like it

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

I created video editorial for Problem F. Sum of Fractions. I also created a practice contest where you can submit easy version of problem F along with some practice problems on similar ideas.

I added hints for all the problems on CF Step

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

Thanks for this div3 contest. Also, the problem statement for problem D was terrible.

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

for G. 300 * 300 * 300 * 30 is approximately 8.1 * 10^8, which is well beyond 3 * 10^8 operations, why does author set tight limits for matrix expo with 2m + 1 size? m could well have been 100, and m^3logn would have passed without much issues.

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

    This problem tested matrix multiplication optimization tricks more unnecessarily or necessarily

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

pls help with my solution on F. im trying to calculate gains over the base sum for every k. love you

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

    heres my previous iteration of code. this doesnt even pass the first 20 tc the og comment is what jippity gave me after removing my template so you all could understand

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

    cnt can be as large as $$$O(n^2)$$$ (from $$$(i - L[i]) * (R[i] - i)$$$)

    So, val * cnt can overflow before the % MOD. Using $$$cnt \% MOD$$$ before multiplying keeps the product within range and preserves the result, since (val * cnt) % MOD == (val * (cnt % MOD)) % MOD.

    Your updated submission now passes TC20, but fails on TC25 (due to the same bug, but in a different place). Hope you can fix it.

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

Thanks for the contest I enjoyed these problems! D and E were my favorites. (solved A-E)

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

B is pretty simple: track a max variable, count how many times it increases -> answer. Stack version works too (push when >= top), size of stack at the end is it ;)

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

the tasks were easier than I thought

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

Statement for D could have been much better, but ok.

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

Share a more natural solution of G with an $$$(m+1)\times (m+1)$$$ transition matrix.

First, the constraint that $$$(1, 1)$$$ should be covered by segments is equivalent to that of $$$(n, m)$$$ by symmetry. Thus, let $$$dp_{i,l,r}$$$ denote the number of ways to choose segments for the first $$$i$$$ rows where the segment for the $$$i$$$-th row is exactly $$$[l, r]$$$, without considering the constraint of $$$(1,1)$$$. Easy to write out the transition:

$$$ dp_{i,l,r} = 1 + \sum_{[a, b] \cap [l, r] \neq \emptyset} dp_{i-1, a, b} $$$

Note that $$$[a, b] \cap [l, r] = \emptyset$$$ iff either $$$b \lt l$$$ or $$$r \lt a$$$. Let the prefix sum and the suffix sum as

$$$ pre_{i,k} = \sum_{r\leq k} dp_{i,l,r}, \quad suf_{i,k} = \sum_{l\geq k} dp_{i,l,r} $$$

Then

$$$ dp_{i,l,r} = 1 + pre_{i-1,m} - pre_{i-1,l-1} - suf_{i-1,r+1} $$$

Summing up $$$dp$$$ by the definitions of $$$pre$$$ and $$$suf$$$ above gives the transitions between $$$pre_i, suf_i$$$ and $$$pre_{i-1}, suf_{i-1}$$$. Flipping the grid horizontally gives the bijection between ways to choose segments of $$$pre_{i,k}$$$ and that of $$$suf_{i,m-k+1}$$$, showing that they are equal. Thus, only $$$m+1$$$ states ($$$pre$$$ and a constant $$$1$$$) should be maintained. The final answer is $$$pre_{n,m} - pre_{n,m-1}$$$.

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

I think G can be solved for $$$M\leq800$$$ . Not recommended. (It seems like the solution above doesn't work for small modulos or non-prime modulos, so if only matrix multiplication is allowed, then $$$M\leq 500$$$ is doable.)

Also, what is the exact reason for the fact that BM doesn't work? What's the time complexity of BM?

Edit: the fastest solutions uses the Reed-Sloane algorithm (BM's extension to non-prime modulos). I guess the time complexity is $$$O(n^3)$$$ or simmilar.

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +11 Vote: I do not like it
Optimizations to E solution
→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    I might argue that max suffix sum of digit is at most 70, not 71 because sum of digit = 999999 is not reachable from given problem constraint, so sum of digit 888889 is the worst case here with sum of suffix digit equal to 70: (8+8+8+8+8+9) + (4+9) + (1+3) + (4) = 70

    My submisson checking only 71 possiblities without any precompute: 367072645 (62 ms)

    And yes, in practice precompute is a bit slower than brute force in this case, I also has another submission that precompute all possible sum of digit too, and the result it's a bit slower (it uses >110 MB of memory): 367056743 (93 ms)

    Maybe because my language is pure C (without plus-plus) so my runtime is faster than yours even with the same algorithm x)

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

how to find rating of ques?

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

I'm trying to understand problem G. If we run the code from the solution for m = 2, we get the matrix:

0 2 1 0 2

0 0 0 1 1

0 1 1 1 2

0 0 0 0 1

But I can't figure out why [1:1] is 2 and not 4. From state j=0 f=1 (these are 10 and 11 ), there are transitions: 10: 10, 11 11 : 10, 11 At j = 0, f=1. What am I missing?

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

for Problem E ,there is a answer check for whitespace in the end of line.

ie '134 ' != '134' .. this caused me WA while practicing

I have rarely seen it on codeforces because my template always printed it, so I want to mention here

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

in the tutorial of G: "that is, if the segments in adjacent rows are $$$[l_1,r_1]$$$ and $$$[l_2,r_2]$$$, we can only transition between them in column $$$j=min(l_1,l_2)$$$"

shouldn't this be $$$j=max(l_1,l_2)$$$?

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

Hi! I've been trying to submit F on python lately and many times I faced TLE on test 25. I've tried to optimise it in different ways but still got TLE. From what I've gathered the only things that could possibly slow down my solution are sort and exponentiation modulo, but I'm more biased towards the second option. I'm a bit curious as why these things could possibly affect complexity so much?

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

For D, I think the problem should be phrased as “Call a vertex v beautiful if all not-necessarily-simple paths in original graph that start at v and that still exist after determining directions of each edge, are alternating in the resulting directed graph.” Because a path in original (undirected) graph could be a->b->a when there is only one edge (a,b). Then, no matter how you choose direction of (a,b), the path a->b->a will be missing an edge, and hence the path becomes invalid. But the problem doesn’t say how an invalid-after-direction path should affect the beauty of the vertices involved. I suppose one can figure out the intended meaning by studying examples, but still it confused me at first. Correct me if I’m missing something.

UPD: I understood the problem now and there is nothing wrong with the phrasing.

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

Hello,

I would like to clarify that I did not copy or share my solution with anyone during the contest.

For problem 2204D, I solved it by modeling the problem as a bipartite graph check. I used a standard BFS/DFS-based coloring approach, where each node is assigned one of two colors and adjacent nodes are checked for conflicts.

Since bipartite checking is a very common and standard technique, I believe it is possible for independently written solutions to look very similar in structure and implementation.

My solution was written independently during the contest, and I did not use any external sources or public code-sharing platforms.

Please let me know if any further clarification is required.

Thank you.

[submission:2204D]

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

i think d bad and e veyyyyy good it dont said the breautiful v must has outdegree i just think all vertices in the connected components in a bipartite graph are breautiful the problem statement feels overly contrived and disconnected from the core algorithm, which is frustrating but the problem itself is well-designed! :)

→ Reply