Блог пользователя awoo

Автор awoo, история, 5 лет назад, По-русски

1555A - PizzaForces

Идея: BledDest

Разбор
Решение (Neon)

1555B - Two Tables

Идея: adedalic

Разбор
Решение (adedalic)

1555C - Coin Rows

Идея: BledDest

Разбор
Решение (awoo)

1555D - Say No to Palindromes

Идея: BledDest

Разбор
Решение (Neon)

1555E - Boring Segments

Идея: vovuh, adedalic

Разбор
Решение (awoo)

1555F - Good Graph

Идея: adedalic

Разбор
Решение (adedalic)
  • Проголосовать: нравится
  • +114
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

good round

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

nice round

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problems A,B,C could have been presented in a different order.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

thank you for your dedication for this round

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

problem E is so good, but I couldn't solve it during the contest :'(

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

These are some incredible problems!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Quality problems, quality constest. Also i think it perfectly encapsulates what a educational round should be: teaching cool techniques through problem-solving.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Can someone pls explain how to implement the segment tree in problem E

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Can anybody explain how this range based segment tree works, editorial doesn't talks about it

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

For the problem C, if the map is N*M, how to solve it? Should I use twice DP?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +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://mirror.codeforces.com/blog/entry/93407

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится 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.

»
5 лет назад, скрыть # |
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 :)

»
5 лет назад, скрыть # |
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];
	}
}