Author: GreenGrape

Tutorial is loading...

Author: GreenGrape

Tutorial is loading...

Author: GreenGrape

Tutorial is loading...

Author: GreenGrape

Tutorial is loading...

Author: ashmelev

Tutorial is loading...

Author: Errichto

Tutorial is loading...

Author: lewin

Tutorial is loading...

Oh well, to be honest I'm so sad that the expected solution for D is indeed

O(N^{3}), since 700^{3}is so strict. I'm coding the same solution but still got TLE instead.Why is the time limit 1 sec instead of 2 and the bound 700 instead of 500? It's like they want us to TLE...

Maybe we need O(N^3/???) to AC

I had the same problem.I added the heuristic of breaking when an answer is found instead of iterating completely from l to r. this reduced time to 93 ms.

Yes, mine also passed because of the heuristic optimisation. I think that the test cases were weak. I did not even precompute the gcd, still it got AC.

I only passed using this idea. Thanks.

I thought

O(n^{3}) might be TLE so I used STL bitset. So did fjzzq2002.I saw that many contestants who coded it iteratively had TL while most of the memoization solutions passed (including mine). This might be caused because a lot of states are practically unreachable.

English tutorial for E?

I don't know how long it will take for an English tutorial, but here is what I did that uses at most 4

n^{2}moves:1) Get every block into their own row. What I did to accomplish this is to push every block in the first column up as high as they can. So, if there are

k_{0}blocks in the first column, they take rows 1...k_{0}. Then, I take the blocks in the second column--let's say there arek_{1}of them--and push them into positionk_{0}+ 1...k_{0}+k_{1}. Do this for each column.2) Now that each block is in its own row, I want to get them each to their own column, but in a specific way. Let's say that, in the end,

a_{0}blocks need to end up in the first column. Then, I make sure that thosea_{0}blocks take up the firsta_{0}columns (1...a_{0}). Then, similarly, ifa_{1}blocks need to be in the second column by the end, then I make sure to move those blocks into columnsa_{0}+ 1...a_{0}+a_{1}. Do this for every column.3) Now that each block is in their own column, simply move each one to its final row.

4) Now you should be able to move each block into its final column. Even though there can be multiple blocks in a row, they will appear in the same order that they have to be in the end due to our work in step 2. Thus, each block can be shifted within its own row to its correct spot.

Everything here can be accomplished pretty nicely with code. My submission: 41868501

Could you elaborate at step 1? I mean is there any nice way to implement shifting x cubes in given colum to positions i...i+x-1?

There exists

O(N^{3}/WordSize) solution for D:At first we need calculate bitset

good[i] for eachi, wheregood[i][j] isgcd(a[i],a[j]) > 1.We need 3 dps:

can[left][right] — stores bitset, wherecan[left][right][x] is true if there is possible to create some tree with all values fromlefttorightand root is inx.canLeft[left] — stores bitset, wherecanLeft[left][x] is true if there is possible to create some tree with all values fromlefttox- 1 and connect it as left subtree tox.canRight[right] — stores bitset, wherecanRight[right][x] is true if there is possible to create some tree with all values fromx+ 1 torightand connect it as right subtree tox.Now we could calculate each

can[left][right] =canLeft[left] &&canRight[right].After that we need update

canLeft[left][right+ 1] =can[left][right] &&good[right+ 1](

canRight[right][left- 1] can be updated in the same way).Each operation is

O(N/WordSize), so total complexity isO(N^{2}·N/WordSize) =O(N^{3}/WordSize).Link to AC solution with this algorithm: https://codeforces.com/contest/1025/submission/41855097

Well, the worse you can do in a competition is getting rejected just because some a*****e copied your solution from ideone.com. Not gonna use ideone.com anymore for contests.

The message I received:

Attention!Your solution 41833175 for the problem 1025A significantly coincides with solutions cfbfgf/41832971, rahul1995/41833175, getSchwifty/41833466. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.You can still use IdeOne, but make your code secret.

I always wondered why people use ideone instead of a compiler/IDE on a local machine.

The program on my computer takes longer

You can also use repl.it

Some people have used some online resources and have got plagiarism message,check the third party rule is changing blog

Anyone knows anything faster than N^3 for D? For someone who sucks at implementation, I don't think I would dare submit such a solution when N = 700 (especially when task doesn't even give use 2 seconds)

Even idea toward a faster solution would be appreciated, thanks!

There is idea of solution in

O(N^{3}/WordSize) with bitsets:https://codeforces.com/blog/entry/61323?#comment-452741

My solution with Divide and Conquer with memoization has asymptotic complexity

O(n^{3}) as 1021839 pointed out, however the actual maximum number of operations isn* 1 + (n- 1) * 2 + (n- 2) * 3 + ... +n(the length of every [l,r] segment multiplied by the amount of such segments) which forn= 700 results in < 10^{8}operations, which fits inside 1 second ... the idea is to try to make each element the root, and split the array into two subarrays and recursively solve for them. The parent of a subarray can either be r+1 or l-1, and those are the memoized states.Code: 41859995

Note that this is only a recursive implementation of the editorial, but explains why it works for n=700 without much problems.

Your

`dac`

function is in factO(N^{3}), since there are up toN^{2}possible states and each state takesO(r-l) time to process. (There might be a stronger bound on this DP thanO(N^{3}) overall, but if so I'm not aware of it.)Usually an author is given just after an editorial for a corresponding problem. So don't get confused: I invented F, not E :D

also, my code if someone wants to take a look: link.

The code is pretty clean, but I don't understand exactly what are you doing? Sorting vectors that each pair creates by what, how does that make L and R the k1 and k2 from the editorial?

Could you elaborate on the loop that looks like two pointers a bit more?

Thanks,

LandRin my code denote the number of points on left and right from the line (k_{1}andk_{2}from the editorial).And yes, I use two pointers. I iterate over point

pin one half, and move indexiLof some point in the other half.Thank you for clarifying that part.

However, I still do not understand how did you exactly sort the vectors, what does your operator < function for comparison of two points (in this case vectors from one point to another it would appear) mean?

nice tutorial for c. Thank You!

Can someone please explain the intuition behind using DP for Problem D?

If you take some binary search tree (BST) and write it's values in increasing order — every subtree will be presented as subarray of result array.

Now we have that result array and we need find if there exists possibility to build some BST with edge constraint from statement.

As we know, each subtree in BST consists of root, left subtree and right subtree. In array it will be presented as index

rootand two subarrays [left...root- 1] and [root+ 1...right].So we could use dynamic programming

dp[left][right][root] — "could we build BST on subarray [left...right] and root isroot(left≤root≤right)".Let's use additional matrix

canEdge[i][j] — "can we build edge betweena[i] anda[j]:gcd(a[i],a[j]) > 1".Now we could write formulas for calculating

dp:dp[i][i][i] =true— we always can build tree with one vertex as its root;dp[left][right][left<root<right] =dp[left][root][root] &&dp[root][right][root] — if tree [left...right][root] is correct then [left...root][root] and [root...right][root] are correct trees too;dp[left][right][left] = there existsrootin [left+ 1...right] thatdp[left+ 1][right][root] &&canEdge[left][root] istrue— if root is the left one then we need find where it connects to it's right subtree;dp[left][right][right] = there existsrootin [left...right- 1] thatdp[left][right- 1][root] &&canEdge[right][root] istrue— if root is the right one then we need find where it connects to it's left subtree.At this moment our

dpalready can be calculated inO(N^{3}) with formulas above, but it hasO(N^{3}) states that is not so good for memory.Let's store only trees where root is the left one or the right one —

dp[left][right][isRootRight] (0 is for the left, 1 — for the right) :dp[left][right][0] = exists somerootin [left+ 1...right] thatdp[left+ 1][root][1] &&dp[root][right][0] &&canEdge[left][root] — we need take left subtree with thisroot, right subtree with it and connect to new root;dp[left][right][1] = exists somerootin [left...right- 1] thatdp[left][root][1] &&dp[root][right- 1][0] &&canEdge[right][root] — similar to first;Now answer for whole array is

trueif exists somerootthatdp[left][root][1] &&dp[root][right][0].New

dphas onlyO(N^{2}) states but calculates inO(N^{3}) as previous one.Wow, Thanks for such a wonderful answer!!

For your 2nd point shouldn't it be :

`dp[left][right][left < root < right] = dp[left][root-1][root] && dp[root+1][right][root]`

?Sorry correct me if I am wrong!

No, it's correct.

By definition of dp root should be inside subarray, but [

left...root- 1] and [root+ 1...right] don't containrootinside.This formula means "if you have some correct tree where root is the right one and other tree where the same root is the left one — you can merge them in one tree".

Okay!! Thanks a lot for reply and for wonderful answer. Indeed it helped a lot.

I understand the solution but only after seeing the editorial. During the contest I got the fact that it's a DP problem and very similar to matrix chain multiplication but I was not able to reduce it to O(N^3). It would be helpful if you provide some insights on how you think about optimizations in DP ? That's a less touched topic I believe.

You're right, this is a topic that is rarely touched on at all. In fact, the optimizations are usually just given right away in the editorial without much motivation (not knocking the author; it's difficult to write out the motivation well if you already know the solution). I'll try to explain my thought process on the DP optimization problems I've done. Keep in mind I'm not too high rated, so I've only done a handful of DP problems where optimization was needed for AC, so I won't be talking about anything like convex hull trick or Knuth optimization.

My original O(n^4) DP was dp[l][r][k], where dp[l][r][k] = 1 if you can create a subtree on [l, r] with k as the root (

l≤k≤r), and 0 otherwise. This had linear updates, and I imagine this was what most people's first iteration of the DP was.In general, the reason one can do DP optimizations is if many states being stored are actually unnecessary, or can be encapsulated in another state. Storing [l, r] seems necessary, since the subarrays can differ and the BSTs will vary wildly, so that's probably not where we look to optimize. However, let's look at k, the root of the subtree. Why exactly are we storing the root? Well, you might argue, it's because when we are recursing on node i as the root, we need to know if one of the possible roots of [i+1, r] is not coprime to node i.

But wait, that's the thing. We only need to know if ONE of the possible roots is not coprime. We don't actually need to store every root that works. And for the subtree on [l, r], the only possible parents of this subtree are l-1 and r+1. So all we need to check in [l, r] is if any of the possible roots are not coprime to l-1 and r+1. That should reduce the state to O(n^2), with linear updates, so O(n^3) (Note: PRECALCULATE GCDs OF PAIRS).

I hope that was somewhat insightful, since that was my (very abridged) thought process during the contest.

An awesome explanation!

Can you explain me the intuition behind the isRight state in your DP?

Fundamentally, one should use DP if a problem can be solved by solving subproblems of an identical structure, and these subproblems get repeated when trying to find a solution.

The biggest key to noticing that you need DP is that BSTs are recursively defined data structures, i.e. the left subtree and right subtree of any node are both BST's themselves. Say you are trying to solve the problem on all the nodes from [0, n-1]. You know that some node i will be the root. Then, you notice that you need to solve the exact same problem as the original one, but on the nodes [0, i-1] and [i+1, n-1]. That should be the observation that immediately triggers "DP" to pop into your head.

There is a different, very nice solution for problem B, working in

O(Nlog4e18) time. Click here to find my implementation from the contest. This solution requires more reasoning, but is significantly easier to implement.Firstly, let’s define

a|bas meaning thatais a factor ofb, so there exists some integerksuch thatb=a*k. Let’s firstly consider any primep. Consider any input pair (a,b). Ifpis to be a solution of the problem, thenp|aorp|bfor every input pair (a,b). However, sincepis prime, this is equivalent to saying thatp|a*bfor every input pair (a,b).Let’s consider the value

curr, which is initially set to 0. For every pair (a,b) in the input, let us setcurr=gcd(curr,a*b). (Here we assume thatgcd(0,x) is equal tox.) In other words, we have thatcurr=gcd(a_{0}*b_{0},a_{1}*b_{1}, …,a_{N}*b_{N}). Let us consider any prime factorpthat may have been a solution to the problem. If it may have been a solution to the problem, that means thatp|a*bfor every input pair (a,b), as we have shown above. Therefore, ifpdivides every producta*b,pmust also divide the gcd of every producta*b, which means thatp|curr. Therefore any prime number which may be a solution is a factor ofcurr. Now, let us consider any prime factorpofcurr. Obviously sincep|curr, thenp|a*bfor every input pair (a,b), sop|aorp|b. Therefore, any prime factor ofcurris a solution to the problem. As a result, this means thatcurrhas prime factors which correspond exactly to the prime solutions to the problem.Now, let’s consider the case that

curr= 1. When this is the case, since we have shown above thatcurrhas prime factors which correspond exactly to the prime solutions to the problem, since 1 has no prime factors, there are no prime numbers which are solutions to the problem. Now, let us consider any possible solution to the problem, if one exists. Ifsis some solution, then it is obviously the case that any prime factorpofsis also a solution. However, since no prime numberspare solutions, then ifshas any prime factors it is also not a solution. Therefore the only solution in this case iss= 1, which by the problem constraints is not a solution at all. Thus, in this case, we must output - 1.Let us now consider the other case, where

curr> 1. We will show that, if we consider every pair (a,b) one more time, and docurr=gcd(curr,a) ifgcd(curr,a) > 1 elsecurr=gcd(curr,b), then we can outputcurr, and it will always be a solution. Firstly, let’s prove that doing this method will always produce a solution to the problem or 1. If we consider this method, then by definition, since we take the gcd ofcurrwith eitheraorbfrom every pair, that means thatcurr|aorcurr|bafter every pair we process. Therefore, our final resultcurrwill divideaorbfor every single pair (a,b). The only problem here is thatcurrmight be equal to 1. We will now prove that, if you use the method above, this will not happen. Let us assume thatcurris initially greater than 1, before processing some pair (a,b). This means thatcurrhas at least one prime factorp; let’s consider any prime factorp. We know from our definition ofcurrthatp|a*bfor every pair (a,b), which means thatp|aorp|b. Let us assume, without loss of generality, thatp|a. (Ifp|binstead, then we can reverse our reasoning and arrive at the same result.) Sincep|a, that means that there is some integerxsuch thata=x*p. In addition, there is some integerysuch thatcurr=y*p, sincep|curr. Therefore,gcd(curr,a) =gcd(y*p,x*p) =p*gcd(x,y) ≥p. As a result, any prime factorpofcurrthat was initially a factor ofawill be preserved, andcurrwill always be greater than 1 after processing each step, assuming that it was originally greater than 1 (which it was). Therefore, using this method, our final result forcurrwill always be such thatcurr|aorcurr|bfor every input pair (a,b), and alsocurr> 1. Thus, in this case, not only is there always a solution, but we can generate it using this above method inO(Nlog4e18) (thelog4e18 comes from gcd finding).very cool reasoning. I have a question derived from this one. If change the definition of WCD to :select arbitrary one number from each pair,let the GCD of all these n numbers be WCD, is there an efficient way to find a solution?

I don't quite understand what your question is. If you consider the GCD of all n numbers for every possible selection within each pair, then every single GCD that you find will be a valid WCD, and every factor of these will be as well. So your change of definition is only a very minor one. As a matter of fact, the solution I propose above will always find some number that is a WCD according to your definition (if one exists).

thanks for reply to me.I think you misunderstood my definition as WCD = gcd(gcd(

set_{1}),(set_{2}),......(set_{n})), whereset_{i}means one possible selection. but mine is just like WCD = gcd(set_{i}),set_{i}means an arbitrary selection of all possible selections. thus, for some input, there may be multi different WCDs, if WCD can only be 1,print -1, else print any possible WCD greater than 1. If input is:in my definition, answer could be gcd(6, 30) = 6 or gcd(15, 30) = 15, but in the original problem, answers include 2, 3 and 5. That's the difference. So, is there an efficient way to find a such WCD greater than 1 if there exists any?

I see. I'm pretty convinced that the solution I give above actually works for this problem as well. The value of

currwill always correspond to the GCD ofset_{i}for some selectionset_{i}. In addition, it will also correctly determine whether or not such a WCD greater than 1 exists. It may be a useful exercise to attempt proving this for yourself (or disprove it).I will rethink it , Thanks a lot.

Cool solution. I'd like to share my (a little different) way to deal with this problem B ( code ). The idea is to take GCD of all pair's LCM, let it be 'allGcd'. Then any prime factor allGcd will be the answer, because it's a factor of at least one number in a pair. But allGcd may be up to 1e18, so we can just take GCD of it and one of the numbers in one of the pairs (the one, which doesn't return 1, if such exists), reducing allGcd at least to 1e9. Finally, we iterate up to sqrt(allGcd) to find first number, which is a factor (it will be prime, so we got what we wanted)

Nice idea. Out of interest, and to check whether or not I actually understand your solution, is it necessary to take the lcm? Because it seems to me that you could just take the gcd of the products

a*b, and then try the gcds witha[0] andb[0] respectively as you do.Actually you're right, didn't think about it earlier

As this points out, if you were to have:

such that

xandyare primes > 10^{9}, theirlcm() will be their product which is > 1e18.So you can't loop to it'ssqrt().Instead, you can find the prime factors of

a[0] andb[0] and return any one of them that dividesallGcd.That's why I reduce it at least to 1e9 by taking GCD of allGcd with a[0] and allGcd with b[0], when choose the one, which isn't 1

Oh yes you're right I didn't read that

Why at the end we have to again take gcd with any one pair?? "so we can just take GCD of it and one of the numbers in one of the pairs"

Because sqrt(allGcd) may be up to 1e9, so it will be TLE. By taking GCD with one pair we guarantee that allGcd will become < 2e9, so cycle to sqrt won't be too long

for problem B, can i say the max (number of divisor) from number 2 <= x <= 2*(10^9) is largest number of 2*3*4*5....(n times) that not exceed 2*(10^9) ? if so, i try to calculate it and it has only max 11 divisor, so at first a[0] and b[0] can have 22 divisor (my approach is generate initial divisors that can be the answer, that is number that divide first number or second number at the most top input).

my implementation using set to store the initial divisor, for each pair 1 to n, traverse the set, if the number cant divide first pair and cant divide second pair, delete it from the set. so at worst no deletion (because each times traverse 22 number on set?) and the worst case is sqrt(2*(10^9)) + 150k*22 < 10^8 (expected 1s) operation, but my code TLE, why?

2*3 is 6 so you would multiply that twice. Number with most divisors below 10^9 has more than 1000 divisors

i see, thanks!

What about the editorials for Round #504 ??

For problem C, now I know that we can get the answer by concact two same strings together and scan it in O(N) time, but why it can be solved by implementation? I think it is an O(N^2) algorithm.Here is my code which got an accepted. Well, I didn't think it would pass all tests before...To view my code for problem C

Can anyone give more details of a rigorous analysis of G?

Are you familiar with how to use martingales to analyze random walks? If so, this technique is very similar.

I skipped some steps in defining what exactly my random variable is. Here it is specifically. Let

X_{i}be a random variable representing the expected value of the potential at timeiminusi.From the analysis, it is not too hard to show that

E(X_{i + 1}|X_{0},X_{1}, ...,X_{i}) =X_{i}(this is because our expected potential increases by one, and alsoiincreases by one, so there is no change in the expected value).We have some unknown stopping time

T, we know thatX_{T}= 2^{n - 1}- 1 -T, and the problem is to findE(T), which is equal toE(2^{n - 1}- 1 -X_{T}).Using the optional stopping theorem, we have

E(X_{T}) =E(X_{0}). So, we haveE(T) = 2^{n - 1}- 1 -E(X_{0}). We already know how to computeE(X_{0}), which is just the current potential of the state.Hi, lewin. Can I ask a question on how to define the potential? It's still not very clear to me. My guess of the procedure is:

Let the potential to be

f(k),pandqto be the numbers of followers for two selected startups. Then the difference of the potentials after a step is: [p*f(0) +f(q+ 1) +q*f(0) +f(p+ 1)] / 2 -f(p) -f(q)And we want to the difference to be constant, so we can choose

f(k) = 2^{k}- 1. Is this similar to what you think?for problem(B) how can we find the prime factorization of number upto 10^9 in logn time ..if we make the seive of lowest prime divisors..even that can be made just upto 10^6 which will find prime divisors for numbers <=10^6 ..please somebody explain how to do it

Finding the prime factorization is done is time. But since there are only primes, doing the linear divisibility check for each prime takes a total of time.

sorry, but i didn't understand how there are only distinct log(10^9) primes to be checked out and what they are, please explain it a bit more

The number of distinct prime factors of a number

kis . It's a good exercise to think about why.Hint: Think about approximately how many non distinct prime factors there are in

k(in terms of big-O). Is this more or less than the number of distinct prime factors?If you're having trouble figuring out how many non distinct prime factors there are in

k, here's another hint: What if the only prime factor was 2? How many non distinct prime factors are there? Again, is this more or less than the total number of non distinct prime factors?i know that the number of distinct prime divisors can be at max O(logn) for 'n', initially i mistakenly thought about creating 'n' union set of distinct prime divisors and then iterating through them to find a number which is present in all sets which is even possible if a,b <=10^6. now after seeing your code things are clear that we are just doing all work for a random pair to get its union set of prime divisors, and then just checking for each element in set because if answer exist then it must be present in this set..overall thanks a lot, learnt few things.