Codeforces Round #523 (Div. 2)

6 years ago, # |

+13

Is F supposed to be just randomly select 2 points and check to see if they're both leaves, then isolate the root from the path? That's the idea I got, but no time to code.

→ Reply

taran_1407

6 years ago, # ^ |

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

→ Reply

bartkaw

6 years ago, # ^ |

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.

→ Reply

shardex

6 years ago, # ^ |

For k=2 probability is 1/8. Because it is 1/2 to pick a leaf and 1/4 to pick a leaf from different subtree.

→ Reply

proofbycontradiction

6 years ago, # ^ |

← Rev. 2 →

+10

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 = $\text{[math]}$ ? Does anybody have a deterministic algorithm for this?

→ Reply

Jakube

6 years ago, # ^ |

Yes (I did it exactly the way you described). The probability that you don't find a path containing the root using this approach is $\text{[math]}$ . Then the probability of getting accepted is $\text{[math]}$ . Sounds good enough for me.

→ Reply

vhnvn

6 years ago, # ^ |

← Rev. 2 →

First use n-2 query to find a leaf, and then randomize select another vertex, fail probability is now (1 / k)⁵⁰ (reserve 10n query for the root finding).

→ Reply

Jakube

6 years ago, # ^ |

Nice, even better. Also notice that you can find the root with a Quick-select approach, which should be a lot better than 10n.

→ Reply

dilsonguim

6 years ago, # ^ |

← Rev. 2 →

+11

After the contest I wrote a deterministic solution for problem F: Code.

The idea is to start at a non-leaf node and go up to the root step by step. If we are at node X and X is not the root, we need to figure out which subtree of X is the largest one and what node in this subtree is the closest to X. This could be done by partitioning all the other nodes by subtree using at most KN queries, but it would exceed the allowed number of queries for large values of K. To fix this, observe that we can stop partitioning the nodes after looking at $\text{[math]}$ of them. For the remaining nodes, we need just to see if they belong to the largest subtree. With extra N queries, we can figure out the node in the largest subtree that is the closest to X. In total, we would need less than 2N queries at each step.

→ Reply

nilesh8757

6 years ago, # |

+12

B was really good. :)

→ Reply

starboy_jb

6 years ago, # |

+38

again a very good contest by Ashishgup.

→ Reply

https://mirror.codeforces.com/contest/1061/submission/46081755

6 years ago, # |

Why this nlogn approach getting TLE at test case 10 in D problem.

→ Reply

Len

6 years ago, # ^ |

+13

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

this works O(N) for set.

→ Reply

6 years ago, # ^ |

How to solve this question D then?

→ Reply

http://www.cplusplus.com/reference/set/multiset/lower_bound/

6 years ago, # ^ |

I checked out it on multiple website. It says set and multiset has complexity O(logn)

→ Reply

Len

6 years ago, # ^ |

+29

But it's s.lower_bound(val)...

→ Reply

himanshujaju

6 years ago, # ^ |

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

→ Reply

Because the reference says so

6 years ago, # ^ |

How this is log(n)?

→ Reply

himanshujaju

6 years ago, # ^ |

→ Reply

6 years ago, # ^ |

Calling lower bound on the set is log n because it knows it is a set, but if you use regular lower bound on the iterators it just steps through linearly until it reaches the answer.

→ Reply

6 years ago, # ^ |

Okay. That's cool. Thanks. Nice hack btw.

→ Reply

Hash

6 years ago, # |

any idea about the 8th pretest for D?

→ Reply

6 years ago, # |

+14

How to solve C?

→ Reply

ndb1996

6 years ago, # ^ |

← Rev. 3 →

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

→ Reply

Taran106

6 years ago, # ^ |

+16

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.

→ Reply

prathmesh_01

6 years ago, # ^ |

← Rev. 2 →

Why do we need to iterate the divisors in non-increasing order ? Also can you please show how the solution works for some sample case, thanks.

→ Reply

Taran106

6 years ago, # ^ |

← Rev. 2 →

To reduce the first dimension of dp array. Let x be divisor of a[i]. We need dp[i-1][x-1] and dp[i-1][x] because we need to know how many good sequence of size x-1 and x can be made using elements upto i-1. So current element(ith) can't contribute in this count. If we ignore the first dimension and iterate divisors in non increasing order then for every divisor x, dp[x-1] and dp[x] is guaranteed to be the count of size x-1 and x up to i-1 elements since for each x we didn't make any update on dp[x] or dp[x-1] till now due to current element as a result of iterating them in non-increasing order.

Consider 6 as current element. Divisors are 1,2,3,6. Take them in non increasing order. First comes 6 , dp[6] = dp[6]+d[5] as dp[5] is count of good sequence of size 5 up to previous element. Then 3, dp[3] = dp[3] + dp[2]. dp[2] is count of good sequence of size 2 upto previous element. And so on. If we iterated in increasing order we would have updated dp[2] before dp[3] due to current element and while updating dp[3] we would use this incorrectly updated dp[2].

→ Reply

baobab

6 years ago, # ^ |

← Rev. 5 →

+20

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
    }
}

→ Reply

PoomrokC

6 years ago, # |

I'm ready for -100 rating XD . Gratz to all who performs well.

→ Reply

teja349

6 years ago, # |

Is E solvable by LP solver?? If can be, can someone give link to their solution using LP solver. Or can you point you some resources for LP solvers explaining their algorithm and rough complexity and also your library code..

Or we need to convert into max flow min cost network somehow?

→ Reply

Ashishgup

6 years ago, # ^ |

+12

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

→ Reply

triveni

6 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

Kognition

6 years ago, # ^ |

I think you're talking about F, but they're talking about E :)

→ Reply

baobab

6 years ago, # ^ |

It's not enough to find 2 leaf nodes (they don't always have a path that goes through root). For example, in the sample picture the probability of finding 2 leaf nodes which have a path through root is 15% (8/15 * 7/14).

→ Reply

Kognition

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # |

is D greedy? It passed pretest but it seems suspicious

→ Reply

natofp

6 years ago, # ^ |

What greedy do you mean?

→ Reply

teja349

6 years ago, # ^ |

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.

→ Reply

shardex

6 years ago, # ^ |

Is there any proof that this greedy approach works?

→ Reply

optimizer

6 years ago, # |

For question A why solutions with O(s) complexity passed. When I tried to hack it with n=1 and s=1000000000 I got an unsuccessful hack and the time was 608ms.

→ Reply

Vicennial

6 years ago, # |

+45

Really cool problem set!
Although, I do wish the contest was 2.5 hours instead!

→ Reply

6 years ago, # ^ |

i agree

→ Reply

shadowfax

6 years ago, # |

← Rev. 3 →

Ignore.

→ Reply

aditya10

6 years ago, # |

What was the pretest 10 for Problem C?

→ Reply

Adibov

6 years ago, # |

Problem F was really nice, but it needs more time to solve.

→ Reply

KeNaj712

6 years ago, # |

← Rev. 2 →

Was O(n*sqrt(ai)) complexity in problem C too much or it could get AC?

→ Reply

6 years ago, # ^ |

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

→ Reply

P0LyFish

6 years ago, # |

Does anyone solve E using mincost flow?

→ Reply

Jhin

6 years ago, # |

probably the way I solved B is the worst yikes ..

I can't look at my code so I don't miss more iq

→ Reply

Wandoka

6 years ago, # |

The statements were clean and easy to understand, very nice :D

→ Reply

Kognition

6 years ago, # |

← Rev. 4 →

+35

My approach for E:

First thought when looking at the problem: small n, lots of constraints, choosing vertices to maximize something, sounds like flow (this is CF so I am very skeptical of seeing flow because flow problems are very rare here, but I had a good gut feeling about this).

It's not immediately clear how to solve this problem using flow. For simplicity, let's imagine the problem with only one candidate and one set of demands. It does seem like some kind of choice-making thing, and one's initial thought might be to make a bipartite graph with demands on one side, and cities on the other, with edges from a demand to everything in its subtree of capacity 1, and edges from the source to each demand with capacity equal to the number of nodes required by that demand. The costs of the edges into city i would be - a_i. This, unfortunately, runs into some problems because there isn't any way to ensure that all the demands are met, and the flow for each particular city that gets chosen will be overcounted depending on how many demand subtrees that city is a part of.

Here comes what I believe is the key observation: if v is a descendant of u, then v's subtree is entirely contained in u's subtree. So, consider two demands (k₁, x₁), (k₂, x₂) where k₂ is a descendant of k₁. Now, for everything in k₁'s subtree that is not in k₂'s subtree, we can create an edge from the demand (k₁, x₁) to that city, and then we can create an edge from the demand (k₁, x₁) to the demand (k₂, x₂) with capacity x₂. This way, the constraints from both demands are now taken into account and any compatibility issues will be reflected in the flow. However, one last thing is that we need to make sure that all the demands are met, so the way we do this is by making the cost a pair of ints, where the second number is the - a_i when appropriate and the first number is - 1 if the edge is entering a demand node, and 0 otherwise. This way we will force our algorithm to use all the demands, if possible.

It turns out that adding the second candidate in is not bad, we simply create an identical graph but mirrored and add it as a third "layer" to our graph, with the mirror of the source being the target of course.

When we run MCMF, we first check to see if the first value is as negative as possible (this I believe should be the negative sum of all the x's in the demands) and if so, the second value should be the negative of our answer.

EDIT: I realize this explanation is not incredibly clear, but I think my code is pretty clear, so here's the submission: 46121195

→ Reply

aiden_pearce

6 years ago, # |

Can Anyone explain how to solve B and C?

→ Reply

6 years ago, # ^ |

+11

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: $\text{[math]}$ .

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

→ Reply

AbdAl-mateen

6 years ago, # ^ |

Hi iristran911, your explanation for Problem B is really nice but your implementation seems complicated.I followed your explanation and implemented it in a very easy way. see my submission: 46105126

→ Reply

https://mirror.codeforces.com/contest/1061/submission/46079795

6 years ago, # ^ |

Nice one! :D

I did mess up with things a little bit (kind of frustrated for submitting wrong B thrice previously), so the source code for B didn't look so good ;)

→ Reply

optimizer

6 years ago, # ^ |

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

→ Reply

eidan

6 years ago, # |

+37

It was really annoying that formula for problem D was b — a instead of b — a + 1, which is more intuitive. Still, nice problem, good contest.

→ Reply

bartkaw

6 years ago, # ^ |

+43

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

→ Reply

teja349

6 years ago, # ^ |

+26

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

→ Reply

guptautkarsh028

6 years ago, # |

How can this code work for n = 1 and S = 10^9? It should give TLE since the loop is running 10^9 times. Can anyone explain this, please? It cost me 1 unsuccessful hack.

→ Reply

6 years ago, # ^ |

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

→ Reply

bartkaw

6 years ago, # ^ |

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

→ Reply

-osdajigu-

6 years ago, # ^ |

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.

→ Reply

rsd511

6 years ago, # |

Why is this code: https://mirror.codeforces.com/contest/1061/submission/46085323 giving RTE? Please help, thanks.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

rsd511

6 years ago, # ^ |

Okay got it! Thanks a lot! :)

→ Reply

-osdajigu-

6 years ago, # ^ |

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;

→ Reply

rsd511

6 years ago, # ^ |

Thanks a lot! :)

→ Reply

queragion2726

6 years ago, # |

+30

I never thought that O(N*sqrt(N)) be accepted on problem C. I just.. used all time to find better solution but failed.

Back to the blue ;(

→ Reply

soul_voyage

6 years ago, # ^ |

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

→ Reply

6 years ago, # |

Why in Problem A if you use Ceil test 35 gives WA?

→ Reply

skyscraper

6 years ago, # ^ |

It should be ceil(s*1.0/n)

→ Reply

6 years ago, # ^ |

But i used float?So, don't need to use this "*1.0". This is my code 46067360

→ Reply

YouKn0wWho

6 years ago, # ^ |

← Rev. 2 →

+14

Daily reminder:

Never use ceil() function. Instead of using ceil(n/k) use (n+k-1)/k
If you want to use ceil() use it like this:
```
(int)(ceil(1.0*n/k)+1e-9)
```

→ Reply

6 years ago, # ^ |

Thanks,but i changed my type o variable to double and the code receive accepted.And I understand your tip I'll use in nexts contests

→ Reply

Benq

6 years ago, # ^ |

Use double instead of float ... 46090088

→ Reply