### awoo's blog

By awoo, history, 22 months ago, translation,

1476A - K-divisible Sum

Idea: vovuh

Tutorial

1476B - Inflation

Tutorial

1476C - Longest Simple Cycle

Tutorial

1476D - Journey

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (BledDest)

1476E - Pattern Matching

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1476F - Lanterns

Idea: BledDest

Tutorial
Solution (BledDest)

1476G - Minimum Difference

Idea: Neon

Tutorial
Solution (Neon)

• +143

| Write comment?
 » 22 months ago, # |   +42 Problem E was beautiful! Thanks :D
 » 22 months ago, # |   -9 Finally a contest with less ad-hoc!
 » 22 months ago, # |   +89 contest is good but statement of E was awful
 » 22 months ago, # |   +3 In problem C , How the value of the following test case will be 6? please explain.. input 3 2 4 2 -1 2 4 -1 2 1 output 6 
•  » » 22 months ago, # ^ |   +44 Excuse the use of Paint lol, but it looks something like this (the blue edges are the ones forming the cycle):
 » 22 months ago, # |   +6 I think Problem D is simpler to use the Disjoint-set. Am I right?
•  » » 22 months ago, # ^ |   +6 It can be done simply by moving from current city to Right to find the largest pattern of RL...RL or RL...RLR and similarly on left from current city to left as LR...LR or LR...LRL and length of both the patterns + 1 will be the max cities visited from current cityYou can see my solution : https://codeforces.com/contest/1476/submission/106090614
 » 22 months ago, # | ← Rev. 2 →   0 This was a very nice contest after a while. Kudos to the authors, each and every problem in the contest that I solved / up-solved taught me something new. Hope for more such rounds :)
•  » » 22 months ago, # ^ |   +5 definitely an alt :rofl:
 » 22 months ago, # | ← Rev. 2 →   +8 Can someone help me figure out the error of code for submission below? My Code Here is my code for problem F. It gets wrong answer on test 5, case 1259. However, I can't get that sample.
 » 22 months ago, # |   0 Can Anyone tell me how to solve question D recursively and doing memoization?
•  » » 22 months ago, # ^ |   0 Not by recursive dp, but Errichto explained the iterative dp approach in his yesterday's stream
•  » » » 22 months ago, # ^ |   0 No like I am asking like can we solve it that way(recursive dp) like I am stuck and unable to move forward in my approach.
•  » » » » 22 months ago, # ^ |   0 You can solve it by recursion just reverse the starting position
•  » » 15 months ago, # ^ |   0 check my solution using memoization https://codeforces.com/problemset/submission/1476/128826229
 » 22 months ago, # |   0 For B, can anyone explain why there's a k-1 added to 100ll * p[i] - k * pSum?
•  » » 22 months ago, # ^ |   +1 It is basically done to take ceil of the value.Let me make it more clear — Ceil(a/b) == (a+(b-1))/b You can check this by taking two cases - a = k*b. Both functions return k a = k*b + x (0
•  » » » 22 months ago, # ^ |   0 but in editorial he didn't mention the ceil thing i understand it from the code but i dont understand the purpose of it, if u can explain please
•  » » » » 22 months ago, # ^ |   0 It is mentioned in the editorial that -$x \ge \left\lceil \frac{100 \cdot p_j - k \cdot (p_0 + \dots + p_{j - 1})}{k} \right\rceil$Notice the bracket, that is for denoting ceil function.Now the next question is why do we even need that — because x is a non negative integer and right hand side acc. to maths will return a floating value (which may not be integer). Let's take an example — You know x is an integer and after solving RHS you get - $x \geq 1.2$So definitely you know you should pick next integer (ceil value) as answer i.e. x = 2.
 » 22 months ago, # |   +1 A constant optimization for 1476G - Minimum Difference -- observing that the upper bound of value $c$ always equals to the lower bound of $(c + 1)$, we can store only the lower bounds (but not both as in the model solution), You can see my submission 106048247 for the detail.
•  » » 22 months ago, # ^ |   +13 There is no need of segment trees for 1476F - Lanterns. We need only two operations: The one is to query $\max\{(j + p_j), \dots, (i + p_i)\}$ for increasing $i$. The other one is to find the minimum $j$ where $\mathrm{dp}[j] \geq i - p_i - 1$. The two operations can be supported by two standard (monotonic) stack and std::lower_bound. My submission 106219219.
 » 22 months ago, # |   +3 In E you can also find a match converting the string to integer. The number of possible strings is $27^k$, so every pattern can be indexed.