May I know how to solve C using segment tree? A lot of folks seem to have done it this way.

For problem B,

Can anyone tell me why is my solution failing?

http://codeforces.me/contest/1029/submission/42053121

Here is one of my solutions for problem E which apparently works in linear time without dynamic programming.

It uses BFS O(n+n-1) = O(n) to get vertexes sorted by distance from the first vertex.

The problem E doesn't need any sorting, just dfs on a tree Code

The idea is to connect the parent of the furthest vertices to the first vertex, and then mark all parent's children as used ones.

In D, can't you use a hashmap with the remainders mod k, instead of appending to rem_len_i and binary search? It should decrease the complexity to O(n) too.

can someone help me i am getting tle for 1029D — Concatenated Multiples https://onlinegdb.com/rks1jEywm

My solution for F is getting WA for test case #37 42102854. Can someone please take a quick look? Edit: nevermind, found a silly mistake.

On problem E i got WA on testcase 11. The answear differs by 1. Can anyone tell why? Code : http://codeforces.me/contest/1029/submission/42104188 Edit: Fixed.

The following is a simple and compact C++17 solution for problem 1029A - Many Equal Substrings using the STL function string::substr().

42106199

Врываюсь с линейным временем по E.

Как уже сказал выше автор, выгодно на каждом шаге брать не самую далёкую вершину, а её предка. На самом деле это свойство можно немного усилить. Давайте посмотрим на любой лист, расстояние до которого  > 2. Понятно, что необходимо провести ребро либо в него, либо в его отца. Понятно, что проводить рёбра в отца выгоднее. Поэтому можно на каждом шаге брать вершину, у которой все дети — листья, и проводить в неё ребро, а потом удалять из дерева её и всех её соседей. Из этого соображения легко построить динамику (которая, вообще говоря, является жадностью):

1. Пытаемся обработать какую-то вершину. Сначала запускаемся от её детей и в них ищем ответ.
2. Если после этого хотя бы один ребёнок « плохой », то в нашу вершину следует провести ребро и удалить всех её соседей.

42045552

I solved E using dynamic programming in linear time but it is failing test case 8 , Can someone tell me what is wrong with my code ?

I can't understand why my solution of problem C fails. Can anyone help me?

Задача Е:

Почему делая так как в разборе ответ будет минимальным?

Can someone explain DP on tree solution for Problem E?

Can someone give better explanation for problem D?

For D, we can maintain an array tenp for (10ⁱ)modk, for 1 ≤ i ≤ 10 (since maximum number of digits is 10). We can also maintain a HashMap, that maps the modulus to it's count. That is the key is (A[i])modK,and the value is the number of times a number in A, that has the same value after moding by k.

Now, for every number A[i], we have to find numbers b such that (b × 10^d + A[i])%k = 0.(Where d is the number of digits in A[i]). This can be written as,

. Let $1$ n = A[i]%k , α = (10^d)%k and m = b%k. So, it becomes:

Thus, if $n=0$, then, we can satisfy the condition when m = 0 or when α = 0. We can search for the number of times a zero is inside the HashMap, for checking the m = 0 condition. If α = 0, then we know that every number int A can be used to satisfy the condition, as the whole number will always be divisible by k.

Now, if n > 0, then (m × α)%k = (k - n), thus,

Thus, we'll just have to count the number of occurrences of $m$ inside the HashMap.

My implementation didn't work quite well, so I think there must be some quirk left behind that may make this implementation unreasonable. Any help appreciated!

Can someone help me with 1029D.http://codeforces.me/contest/1029/submission/42209023

For the explanation of question F, what do they mean by "a+b should be area of the outer rectangle." Like is there even an outer rectangle?

In problem D, the only difference between the editorial and my approach is that i've used "unordered_map<int,int> mp[11]" where mp[d][x] stores the frequency of numbers which have d digits and leave a remainder x when divided by k. I get TLE. why?
This is the link to my solution. 42241992

For problem A, isn't the first idea in O(n^3)? Because for this example 'aa..aac', for every k we need to verify the prefix in (n * (n + 1)) / 2 steps. But in the first solution, which implements this idea, the author says that it's in O(n^2) 'Solution (Vovuh, O(n^2))'.

In problem 1029C — Maximal Intersection .

Intersection of some segments [l1,r1],[l2,r2],[l3,r3],....,[ln,rn] is [max li,min li].If 
    this segment has its left bound greater than its right bound then the intersection is 
   empty.

Can anyone give me proof of this. I want to know why this happens?

In Problem C, instead of storing result in partial sum like arrays, we can store 4 values which are max of left, min of right and second largest max of l, second largest min of r.

Now, my result is min — max > 0 ? min — max : 0.

So, now I iterate over all the segments and see if removing that improves my answer which maximum length intersection between the remaining.

if the current segments left is equal to max then I replace max my second largest max, else it remains same. Similarly, if current segments right is equal to min then I replace min by second largest min, else it remains same.

Now I keep checking in the loop if my result increases and finally output the maximum result.

This solution also works in O(n) but extra space complexity is reduced to O(1), since it does not require partial sum array.

43075255

can anyone explain me how to solve problem A ? i can't understand the tutorial :|

I think the time limit of D is too strict.

The key idea in problem E is that: The set represents the vertices which are not yet reachable from 1 in at most 2 steps. Then greedy algorithm for the farthest vertex suffices.

in "CREATING CONTEST" what will be the output if i/p is 1 4 5 7 9 10