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.

int(Log2(n))+1. By induction, a packet of 1 gives you 1. and for packets 1, 2, 4, ..., n, you know that this combination gives you from 1 to 2n-1. So adding 2n will give you 2n itself, and 2n+1, .... all the way to 2n+2n-1 = 4n-1 = 2(2n)-1

In Java, it's one liner: out.println(32 - Integer.numberOfLeadingZeros(n));

Here is my intuition. At each step we can generate everything from 0 to x. We start with 0 as we can always generate. The next packet we should add is x+1. Now using all these packets we can generate everything from 0 to 2x+1. If we can't add x+1 as it exceeds n, just add the rest and it will be the last packet.

1. I guess, yes.
2. Your program is not checked yet.
3. I didn't understand. I suggest you using a translator at this point.

Just wait a little (15 mins), all the colors will settle and everything will be much clear,

Thankyou Everyone. I get know about my question!

Check this:

Input:

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

Output:

No

I think you maybe do the same thing as me.The childs of a node, will be visited together.
like this case:
7
1 2
1 3
2 4
2 5
3 6
3 7
1 2 3 4 6 5 7
the answer is No
and 
1 2 3 6 7 4 5 
//the answer is Yes (wrong)
the answer is No
and for 1 3 2 6 7 4 5
the answer is Yes
test it on your solution.

No. It is told "valid BFS traversal of the given tree starting from vertex 1".

Parent indices aren't bound to increase:

3
1 3
3 2
1 3 2

They need to be level wise, as well as in same order as their parents. So, for input like-
5
1 2
1 3
2 4
3 5
"1 2 3 5 4" is wrong, as 2 came before 3, so children of 2 should also come before children of 3.

Used the same approach keeping priority_queue as adjacent list but got hacked. Can you please explain this case, 2 1 2 2 1

why this should give "No"? mine gives "Yes"

std::set<>

Cppreference on deque (stack uses deque as underlying container)

deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++)

Hope that helps

Well...

"The standard container classes vector, deque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used."

Why tho?