he is chamaleon of codeforces

I think gritukan wants to beat the record of Mhammad1 for the maximum rating change in codeforces history.

I'll put my best effort to become cyan :P !
My color was changed at previous Ashishgup's contest , hopefully I'll do that again ^^

Finally, I am green again :P

:D

Dont you ever say that, Unrated round is not a round, its just problem set with standing!

Well, It's already unrated for you :d

Code on your phone :)

Consider charging it

Tried this hack as well and it passed in 1.2/2 sec lol

Same 46069414 1996ms/2000ms

feelsbadman

Looks like codeforces have very fast processors.

Same , I got -50 point since tried to hack this solution with n=1 , s=1e9 :'( 46068920

I also want to know :( dont understand whats wrong with my code

i have this one

5 10

2 2 2 2 10

the answer is 6

E: if a constraint k1 is immediately below (as in there's no other in between and k1 is in the subtree of k2) other k2, the constraint k2 will get subtracted by k1 since you need k1 and it will also appear in the other. Now, group the vertices by "first ancestor that has a constraint" and the problem becomes min-cost max-flow

F: root in any R. You can get the amount of subtrees and the sizes in O(N * K) questions. Now, you can "walk" to the side that has the "heaviest" subtree until you get to the real root. This solves it ok for small K's. For large K's, get random paths and mark the vertices that belong to the path in O(N). There's a very high chance that the most visited vertex is the root.

I too thought so but wasn't sure, though had some time.

I have the same idea, but haven't enough time to debug.

This solution should be good. You have at lest 1/4 chance to find this leafs if you take two random vertices.

I couldn't solve this in the contest, but I had a similar idea. I'm explaining your comment in a little more detail.

Choose two vertices a and b, arbitrarily. Iterate over all the other vertices x and query if b lies between x and a. If that is true, then assign b = x. At the end of this procedure, you have that b is a leaf with n queries.

You can repeat this process for a, and ensure that it is a leaf as well.

However, You cannot assume that the root would lie on the path between the leaves a and b. This can be checked in O(n) queries by finding the length of the path between a and b.

And this is where I got stuck.

Are you suggesting that we could do a probabilistic approach after this? Because a and b would be in different subtrees with probability = ? Does anybody have a deterministic algorithm for this?

auto it=lower_bound(s.begin(), s.end(), v[i].fs);

this works O(N) for set.

You need to call st.lower_bound(val) instead of what you have written.

It's a kind of DP problem.

DP & Divisor Problem = O(N) * O(D^1/2)

So total number of operations is about 100,000,000... (N = 100,000, D = 1,000,000) I think this is correct approach because the time limit is 3 seconds...

Let, dp[i][j] = number of good sequences of size j using elements from 1 to i and dp[i][0] = 1 for i = 1 to n. Now, for every divisor x of a[i], dp[i][x] = dp[i-1][x] + dp[i-1][x-1]. We can reduce the first dimension of dp array by iterating divisors in non increasing order for every element.

Taran106 was much faster at typing than me. Consider this to be an expansion to his excellent answer.

Let's iterate the array from left to right. At each position we will update our answer dp[], where dp[5] gives you the number of good subsequences which have 5 elements, dp[6] gives the number of good subsequences with 6 elements, and so forth. The answer for C will be the sum of these dp values.

Let's say we iterate the values and at some point we arrive at value 9. We want to update dp[] to consider all subsequences which can use this particular 9. Can we continue a subsequence which has 5 elements? No, because 9 would be the 6th element and 9 is not divisible by 6, so this would not be a "good" subsequence according to the problem statement. Ha! Let's look at the divisors of 9: {1,3,9}. Clearly we can only continue subsequences where this 9 will become the 1st, 3rd or 9th element. So for each divisor: dp[divisor] += dp[divisor-1] (Example: if we had 81 ways of creating a subsequence with 2 elements, then we will have 81 new ways of creating a subsequence of 3 elements).

You might be wondering: isn't it slow if we iterate all values and then find the divisors for all values? Any number < 1000000 isn't actually divisible by many other numbers, so there aren't that many divisors. The only question is how do we find them efficiently. There's probably some fast way to do this as we go along, but I chose to pre-calculate divisors for all numbers.

Here's the code for pre-calculating divisors:

for (int divisor = 1; divisor <= n; divisor++) {
    int v = divisor
    while (v <= 1000000) {
        if (v exists in original input) then (add divisor to list of v's divisors)
        v += divisor
    }
}

Intended solution was min-cost max-flow. We don't know about LP solver

Sorry, this is F.

This can be solved using simple randomized algorithm. See my code for ref: 46083309 Right now this WA because I messed up with calculating tree height -_-

Idea is simple — randomly select two nodes. There is more than 50% chance that both of them will be leaf nodes. To check if the selected nodes say x and y are indeed leaf, query n-2 times and find out how many nodes are between them. Repeat for 50 times or so. It is highly likely that you will get two leaves. (As high as probability that quick sort is nlogn).

Now you know the path between x and y. So the root node has to be one of them. Just query for each of them to find who is the actual root.

I've got an explanation for how I constructed MCMF graph in a comment below, if you're curious.

What greedy do you mean?

Yes. keep assigning the latest TV where show is completed. And also check if that TV should be given and taken or should be kept with you.

i agree

I used an approach with that complexity and got pretest passed in ~1500ms. Taken implementation into accounts, maybe? ;)

Problem B:

The order of the columns doesn't matter, so we can safely sort them in non-descending order. We can see that we must keep at least one block in each column.

Let's denote Highest as the currently highest block kept, initially Highest = 0.

Let's denote Max as the maximum height of all columns, s as the total number of blocks initially.

Traverse through the sorted columns, with each column, update Highest by min(Highest+1, Height[i]).

Let's denote the minimum number of kept blocks as Min, initially Min = n. Add Max - Highest into Min, thus, the answer would be s - Min.

Problem C:

This is a dynamic programming problem. Let's denote dp[i][j] as the number of valid subsequences that has i elements and the rightmost one is the j^th one in the original array.

Thus, the recursive function would be: .

Obviously, we can't build an entire dp 2D-array (guaranteed TLE/MLE given the problem's constraints). Therefore, we'll only consider (and keep the dp values only in) the cases when a[j] is divisible by i. To do this, vectors and two-pointers techniques are required.

You can see my solution for better understanding: 46075711.

Hope these guides help! :D

C is dp + number factorization. At first find all the factors of arr[i] which are not more than i. f be the array of all those factors. For every number in f, the ans is dp[f[i]-1]. Update dp[f[i]] to dp[f[i]]+=ans[f[i]].

Yes, that was nice. This contest was really well written. All tasks have pretty good and short solutions. Thanks to Ashishgup for that contest.

It is just use x=x-y then it will be b-a+1

Because the constant factor is super low. This isn't something with arrays and mods, this is just straight addition.

And computers become faster and faster nowadays. It's not like 10^6 operations will take 1 second...

The CF servers are really fast. That's it. If you do a for-loop of 1e9 iterations, it runs is less about 1 second. Also TL for A is 2s. You can try in custom-test.

Deleting elements directly on a set while you're working on that exact set will alter, or worse, mess up the entire iterators of that set completely. You should consider keeping the about-to-be-deleted elements in a dummy vector, and delete those after the traverse of that set is done.

You are erasing and iterator from set. So when it do it++, it doesn't belong to the set. You should first move, and then erase. Some like:

auto nxt = next(it);
erase(it); 
it = nxt;

Same. Thought we need O(n*log(n))

It should be ceil(s*1.0/n)

Use double instead of float ... 46090088

Since there are at least leaves, the probability of a pair of random vertices being a pair of leaves is , so the probability of fail per test is . I doubt this is breakable.

http://codeforces.net/contest/1061/submission/46085722 — WA (in systest) http://codeforces.net/contest/1061/submission/46090449 — AC

The only difference in codes is random seed :(

I used a deterministic approach for small K and random approach for large K. It makes the probability of failing smaller.

Could you tell us what is the mistake if we fail in test 43?

any help bro, i m also stuck there?