Editorial of Round #569

(Идея задачи Div2B — kirillbogatiy)

(Разрабатывал задачу Div2B — gop2024)

Tutorial is loading...

(Идея задачи Div1A — Mr.Hakimov)

(Разрабатывал задачу Div1A — Mr.Hakimov)

Tutorial is loading...

(Идея задачи Div1B — gop2024)

(Разрабатывал задачу Div1B — PeregudovSergey)

Tutorial is loading...

(Идея задачи Div1C — ----------)

(Разрабатывал задачу Div1C — ----------)

Tutorial is loading...

(Идея задачи Div1D — gop2024)

(Разрабатывали задачу Div1D — ---------- и gop2024)

Tutorial is loading...

Читайте этот комментарий от saketh про другое решение этой задачи.

(Идея задачи Div1E — gop2024)

(Разрабатывал задачу Div1E — TheWayISteppedOutTheCar)

Tutorial is loading...

Разбор задач Codeforces Round 569 (Div. 1)

Разбор задач Codeforces Round 569 (Div. 2)

+105

gop2024
5 лет назад
90

Комментарии (71)

Показать архивные | Написать комментарий?

agtxdy_orz

5 лет назад, # |

← Rev. 2 →

+10

For Div1 D can someone help me prove/disprove how is this strategy working:
For any node L to get minimum sum we choose two children u and v such that dp[u]-2*n*sz[u] and dp[v]-2*n*sz[v] are smallest among all the children?

My code: 55909246

→ Ответить

MAOoo_Love_Molly

5 лет назад, # ^ |

I'm not sure about your strategy. But I find that the complexity of your code can be reduced into O(n) by using bubble sort to obtain the minimum and second minimum value.

→ Ответить

Fly_37

5 лет назад, # ^ |

I support the question.

→ Ответить

dragonslayerintraining

5 лет назад, # ^ |

It looks like your code also fails on saketh's test case here.

Correct answer is 1019. Your code outputs 1018.

→ Ответить

https://ideone.com/kPEg0m

5 лет назад, # ^ |

Here's the input:

35 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 19 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35

→ Ответить

agtxdy_orz

5 лет назад, # ^ |

← Rev. 2 →

I just ran my code on this example. Its giving correct output- 1019
https://ideone.com/UAyyqj

→ Ответить

dragonslayerintraining

5 лет назад, # ^ |

+10

Interesting. I guess the order of input data matters. We need the degree three vertex to be the root.

Input I used

→ Ответить

bsbs

5 лет назад, # |

← Rev. 2 →

Thanks for the great editorial!

I have a question about Div1C editorial. In definition of x, isn't it supposed to be the maximum x (instead of minimal) that satisfies the mentioned condition?

If I'm wrong, can you please tell me why?

→ Ответить

EmilConst

5 лет назад, # ^ |

← Rev. 2 →

But money isn't a problem at all for Serge, so Serge is buying the most expensive dish if there is at least one remaining.

There is a typo in the editorial. Also if you check editorials source code for that problem, you will see that it finds maximal X.

→ Ответить

5 лет назад, # |

+53

In D, we only need to consider the two best dp values for each unique subtree size. With that observation, there's no need for CHT: we can just check all pairs quadratically and it will still be fast enough.

→ Ответить

msuwakow

5 лет назад, # ^ |

Sorry for my not understanding…… But doesn't it have a complexity of $$$O(n^2)$$$ when facing a graph that each vertex has an edge to the same vertex?

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

At each node, it’s quadratic in the number of distinct child subtree sizes. Your tree has a node with many children, but they have only one distinct subtree size.

→ Ответить

Antoine

5 лет назад, # ^ |

I had the same idea. This clearly takes O(n sqrt n) but I'm wondering if there's a tighter bound.

→ Ответить

5 лет назад, # ^ |

← Rev. 4 →

+18

I think it's way faster than that, like $$$n \log \log n$$$. Credit due to dinosaurs and danielfleischman.

Suppose $$$f(n)$$$ is an upper bound on work done on a tree with $$$n$$$ nodes. We need $$$f(n) \geq k^2 + \sum_i { a_i \cdot f(i) }$$$ for any $$$a_i$$$ where $$$\sum_i a_i \cdot i = n - 1$$$ and $$$a_i$$$ has $$$k$$$ non-zero elements.

Let's write $$$f(n)$$$ as $$$n \cdot g(n)$$$, and let's rewrite $$$\sum_i { a_i \cdot f(i) }$$$ as $$$\sum_{i < \sqrt{n}} { a_i \cdot i \cdot g(i) } + \sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(i) }$$$.

The first sum is at most $$$\sum_{i < \sqrt{n}} { a_i \cdot i \cdot g(\sqrt{n}) }$$$ which is at most $$$n \cdot g(\sqrt{n})$$$. The second sum is at most $$$\sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(n) }$$$ which is at most $$$\sqrt{n} \cdot g(n)$$$.$$$^\dagger$$$

Finally, $$$k^2 \leq 2\sqrt{n}$$$. So $$$f(n) \geq k^2 + \sum_i { a_i \cdot f(i) }$$$ becomes $$$n \cdot g(n) \geq 4n + n \cdot g(\sqrt{n}) + \sqrt{n} \cdot g(n)$$$.

Dividing by $$$n$$$ gives $$$g(n) \geq 4 + g(\sqrt{n}) + g(n)/\sqrt{n}$$$. $$$g(n) = 4\log \log n$$$ satisfies it for sufficiently large $$$n$$$.

$$$\dagger$$$ The root of a tree on $$$n$$$ nodes cannot have more than $$$\sqrt{n}$$$ child subtrees each with at least $$$\sqrt{n}$$$ nodes.

→ Ответить

tmwilliamlin168

5 лет назад, # ^ |

+18

I think that $$$n \log \log n$$$ is also the worst case. We can construct a tree with a structure similar to the Sqrt-tree in which each node with subtree size $$$x$$$ has $$$O \left ( \sqrt{x} \right )$$$ children with distinct subtree sizes of at least $$$O \left ( \sqrt{x} \right )$$$. There will be at least $$$O \left ( \log \log n \right )$$$ layers that take $$$O \left ( n \right )$$$ time each.

→ Ответить

KeyID

5 лет назад, # ^ |

+20

Could you explain why $$$\sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(n) }$$$ is at most $$$\sqrt{n} \cdot g(n)$$$ with more detail? For example, what if the node has only one child whose size is $$$n-1$$$ ?

→ Ответить

5 лет назад, # ^ |

I am wrong, sorry. Do you see how to fix it?

→ Ответить

KeyID

5 лет назад, # ^ |

+10

I don't know how to fix it either. A progress is that there exists a worst case in which $$$a_i \in \lbrace 0,1\rbrace$$$.

Proof: First observe that $$$f(a+b) \geq f(a)+f(b)$$$. Let $$$m$$$ be the largest number which satisfies $$$a_m > 0$$$. If there exists an $$$a_i >1$$$, it doesn't take less time to let $$$a_i=a_i-1, a_m=a_m-1,a_{i+m}=a_{i+m}+1$$$(after this operation, $$$m$$$ becomes $$$i+m$$$).

And I wrote a dp program which runs in $$$O(n^{2.5})$$$ to calculate the worst time. When n=500, the worst time is about 2700 operations. When n=5000, the worst time is about 31000 operations. It seems the time complexity is really something like $$$O(n \log \log n)$$$ or $$$O(n \log n)$$$.

→ Ответить

tmwilliamlin168

5 лет назад, # ^ |

← Rev. 2 →

+10

If we assume that $$$f(n)$$$ is convex, it means that $$$f(x-1)+f(y+1) \ge f(x)+f(y)$$$ where $$$x \le y$$$. Following from this convex property and $$$a_i \in \lbrace 0,1\rbrace$$$, there is a worst case such the sizes of the children of any node with subtree size $$$n$$$ are $$$1, 2, 3, ..., k, n-1-\frac{k(k+1)}{2}$$$.

Consider the heavy path from any node with subtree size $$$n$$$ to a leaf. Whenever we do $$$O \left( k^2 \right)$$$ work and move down to the heavy child, the size of the subtree decreases by $$$O \left( k^2 \right)$$$, so the total work of this heavy path is $$$O(n)$$$.

Each time a node changes the heavy path it's on while moving to the root, the subtree size will be squared, so each node will be included in $$$O(\log \log n)$$$ heavy paths. It follows that the time complexity is $$$O(n \log \log n)$$$.

→ Ответить

KeyID

5 лет назад, # ^ |

← Rev. 3 →

+10

Good proof!

We can prove $$$f(n)$$$ is convex as follows, i.e. $$$f(n+1)-f(n) \geq f(n)-f(n-1)$$$.

If $$$f(n)$$$ is convex when $$$n \leq k$$$, then it can be proved that $$$f(n) \leq c \cdot n \log \log n+d(n \leq k+1)$$$ using your proof. Just let $$$f(n)=n \log \log (n)$$$ since the constants $$$c,d$$$ make no sense(by now) and $$$f$$$ represents the upper bound. We only need to prove $$$g(x)=x \log \log x - (x-1) \log \log (x-1)$$$ is an increasing function.

Though $$$g$$$ isn't always increasing, it's increasing when $$$x > 10$$$. We can assign some constants to $$$f(x) (x \leq 10)$$$ to ensure $$$f(x)$$$ is convex when $$$x \leq 10$$$. Then we add a proper constant $$$d$$$ to $$$f(x) (10<x\leq k+1)$$$ to ensure $$$f(x) (1 \le x \le k+1)$$$ is convex.

So $$$f$$$ is convex.

→ Ответить

gop2024

5 лет назад, # ^ |

+10

Oh, we knew this solution but we thought it`s something like $$$n^{\frac{3}{2}}$$$. Great thanks to you for this comment.

→ Ответить

where_are_you_my_queen

5 лет назад, # ^ |

I am struggling to even see the correctness. Can you please give me some details?

→ Ответить

atlasworld

5 лет назад, # |

gop2024 for div 1 c what you mean by the line.. "Now to find the answer we can use a segment tree that maintains a balance between the number of dishes and the number of pupils for all suffices of values"

which segment tree to use what balance we need to mantain. what to add in segment tree?. can you explain this more.

→ Ответить

meaningIess

5 лет назад, # ^ |

Sort all pupils and dishes with value, add them from big to small, dishes are $$$+1$$$, pupils are $$$-1$$$, the answer is the maximal $$$k$$$ that sum of $$$[k,1000000] > 0$$$.

→ Ответить

ThePonyCoder

5 лет назад, # ^ |

But how to find this maximal k? What to store in nodes?

→ Ответить

meaningIess

5 лет назад, # ^ |

Use segment tree to count the maximum suffix sum.

→ Ответить

ThePonyCoder

5 лет назад, # ^ |

And check every suffix? It'll be comething like O(n log n). Or maybe there is more efficient algo? Can you help me plz?

→ Ответить

5 лет назад, # |

← Rev. 2 →

sir , my approach was same for question 1180b , but it failed at 9 th pretest .. reason was the big product value. i used 'long long int ' and i am not aware of any data type bigger than that. i solved using c language . please help ,how to overcome that.

→ Ответить

https://codeforces.com/contest/1180/submission/55892852

5 лет назад, # ^ |

← Rev. 2 →

here is my solution ,see 9th test

→ Ответить

navneet.h

5 лет назад, # ^ |

C++ can't handle big integer using inbuilt data type, at max i saw int128 something, so instead u can deal with logarithm of numbers and operation performed will be addition .even if u implement in python for handling big integers,it will rise tle,i guess.

→ Ответить

aberent

5 лет назад, # ^ |

You don't need to calculate the product, just work out its sign. This is easy, since after the loop all the a_is are negative (if x>= 0 then |-x-1| > |x|). As such the product is negative if and only if n is odd.

See my code (in Python)

→ Ответить

5 лет назад, # |

← Rev. 2 →

sir , i got the same approach in 1179b ,but was confused to think about the case in which case is not possible and we need to print -1 there ..... by this algo even if some points repeat , it will be very hard to keep on check on each point visited and will further will take a long time ,resulting in TLE ...... can you please give me an example where we cant visits all cell block and hence -1 prints .... thank you;

→ Ответить

ddytxdy

5 лет назад, # ^ |

we never will print -1 because we always have a way which is mentioned above to visit the all cell block.

→ Ответить

ddytxdy

5 лет назад, # |

-8

What is CHT?

→ Ответить

5 лет назад, # ^ |

where i have written CHT ??? or its a general question?

→ Ответить

ddytxdy

5 лет назад, # ^ |

It's a general question.Would you please tell me what CHT is?

→ Ответить