### awoo's blog

By awoo, history, 2 years 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

| Write comment?
 » 2 years ago, # |   0 good round
 » 2 years ago, # |   0 nice round
 » 2 years ago, # |   0 Problems A,B,C could have been presented in a different order.
 » 2 years ago, # |   0 thank you for your dedication for this round
 » 2 years ago, # |   +10 problem E is so good, but I couldn't solve it during the contest :'(
•  » » 2 years ago, # ^ |   +44 How it is good?
 » 2 years ago, # |   +3 These are some incredible problems!
 » 2 years ago, # |   +6 Quality problems, quality constest. Also i think it perfectly encapsulates what a educational round should be: teaching cool techniques through problem-solving.
 » 2 years ago, # |   +5 Can someone pls explain how to implement the segment tree in problem E
•  » » 2 years ago, # ^ |   +15
•  » » 2 years 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.
•  » » » 2 years 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.
 » 2 years ago, # |   +5 Can anybody explain how this range based segment tree works, editorial doesn't talks about it
•  » » 2 years ago, # ^ |   +10
•  » » » 2 years ago, # ^ |   +3 Thanks helpful very
 » 2 years ago, # |   +1 For the problem C, if the map is N*M, how to solve it? Should I use twice DP?
 » 2 years 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
 » 2 years 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.
•  » » 2 years ago, # ^ |   +8 problem A requires O(1) solution
 » 2 years 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.
 » 2 years 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.
 » 2 years 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 :)
•  » » 21 month(s) ago, # ^ |   0 BIT stands for Binary Indexed Tree also known as Fenwick Tree. You can find more on cp-algorithms
 » 2 years 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]; } } 
 » 11 months ago, # |   0 In problem A what would be the answer of test case of n=777 According to tutorial 1945 min is answer but what would be the combination of pizzas to get this answer because 1945 is not multiple of 15,20,25,35,45,40 so how could this answer be feasible.
 » 9 months ago, # |   0 I'm new to CP and was utterly demolished by the first problem (PizzaForces). I spent about 4 hours on the problem, with 20 submissions, and 140+ lines of code before I finally caved in and looked at the solution. It's kind of embarrassing how easy the problem really was when you took a mathematical approach first before jumping straight to coding. So much time and energy were spent when all it took was about 10 lines haha. Oh well, I guess that's how you learn :)