Eran's blog

By Eran, 8 years ago, translation, In English

703A — Mishka and Game

In this problem you had to do use the following algo. If Mishka wins Chris in the current round, then increase variable countM by 1. Otherwise (if Chris wins Mishka) increase variable countC. After that you had to compare this values and print the answer.

703B — Mishka and trip

Let's look at the first capital. Note that the total cost of the outgoing roads is c[id1] · (sum - c[id1]), where sum — summary beauty of all cities. Thus iterating through the capitals we can count the summary cost of roads between capitals and all the other cities. But don't forget that in this case we count the roads between pairs of capitals twice. To avoid this on each step we should update sum = sum - c[idcur] , where idcur is the position of current capital. In the end we should add to the answer the cost of roads between "non-capital" neighbour cities.

Complexity — O(n).

703C — Chris and Road

Imagine that the bus stands still and we move "to the right" with a constant speed v. Then it's not hard to see that movement along the line y = (u / v) · (x  -  v · t0) is optimal, where t0 — time in which we begin our movement. In this way answer is t = t0 + (w / u).

If t0 = 0, then we start our movement immediately. In this case we need to check that our line doesn't intersect polygon (either we can cross the road in front of a bus, or the bus is gone).

Otherwise we need to find such minimal t0 that our line is tangent to the polygon. It can be done with binary search.

Complexity — O(nlogn).

Exercise: Solve this problem in O(n).

703D — Mishka and Interesting sum

Easy to see, that the answer for query is XOR-sum of all elements in the segment xored with XOR-sum of distinct elements in the segment. XOR-sum of all numbers we can find in O(1) using partial sums. As for the XOR-sum of distinct numbers... Let's solve easier problem.

Let the queries be like "find the number of distinct values in a segment". Let's sort all the queries according to their right bounds and iterate through all elements of our array. We also need to make a list last, where last[value] is the last position of value on the processed prefix of array. Assume we are at position r. Then the answer for the query in the segment [l,  r] (l ≤ r) is , where cnt[i] = 1 if last[ai] = i and 0 otherwise. It's easy to store and update such values in cnt. When moving to the next position we have to make the following assignments: cnt[last[ai]] = 0, cnt[i] = 1, last[ai] = i. To get described sum in O(logn) we can use segment tree (or Fenwick tree) instead of standard array.

Now let's turn back to our problem. Everything we have to do is to change assignment cnt[i] = 1 to cnt[i] = ai and count XOR-sum instead of sum. Now we can solve this problem in O(nlogn).

Solution (with Fenwick)

P.S.: Also there is a solution with O(nsqrtn) complexity (using Mo's algo), but we tried to kill it :D

703E — Мишка и делители

Let's use dp to solve this problem.

Suppose dp[i][d] is the minimal number of elements on prefix of size i, that their product is divisible by d. It's easy to see that dp[i][d] = min(dp[i  -  1][d],  dp[i  -  1][d  /  gcd(d,  ai)]  +  1). That is so because it's optimal to take as much divisors of ai as possible. Answer — dp[n][k].

Let's imrove our solution. Notice, that as d we should use only divisors of k (which in the worst case would be 6720). As for gcd, we can easily find it in O(primes(k)), where primes(k) — number of primes in decomposition of k. We also need to renumber our divisors according to their prime decomposition.

To get AC in this problem you had to optimize described dp and add minimization of used elements' sum. Final complexity — O(n · divs(k) · primes(k)).


Full text and comments »

  • Vote: I like it
  • +70
  • Vote: I do not like it

By Eran, 8 years ago, translation, In English

Hi everyone!

Codeforces Round #365 (Div.2) takes place today on 4th of August at 18:05 MSK. As usual Div.1 participants can join out of competition.

I am the author of all the problems, and this is my first round on Codeforces. I advise you to read all the problems, hope you will enjoy them :)

I'd like to thank GlebsHP and for helping me in preparing problems, MikeMirzayanov for the great Codeforces and Polygon platforms and IlyaLos for some useful adviсe.

In this round you will meet Mishka, a little polar bear. She is still young, that's why she may have some problems in finding answers for difficult questions. Will you help her to cope with some of them? :)

UPD. 5 problems, 2 hours to solve them and scoring distribution: 500 — 1000 — 1750 — 2000 — 2250

UPD. We apologize for the inconvenience. All solutions will be judged soon.

UPD. Round is unrated.

UPD. The contest is over. Congratulation to the winners!

Div1: 1. uwi 2. kmjp 3. savinov 4. BigBag 5. KrK

Div2: 1. meteor 2. TmEnd 3. chenjiamin 4. vokeal 5. Denisson

Editorial will be published in the nearest time.

UPD. Editorial

Full text and comments »

  • Vote: I like it
  • +242
  • Vote: I do not like it