Hello Codeforces!

On April 28, 18:05 MSK will be held Educational Codeforces Round 20.

Series of Educational Rounds continue being held as Harbour.Space university initiative! You can read the details about the cooperation between Harbour.Space and Codeforces in the blog post.

Here is the special message from Harbour.Space University for **girls from India**:

*Harbour.Space University offers a unique opportunity to win a FULL SCHOLARSHIP for #womenintechIndia and join our amazing Data Science, Computer Science or Cyber Security Master's Programme in Barcelona, Spain!Follow this link to complete the application form.*

The round will be **unrated** for all users and it will be held with extented ACM ICPC rules. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours 15 minutes** to solve them. Though this round may come a bit harder than two previous ones, we still hope that everyone will enjoy problems.

The round was prepared by Ivan BledDest Androsov, Mikhail MikeMirzayanov Mirzayanov and me.

Good luck!

**UPD:** Editorial is available here

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | Um_nik | 7 | 129 |

2 | bmerry | 7 | 160 |

3 | kmjp | 7 | 191 |

4 | KrK | 7 | 212 |

5 | rajat1603 | 7 | 235 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | halyavin | 135:-25 |

2 | Nikitka_Herach | 20 |

3 | oipotato | 17 |

4 | tqyaaaaaaaang | 16 |

5 | GreenGrape | 16:-3 |

324 successful hacks and 209 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | kmjp | 0:02 |

B | RockyB | 0:02 |

C | Lewin | 0:07 |

D | Um_nik | 0:15 |

E | eddy1021 | 0:20 |

F | tanphatls987 | 0:07 |

G | ODT | 0:33 |

Hope everyone enjoy the contest. :)

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).。

The duration in Contests list is 2 hours.

What is time complexity needed for acc on C? I can't belive didn't passed.I found all factors of

nin and got sorted array.It's easy to see thatgcd|nand so we need to find largest such thatk|nand that's just binary search on array with factors.I was 100% sure that this will pass.. Really looking forward for solution!my solution works in sqrt(N)*log(sqrt(N))

root(N) passes pretty easily.

you wrote:

`for(int i=1;i*i<=n;i++)`

`i*i=1e10`

overflow, and TLE :D

Thanks,hopefully Educational round :D

yes，I get TLE because k*(k+1)/2 is greater than long long.my solution is sqrt(n).But I did't find the error.So I failed the test.What a sad story it is.

First two solutions works in

O(n). In the third one you have integer overflow in factorization, so for bignit is an infinite loop.Why is my solution for Problem C not passing.?

My idea is suppose that mid is the gcd of all the numbers then, the smallest form of the numbers is

A = 1*mid, 2*mid, 3*mid, ..., k*mid.

Now consider n-sum(A); This value must be a multiple of mid; simply add this remainder to the last item in A.

We can find mid by binary search.

My solutions always fails on test 14. I think my logic is wrong but why?

Because it isn't a monotonic function so you can't use binary search for it.

No it is,that array of divisors is sorted,solution works.I got silly overflow because used int in loop.

He didn't mention that he did binary search over the divisors so I guess he did it over all numbers. Btw, you don't need binary search, you needed to calculate all the divisors so simply see if it fits over all divisors, the complexity is the same.

You are right. I don't need binary search for this problem at all. I can find the best gcd in O(sqrt(n)) time.

I misread your comment. Your solution is the same as mine. Maybe your "mid" value was not selected correctly. Did you check all the divisors of n to choose the optimal mid?

You have to make sure that n / mid >= k(k+1) / 2

tfg is correct.

I did not realize that the gcd should be a divisor of n.

And there is was staring me in the face :(. if gcd*a + gcd*b = n, gcd|n.

However, what of if K is large, how to print all K ? I am getting TLE

http://codeforces.com/contest/803/submission/26733784

Thanks guys,I know where the error in my solution is. The value of k is bounded. We can prove this by the sum of the first k numbers <= 1e10. This leads us to see that k < 1e6 (not exact :) ).

So I can check early for that and exit.

Problem G basically.

One segment tree (used twice) is enough.

i guess i did overkill as i had a normal segtree from [1..K] and a persistent segtree in each leaf node of this segtree.

Can you please explain how?

I just got AC with a normal segtree and an implicit segtree.

What I did was maintain an implicit segtree over the range [1,

N*K], and a normal segtree over the given array, i.e. [1,N].The invariant of the implicit segtree is that for every node, if it exists, it will store the correct minimum value of the range it represents. It will also store a lazy value, which if non zero, means that there was an update at some time on the range it represents, with the value of lazy.

Now when you are updating on the implicit segtree, say the current node completely overlaps with the update interval, then I will mark the lazy value on this node as the current query's value, and free all the nodes in the subtree of this node, since they are not needed anymore.

When I am querying, if I reach a node that completely overlaps with the query interval, and the node is allocated, I will just return the minimum value at this node (which is correct because of the invariant of the implicit segtree).

If I reach a node that completely overlaps with the query interval, but hasn't been allocated, I will first see the lazy value of the closest allocated ancestor of the current node which has a non zero lazy value. If their exist an ancestor with a non zero lazy value, I will return that lazy value. If there doesn't exist any such ancestor, I will query over the segtree made over the original array, as this range hasn't been updated in any way.

It's kind of hard to explain in words, you can try to read the code and see if it helps: Code

Let's write down all values of

`l`

and`r`

for all queries, sort them and remove duplicates. One can see that a range between two consecutive elements can be treated as a point (because no query splits it) and there're clearly`O(q)`

such points.We can build a standard segment tree over this compressed array of query boundaries. Each position should contain a value equal to the smallest element in the given range in the initial array (we can find it using the same segment tree build over the input array. We need to handle "long" ranges carefully: if

`r - l > n`

, we can just return the minimum of the entire array). After that, each query is a range assignment/range max in this segment tree.Thanks for the clever hint. Solved it.

so that's what div 1 people do after solving all the questions...make memes :P

Couldn't solve D because of writing

`while( ++idx && idx < n )`

instead of`while( ++idx < n )`

Any idea how to solve F?

dp[i] = number of subsequences with gcd i

dp[i] = 2^c — dp[2i] — dp[3i] — dp[4i] — ..... where c = number of multiples of i.

Would you explain more details about why and how to use the formula?

that was easy! feel stupid not being able to solve this one.

GCD is 1 if and only if GCD isn't multiple of a prime

So you are looking for |G'(2) n G'(3) n G'(5)....| n is intersection and G(i) means answers where gcd is multiple of i and G'(i) is G negated. Negate this twice and you'll get |G(1)| — |G(2) U G(3) U G(5) ...| use inclusion-exclusion and there you go. G(i) = 2^(frequency of multiples of i) — 1

Is there anyone who may know how to solve problem F?

My solution is O(n log^2 max(a)) but I got TLE.

http://codeforces.com/problemset/problem/585/E

F is an easier version of this problem. Basically the solution is directly inclusion-exclusion using the mobius function.

Thnaks a lot. I will try that problem and study about the related things.

nice problems <3

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Can anyone please explain the solution of problem C?

thank you very much, managed to AC.

You're welcome :)

Why should intended gcd value divide n?

sum of a_i = n Moreover, each a_i can be represented as gcd multiplied by some x_i according to gcd's property. -> sum of gcd * x_i = n ;)

Why does iterating over an array of all divisors get TLE in C? Isn't the max number of divisors quite a small number?

The maximum number of divisors among all numbers in range [1..10^10] doesn't exceed 2304 :)

I had a similar upper bound but my solution got TLE. Probably because of cout. :|

No. I hacked many solutions (yours fails this aswell) with long long overflow) Check something like n = 1, k = 3 500 000 000

So it's actually WA. I had it in my head that k must me < 10^6 but forgot to include it in code :|

In Problem E, I don't understand the line

There is no hand such that the absolute difference before this hand was equal to k., can anyone please clarify?I think it means that the game ends when the absolute difference of number of wins and losses is k.

Thank you very much, by the way, I solved it.

hi, i am sorry if this is a bad question. http://codeforces.com/contest/803/submission/26820750

i got WA in test case 24, it says jury's answer is better than my output but my output gcd is obviously greater that the jury's. Is there something i'm missing here?

[EDIT] it's my fault.