reality's blog

By reality, history, 5 months ago, In English,

798A - Mike and palindrome

Let cnt be the number of such that si ≠ sn - i + 1.

If cnt ≥ 2 then the answer is NO since we must change more than 1 character.

If cnt = 1 then the answer is YES.

If cnt = 0 and n is odd answer is YES since we can change the character in the middle, otherwise if n is even the answer is NO because we must change at least one character.

Complexity is O(|s|).

Solution: Link

798B - Mike and strings

First of all, you must notice that the operation of removing the first character and appending it to the left is equivalent to cyclically shifting the string one position to the left.

Let's denote by dpi, j the smallest number of operations for making the first i strings equal to string si moved j times.

Let f(i, j) be the the string si moved j times,then .

The answer is min(dpn, 0, dpn, 1, ..., dpn, |sn| - 1).

The complexity is O(|S|3 × n).

Solution: Link

798C - Mike and gcd problem

First of all, the answer is always YES.

If then the answer is 0.

Now suppose that the gcd of the sequence is 1. After we perform one operation on ai and ai + 1, the new gcd d must satisfy d|ai - ai + 1 and d|ai + ai + 1 d|2ai and d|2ai + 1. Similarly, because d is the gcd of the new sequence, it must satisfy d|aj, j ≠ i, i + 1.

Using the above observations we can conclude that , so the gcd of the sequence can become at most 2 times bigger after an operation. This means that in order to make the gcd of the sequence bigger than 1 we need to make all numbers even. Now the problem is reduced to the following problem:

Given a sequence v1, v2, ... , vn of zero or one,in one move we can change numbers vi, vi + 1 with 2 numbers equal to . Find the minimal number of moves to make the whole sequence equal to 0.

It can be proved that it is optimal to solve the task for consecutive ones independently so we divide the array into the minimal number of subarrays full of ones, if their lengths are s1, s2, ... , st,the answer is .

Complexity is .

Solution: Link

798D - Mike and distribution

In the beginning, it's quite easy to notice that the condition " 2·(ap1 + ... + apk) is greater than the sum of all elements in A " is equivalent to " ap1 + ... + apk is greater than the sum of the remaining elements in A ".

Now, let's store an array of indices C with Ci = i and then sort it in decreasing order according to array A, that is we must have ACi ≥ ACi + 1.

Our answer will always have size . First suppose that N is odd. Add the first index to our set, that is make p1 = C1. Now, for the remaining elements, we will consider them consecutively in pairs. Suppose we are at the moment inspecting AC2k and AC2k + 1. If BC2k ≥ BC2k + 1 we make pk + 1 = C2k, else we make pk + 1 = C2k + 1.

Why does this subset work? Well, it satisfies the condition for B because each time for consecutive non-intersecting pairs of elements we select the bigger one, and we also add BC1 to the set, so in the end the sum of the selected elements will be bigger than the sum of the remaining ones.

It also satisfies the condition for A, because Ap1 is equal or greater than the complement element of p2 (that is — the index which we could've selected instead of p2 from the above procedure — if we selected C2k then it would be C2k + 1 and vice-versa). Similarly Ap2 is greater than the complement of p3 and so on. In the end we also add the last element from the last pair and this makes the sum of the chosen subset strictly bigger than the sum of the remaining elements.

The case when N is even can be done exactly the same as when N is odd, we just pick the last remaining index in the end.

The complexity is .

Solution: Link

798E - Mike and code of a permutation

Let's consider ai = n + 1 instead of ai =  - 1. Let's also define the sequence b, where bi = j such that aj = i or bi = n + 1 if there is no such j. Lets make a directed graph with vertices be the indices of the permutation p with edges of type (a, b) representing that pa > pb. If we topologically sort this graph then we can come up with a possible permutation: if S is the topologically sorted graph then we can assign to pSi number i.

In this problem we will use this implementation of topological sort.

But how we can find the edges? First of all there are edges of the form (i, bi) if bi ≠ n + 1 .For a vertex i he visited all the unmarked vertices j (1 ≤ j < ai, j ≠ i) and you know for sure that for all these j, pj < pi. But how we can check if j was already marked? The vertex j will become marked after turn of vertex bj or will never become unmarked if bj = n + 1. So there is a direct edge from i to j if j = bi or 1 ≤ j < ai, j ≠ i and bj > i.

Suppose we already visited a set of vertices and for every visited vertex node we assigned to bnode value 0 (for simplicity just to forget about all visited vertices) and now we want to find quickly for a fixed vertex i an unvisited vertex j with condition that there is edge (i, j) or say it there isn't such j, if we can do that in subquadratic time then the task is solved. As stated above the first condition is j = bi if 1 ≤ bi ≤ n, this condition is easy to check. The second condition is 1 ≤ j < ai and bj > i, now consider vertices with indices from interval 1..ai - 1 and take j with maximal bj. If bj > i we found edge (i, j) otherwise there are no remaining edges. We can find such vertex j using segment tree and updating values while we visit a new vertex. In total we will visit n vertices and query the segment tree at most 2 × (n - 1) times (n - 1 for every new vertex and n - 1 for finding that there aren't remaining edges).

Complexity and memory are and O(N).

Solution: Link

Read more »

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

By reality, history, 5 months ago, In English,

Hi everyone!

I'm pleased to announce Codeforces Round #410 (Div. 2) that will take place on Friday, 17:35 MSK. I'm the writer of the round.

I'd like to say thanks to Alex netman Vistyazh and Marcel yosei-san Bezdrighin for feedback and help in preparing the round and to MikeMirzayanov for awesome platforms : Codeforces and Polygon.

I hope you will like the problems.

Good luck and have fun!

UPD: Scoring distribution: 500 — 1000 — 1500 — 2000 — 2500

UPD 2. The round is finished. Congratulations to winners:

Div 2:

  1. Gonens

  2. Blue_Sky.

  3. kimnoia

  4. RAG3

  5. jtnydv25

Div 1:

  1. OnionPringles

  2. unused

  3. uwi

  4. Reyna

  5. alexrcoleman

Editorial: Link

Read more »

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

By reality, history, 15 months ago, In English,

A.Mike and Cellphone

Author:dans.

Developed:reality,ThatMathGuy

We can try out all of the possible starting digits, seeing if we will go out of bounds by repeating the same movements. If it is valid and different from the correct one, we output "NO", otherwise we just output "YES".

C++ code
Another C++ code
Another C++ code
Python code

B. Mike and Shortcuts

Author:dans,reality

Developed:reality,ThatMathGuy

We can build a complete graph where the cost of going from point i to point j if |i - j| if ai! = j and 1 if ai = j.The we can find the shortest path from point 1 to point i.One optimisation is using the fact that there is no need to go from point i to point j if j ≠ s[i],j ≠ i - 1,j ≠ i + 1 so we can add only edges (i, i + 1),(i, i - 1),(i, s[i]) with cost 1 and then run a bfs to find the shortest path for each point i.

You can also solve the problem by taking the best answer from left and from the right and because ai ≤ ai + 1 then we can just iterate for each i form 1 to n and get the best answer from left and maintain a deque with best answer from right.

Complexity is O(N).

C++ code with queue
C++ code with deque
Python code

What if you have Q queries Q ≤ 2 × 105 of type (xi, yi) and you have to answer the minimal distance from xi to yi.

C. Mike and Chocolate Thieves

Author:dans,reality

Developed:reality,ThatMathGuy

Suppose we want to find the number of ways for a fixed n.

Let a, b, c, d ( 0 < a < b < c < d ≤ n ) be the number of chocolates the thieves stole. By our condition, they have the form b = ak, c = ak2, d = ak3,where k is a positive integer. We can notice that , so for each k we can count how many a satisfy the conditions 0 < a < ak < ak2 < ak3 ≤ n, their number is . Considering this, the final answer is .

Notice that this expression is non-decreasing as n grows, so we can run a binary search for n.

Total complexity: Time ~ , Space: O(1).

C++ code
Another C++ code

D. Friends and Subsequences

Author:reality

Developed:reality,ThatMathGuy

First of all it is easy to see that if we fix l then have . So we can just use binary search to find the smallest index rmin and biggest index rmax that satisfy the equality and add rmax - rmin + 1 to our answer. To find the min and max values on a segment [l, r] we can use Range-Minimum Query data structure.

The complexity is time and space.

C++ code O(N)
C++ code O(N log N)
C++ code O(N log ^ 2 N)
Another C++ code

What if you need to count (l1, r1, l2, r2), 1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n and .

Hint:Take idea from this problem.

C++ code for Bonus

E. Mike and Geometry Problem

Author:reality

Developed:reality,ThatMathGuy

Let define the following propriety:if the point i is intersected by p segments then in our sum it will be counted times,so our task reduce to calculate how many points is intersected by i intervals 1 ≤ i ≤ n.Let dp[i] be the number of points intersected by i intervals.Then our answer will be . We can easily calculate array dp using a map and partial sum trick,here you can find about it.

The complexity and memory is and O(n).

C++ code
Another C++ solution

what if where l, r are given in input.

I'm really sorry that problem A was harder than ussually.

Read more »

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

By reality, history, 15 months ago, In English,

Hi everyone!

I want to present you the Codeforces Round #361 (Div. 2) that will take place on the 6th of July at 19:35 MSK. The contest was prepared by Gabriel reality Cojocaru and Mihail ThatMathGuy Tarigradschi.

I'd like to thank Dan dans Sagunov and Gleb GlebsHP Evstropov for their help in preparing the round and for making the round possible,Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

Good luck in the contest!!

UPD1.In this round you will help our hero Mike solve tasks he encounters every day.

UPD2. Editorial

UPD3.Congratulations to the winners of the round.

Div 1:

1.Um_nik

2.cgy4ever

3.anta

4.HellKitsune

5.ksun48

6.williamhu08

7.Kaban-5

8.I_love_Tanya_Romanova

9.skyvn97

10.RomeoFantastik

Div 2:

1.Sky4teen

2.TudorMiclovan

3.NoFearOfTheDark

4.Hirasawa_Yui

5.Chloe_fan

6.AnonymousBunny

7.fenchen

8.Grandpa

9.6eJIa9IzZzTeHb

10.raiders

Read more »

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