so it was your 5th contest last year.

Yeah, it's relatively easy than last time.

Last year problems were harder than problems of the year before last year :)

Dude i don't know how, but you got to div1 in only 1 year. Last year's B was very hard for me too back then. I read it now and solved it instantly. I am sure it will be the same way for you. It's actually just playing with prefixes and sufixes.

Just solved B from last year, DP was definetely overkill.

People remember an year old event -- the scar must have been real.

lol, mail says 7 problems, here it's written 8 problems!!

then a matrix multiplication will suffice

div 1 + div 2 = for everyone

2 hours

Don't worry, you're already blue :)

It actually means Brainstorming, but if you're looking for something funny, then the words can be broken to get an another, very interesting meaning. Click

It probably pertains to when the height of tree is at least 4, such that there is an erroneous nesting while doing the traversal. For e.g.

INPUT:

6
1 3
1 2
2 4
3 5
4 6
1 2 3 4 5 6

EXPECTED OUTPUT: Yes

Announcement states that a[1] is not guranteed to be 1 in tests.

According to the first step in BFS algorithm, vertex 1 is always chosen as root for the algorithm, but a₁ is not guaranteed to be 1.

In this case, answer is "NO".

Don't compare us with tourist he is Legendary <3

My hacks were:

200000
1 2
1 3
1 4
...
1 200000
1 200000 199999 199998 199997 ... 2

(TLE)

3
1 2
2 3
2 3 1

(WA)

Let's first consider slow solution. Let deg[v] be the current degree of vertex v. Add (deg[v], v) into set, delete minumum degree vertex while it's degree < k and update degrees of vertices. Answer will be this set's size. Now to support queries, we can just do everything from backwards, instead of adding you will delete edge, and now it is easy to implement in O(n*log(n)).

Hint: Reverse the process (instead of adding edges from 1 to m, erase edges from m to 1).

We can answer the queries backwards.

We build a graph based on the relation, and maintain the degree of each vertices in a set.

When we answer a query, we remove the vertices with degree < k, and remove their corresponding edges recursively. Then, all vertices has atleast k neighbours. The answer is the number of remaining vertices. After computing the m-th query, we need to remove the m-th edges given in the input.

I got caught there too, I think you have to check (when iterating over guys with depth d-1 as parents) to skip over leaves.

I think something like traversing nodes in level i in some order but their children in level i+1 are traversed in a different order (node k appeared before node l in level i but children of node l appeared before children of node k).

Just looking at the levels will not be enough. For example if 4 is the child of 3, and 5 is the child of 2, then 1 3 2 5 4 also comes out to be correct whereas the correct order should be 1 3 2 4 5.

I guess that test might be checking for naive solutions which only check all nodes in one level, which is not sufficient. It is important to check nodes in each depth in groups based on the node on depth — 1. Compare these two cases:

7
1 2
2 3
2 4
1 5
5 6
5 7
1 2 5 3 6 4 7

ANS: No , because 3 and 4 have to be next to each other in the traversal path, whereas

7
1 2
2 3
2 4
1 5
5 6
5 7
1 2 5 3 4 6 7

the answer to this test is Yes. Unfortunately, I didn't finish my solution in time...

Problem D

You'll have to wait until system testing is done. Only then the problem will be added for practice.

7

1 2

1 3

2 4

2 5

3 6

3 7

1 2 3 4 6 5 7

Your code says "yes" to this, while it should be "no". Children of a node in BFS would be printed together. So, correct order is 4 5 6 7. or 6 7 4 5. Depending on 2 3 or 3 2.

The problem is equivalent to counting for every v_i = 1 + i * (k - 1) the sum .

Assume that with two equal numbers, the one with higher index is larger.

To solve this, find for every i the values prev[i] and next[i], where prev[i] is the minimum index i such that maximum value in [prev[i], i] = val[i], and next[i] the maximum index such that the maximum value in [i, next[i]] = val[i]. Now:

Let cou[i] =  the number of intervals [a, b] such that len([a, b]) = v_j for some j and prev[i] ≤ a ≤ i ≤ b ≤ next[i]. We can calculate this with inclusion-exclusion: let count(len) be the number of intervals [a, b] such that len([a, b]) = v_j for some j, and 1 ≤ a ≤ b ≤ len. Now cou[i] = count(next[i] - prev[i] + 1) - count(i - prev[i]) - count(next[i] - i).

The answer is .

Yeah

how can you find the 2 submissions?

Probably, your hack generating code had a runtime error.

Well I explicitly removed the a[0] condition because I misunderstood the announcement, smh

Could you please share your idea with me? I tried to solve it with Suffix Automaton and Link-cut Trees but didn't manage to finish debugging in time.

I can suggest the following solution:

Build suffix automaton for string s. Append symbols to s one by one and answer queries whenever we reach their right border r. To answer the query with string x: feed symbols of x to automaton one by one and iterate over the next (bigger than current in x) symbol. Now we need to check is last occurrence so far of suffix of particular length of current state of automaton  ≥ l. It could be done in the following way: consider the tree of suffix links of automaton, call it T. Then you append new symbol to s, update biggest right border for the state corresponding to the current prefix of s (we must also update right borders for all suffix links of that state, but lets don't do that and ask queries for maximum in subtree of T instead).

This is in a way I implemented it during the contest (and had wa2 due to some typos). I think it should pass (you will make much less queries than n·A).

UPD: it passed in 405 ms 42402008

solution =

Same. I solved B and C, wasn't able to solve A. I feel like an idiot as everyone got the logic within 5 minutes.

Every number has a primary representation. And never does it happen that you use some power of 2 twice. Thus get all powers of 2 lower than this number! That is (int)log2(n)+1.