Editorial of Round #569

(Idea of the problem Div2B — kirillbogatiy)

(Developer of the problem Div2B — gop2024)

Tutorial is loading...

(Idea of the problem Div1A — Mr.Hakimov)

(Developer of the problem Div1A — Mr.Hakimov)

Tutorial is loading...

(Idea of the problem Div1B — gop2024)

(Developer of the problem Div1B — PeregudovSergey)

Tutorial is loading...

(Idea of the problem Div1C — ----------)

(Developer of the problem Div1C — ----------)

Tutorial is loading...

(Idea of the problem Div1D — gop2024)

(Developers of the problem Div1D — ---------- и gop2024)

Tutorial is loading...

Read this comment of saketh about another approach for this problem.

(Idea of the problem Div1E — gop2024)

(Developer of the problem Div1E — TheWayISteppedOutTheCar)

Tutorial is loading...

Tutorial of Codeforces Round 569 (Div. 1)

Tutorial of Codeforces Round 569 (Div. 2)

+105

gop2024
5 years ago
85

Comments (71)

Show archived | Write comment?

agtxdy_orz

5 years ago, # |

← 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

→ Reply

MAOoo_Love_Molly

5 years ago, # ^ |

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.

→ Reply

Fly_37

5 years ago, # ^ |

I support the question.

→ Reply

dragonslayerintraining

5 years ago, # ^ |

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

Correct answer is 1019. Your code outputs 1018.

→ Reply

https://ideone.com/kPEg0m

5 years ago, # ^ |

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

→ Reply

agtxdy_orz

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

dragonslayerintraining

5 years ago, # ^ |

+10

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

Input I used

→ Reply

bsbs

5 years ago, # |

← 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?

→ Reply

EmilConst

5 years ago, # ^ |

← 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.

→ Reply

5 years ago, # |

+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.

→ Reply

msuwakow

5 years ago, # ^ |

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?

→ Reply

5 years ago, # ^ |

← 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.

→ Reply

Antoine

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

← 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.

→ Reply

tmwilliamlin168

5 years ago, # ^ |

+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.

→ Reply

KeyID

5 years ago, # ^ |

+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$$$ ?

→ Reply

5 years ago, # ^ |

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

→ Reply

KeyID

5 years ago, # ^ |

+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)$$$.

→ Reply

tmwilliamlin168

5 years ago, # ^ |

← 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)$$$.

→ Reply

KeyID

5 years ago, # ^ |

← 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.

→ Reply

gop2024

5 years ago, # ^ |

+10

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

→ Reply

where_are_you_my_queen

5 years ago, # ^ |

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

→ Reply

atlasworld

5 years ago, # |

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.

→ Reply

meaningIess

5 years ago, # ^ |

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$$$.

→ Reply

ThePonyCoder

5 years ago, # ^ |

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

→ Reply

meaningIess

5 years ago, # ^ |

Use segment tree to count the maximum suffix sum.

→ Reply

ThePonyCoder

5 years ago, # ^ |

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?

→ Reply

5 years ago, # |

← 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.

→ Reply

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

5 years ago, # ^ |

← Rev. 2 →

here is my solution ,see 9th test

→ Reply

navneet.h

5 years ago, # ^ |

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.

→ Reply

aberent

5 years ago, # ^ |

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)

→ Reply

5 years ago, # |

← 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;

→ Reply

ddytxdy

5 years ago, # ^ |

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

→ Reply

ddytxdy

5 years ago, # |

-8

What is CHT?

→ Reply

5 years ago, # ^ |

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

→ Reply

ddytxdy

5 years ago, # ^ |

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

→ Reply