### awoo's blog

By awoo, history, 14 months ago, translation,

1555A - PizzaForces

Idea: BledDest

Tutorial
Solution (Neon)

1555B - Two Tables

Tutorial

1555C - Coin Rows

Idea: BledDest

Tutorial
Solution (awoo)

1555D - Say No to Palindromes

Idea: BledDest

Tutorial
Solution (Neon)

1555E - Boring Segments

Tutorial
Solution (awoo)

1555F - Good Graph

Tutorial

• +114

 » 14 months ago, # |   0 good round
 » 14 months ago, # |   0 nice round
 » 14 months ago, # |   0 Problems A,B,C could have been presented in a different order.
 » 14 months ago, # |   0 thank you for your dedication for this round
 » 14 months ago, # |   0 Finally the editorial is out.
 » 14 months ago, # |   +10 problem E is so good, but I couldn't solve it during the contest :'(
•  » » 14 months ago, # ^ |   +44 How it is good?
 » 14 months ago, # |   +3 These are some incredible problems!
 » 14 months ago, # |   +6 Quality problems, quality constest. Also i think it perfectly encapsulates what a educational round should be: teaching cool techniques through problem-solving.
 » 14 months ago, # |   +5 Can someone pls explain how to implement the segment tree in problem E
•  » » 14 months ago, # ^ |   +15
•  » » 14 months ago, # ^ |   0 First, sort the Segments by $w_i$Then, use two-pointers + Segment tree. For each $i$, you can add $[l_i,r_i]$ by 1, and in the segment tree, record the minimal value.for the second pointer, if the minimal value of $[l_i,r_i]$ is bigger than 2, then it means it is no longer useful, so you can add $[l_i,r_i]$ by $-1$, and the position of the second pointer ++the answer is the minimal value of $w_i-w_j$ For each $i$.Maybe my English is not good, if you want my code/still don't understand, you can ask me in codeforces.
•  » » » 14 months ago, # ^ |   0 You could also $update(L, R)$ by setting $wi$ at every index, do range minimum query, and get rid of the $(+1, -1)$ thing.
 » 14 months ago, # |   +5 Can anybody explain how this range based segment tree works, editorial doesn't talks about it
•  » » 14 months ago, # ^ |   +10
•  » » » 14 months ago, # ^ |   +3 Thanks helpful very
 » 14 months ago, # |   +1 For the problem C, if the map is N*M, how to solve it? Should I use twice DP?
•  » » 14 months ago, # ^ |   0 it can be solved without dp brute force only
 » 14 months ago, # |   +1 Surprisingly this time Question A stumped me during the contest. It really took some time to understand and solve it, so if anyone would like a more detailed explanation with a slightly different approach feel free to visit my blog on it.https://codeforces.com/blog/entry/93407
 » 14 months ago, # |   0 It took me almost 2 hours to come up with an approach for problem A. And my logic is extremely weird. see: 124335979 ;)
•  » » 14 months ago, # ^ |   0 brute force
•  » » » 14 months ago, # ^ |   0 Yes... I'm so dumb
•  » » » » 14 months ago, # ^ |   0 it took me 40 min to solve that prob. ig ,am dumb too. cheers
 » 14 months ago, # |   0 Can't the probelm A be solved using a DP-like approach? I tried but my code was failing on larger values like 99999 and greater.
•  » » 14 months ago, # ^ |   +8 problem A requires O(1) solution
 » 14 months ago, # |   0 They are very good problems， all of div2 ' s contests should like this.
 » 14 months ago, # |   0 "It induces at least one "all-tree-edge" cycle since u and v are already connected. It can't induce more than one "all-tree-edge" cycle, since it contradicts with tree edge definition, and if it induces a cycle with some other cycle edge, then we can replace that cycle edge with its own tree-edge path: our cycle will become "all-tree-edge" cycle, but it will use already used tree edges. In other words, it's enough to consider only one "all-tree-edge" cycle induced by any cycle edge."Such Verbosity makes editorials rather convoluted.
•  » » 11 months ago, # ^ |   0 Thanks
 » 14 months ago, # |   0 Problem B is so interesting! It seems to need Pythagorean theorem, but we can prove that the best strategy only moves vertically or horizontally.
 » 14 months ago, # | ← Rev. 2 →   0 Could someone tell me how the BIT part of the last problem works in code? It is not something like ‘lowbit’ that I am familiar with. Just providing me a link should be ok :)
•  » » 10 months ago, # ^ |   0 BIT stands for Binary Indexed Tree also known as Fenwick Tree. You can find more on cp-algorithms
 » 14 months ago, # |   0 for problem C, why my i'm getting WA? i've used prefix, suffix sums.firstly i let ALICE to take max point path, then let bob to choose any path which obviously will have less point than alice's path.my submission
•  » » 13 months ago, # ^ |   0 No Alice will not take the maximum point path. She will take the path that minimise the bob's score. See test case 1 Alice can achieve 12 points(max) but then bob will take 8 points which is obviously not minimum and Alice wants to minimise his score, so she will chose the path that forces bob to choose minimum score(7).
•  » » » 13 months ago, # ^ |   0 thanks,i got u!
 » 14 months ago, # | ← Rev. 2 →   0 In the solution of F, when add 1 to all the edge on the path, the function addOnPath just add the all the edges one by one. But isn't it O(n)? UPD: My bad, I didn't see that every edge will be at most delete once. void addOnPath(int v, int l) { while (v != l) { inc(tin[v], 1); inc(tout[v], -1); v = up[0][v]; } } 
 » 13 months ago, # |   0 how to do d using dp?
 » 13 months ago, # |   0 I really appreciate the effort put into the explanations.
 » 9 months ago, # |   0 In problem B, the editorial mentions to consider to move the second table to the left. How does this make sense when our room is bounded by 0 on the x — axis and the statement guarantees, that the lower left corner of our first table starts at (0, 0)?