Hi Guys,

Hope you enjoyed Round 174. :) I would like to add a few comments on some of the problems, beyond the editorial.

div 2 A ****

If you know some math, you can actually solve this problem in (!!!) You can show that the answer is φ (p - 1) where φ (n) is the number of positive integers i less than to n with gcd(i, n) = 1. To prove this we first show that there is always at least one primitive root for all primes p. (This is a fairly well known result so I won’t prove it here, but you can find many proofs online) So now assume g is a primitive root Then, the set {g, g², ... g^p - 1} is congruent to the set {1, 2, ... , p - 1}. Furthermore, its not hard to show that gⁱ is a primitive root if and only if gcd(i, p - 1) = 1,  (try it!) hence our formula φ (p - 1). φ (n) can be computed by getting the prime factors of n,  since so this gives us our algorithm. :)

div 1 D ****

Here is a full solution to Codeforces #174 div 1 D.

Let ν₂(n) denote the exponent of the largest power of 2 that divides n. For example ν₂(5) = 0, ν₂(96) = 5. Let f(n) denote the largest odd factor of n.

Note the following formula for sum of arithmetic series:

I claim that the pair (x, y) is cool if and only if and one of the following is true \begin{enumerate} \item ν₂(x) + 1 = ν₂(y) \item ν₂(y) = 0 \end{enumerate} This can be proven by casework on the number on the parity of y.

If y is odd, the average term of the arithmetic sequence is an integer, so f(y) = y divides f(x) and ν₂(y) = 0.

If y is even, the average is of the form .5·k where k is odd, so so it follows that y divides x so f(y) divides f(x),  and furthermore

From this observation it follows that for fixed a_i, a_j(i < j),  we can construct a cool sequence a_i = b_i, b_i + 1, ... b_j - 1, b_j = a_j if and only if and either ν₂(a_i) + j - i = ν₂(a_j) or ν₂(a_j) ≤ j - i - 1.

Now that we have this observation, we can finish the problem using dynamic programming where the kth state is the maximum number of a_i (i ≤ k) we can keep so that it is possible to make a₁, ... a_k cool. Then the answer is just n - max (dp[1], dp[2], ..., dp[n]).

div 1 E ****

Here is a full solution to Codeforces 174 div 1 E. I find this problem beautiful. :)

The first thing to note, is that, if you interpret the problem as a graph, you can compute the answer if you have the degrees (i.e. number of wins) of every cow. Call three cows ``unbalanced’’ if the is one cow that beats the other two. Note that every three cows is either unbalanced or balanced (there are no other configurations of three cows). Thus,

So to count the number of balanced it suffices to count the number of unbalanced. But it is easy to show that so

So now we have reduced the problem to computing the number of wins for each cow. If we do this the dumb way, this is O(MN^2), still way too slow.

Sort the skill levels of the cows (the order of the s_i doesn’t actually matter). s₁ is lowest skill Now consider an n × n grid where the ith row and jth column of the grid is a 1 if the match between cow i and cow j is flipped. The grid is initially all zeros and Farmer John’s query simply flips a rectangle of the form [a, b] × [a, b],  and the outdegree (#wins) of cow i is just (Number of 1’s in range [1,i — 1]) + (Number of 0’s in range [i + 1, N]) = (Number of 1’s in range [1,i — 1]) + (N — i — (Number of 1’s in range [i + 1, N]))

We can process these queries and compute outdegrees using a sweep line with a seg tree on the interval [1,N]. The seg tree needs to handle queries of the form

1. Flip all numbers (0->1, 1->0) in a range [a, b].

2. Query number of 1’s in a range [a, b].

Note that the seg tree needed to handle this is the same seg tree you need for problem ‘lites’ on USACO 2008 Gold http://tjsct.wikidot.com/usaco-nov08-gold.

Once again, thanks for participating!

abacadaea

Here is the editorial for Round #174. Thanks for participating. We hope you enjoyed the problems! :)

Div2 A

We didn’t expect this problem to be so hard :(. This problem can be solved by brute forcing. For any x,  you can compute in O(p) time (iteratively multiply cur = (cur * i) % p, not use pow in math library!), so overall brute force will be O(p²) time.

Note: there is actually algorithm.

The problem was written by abacadaea.

Div2 B

We first note that players who have folded do not affect our desired answer. Then, we can do casework on the number of players who are currently “IN”. If no cows are “IN”, then all the players who are “ALLIN” can show their hands. If exactly one cow is “IN”, she is the only one who can show, so the answer is 1. If two or more cows are “IN”, no one can show their hands. Then we simply count the number of cows of each type and check for each case. The total runtime is O(n).

The problem was written by scott_wu.

Div1 A / Div2 C Consider the problem with only queries 1 and 2. Then the problem is easy in O(n): keep track of the number of terms and the sum, and you can handle each query in O(1). But with query 3 we need to also be able to find the last term of the sequence at any given time. To do this, we keep track of the sequence d_i = a_i + 1 - a_i for i = 1, 2, ..., s - 1,  and a_s,  where s is the length of the sequence. Notice that query 2 only modifies one value of d_i,  and queries 1 and 3 are easily processed and able to update this information. This gives us an O(n) algorithm.

One can also use a fenwick or segment tree to compute the last element, but it’s not nearly as nice :).

The problem was written by abacadaea.

Div1 B / Div2 D

First, suppose we only have the sequence a₂, a₃, …a_n. We note that the current state is only determined by the location and the direction we are facing, so there are only 2·(n - 1) states total. Then, we can use DFS with memorization to find the distance traveled from each state, or  - 1 if a cycle is formed, in O(n) time. Now, when we add a₁ into the sequence, we essentially only need to give the distance traveled starting from each state facing left. The only difference is that if we ever land on a₁ again, there must be a cycle, as we started on a₁. Using this, we can solve the problem in O(n) time total.

The problem was written by scott_wu.

Div1 C / Div2 E

Imagine the problem as a graph where coins are the nodes and Bessie’s statements are directed edges between coins. Because of the problem conditions, the graph must be a set of cycles and directed paths. If there are any cycles in the graph, the answer is clearly 0.

Then, suppose we have a path p₁, p₂, …p_k in the graph, where it is known that we have more coins of type p₁ than of type p₂, more of type p₂ than of type p₃,  and so on. The key observation in this problem is that this is equivalent to having k independent coins of value {a(p₁), a(p₁) + a(p₂), a(p₁) + a(p₂) + a(p₃), …}. The first coin in our new list represents how many more coins of type p₁ than of type p₂ we have, the second coin in our new list represents how many more coins of type p₂ than of type p₃ we have, and so on. However, we must be careful to note that we need at least one of each of the new coins except for the last one, so we can subtract their values from T before doing the DP.

After creating our new set of values, we can run the DP the same way we would run a standard knapsack. This algorithm takes O(nt) time total.

The problem was written by scott_wu.

Div1 D

Let ν₂(n) denote the exponent of the largest power of 2 that divides n. For example ν₂(5) = 0, ν₂(96) = 5. Let f(n) denote the largest odd factor of n.

We can show that for fixed a_i, a_j(i < j),  we can construct a cool sequence a_i = b_i, b_i + 1, ... b_j - 1, b_j = a_j if and only if and either ν₂(a_i) + j - i = ν₂(a_j) or ν₂(a_j) ≤ j - i - 1. Proof here

With this observation, we can use dynamic programming where the kth state is the maximum number of a_i (i ≤ k) we can keep so that it is possible to make a₁, ... a_k cool. The transition for this is O(n),  and the answer is just n - max (dp[1], dp[2], ..., dp[n]). This algorithm is O(n²).

The problem was written by scott_wu.

Div1 E

This will go over the basic outline for solution.

We can show that the answer is where w_i is the number of wins cow i appears to have. Proof here

Now sort the skill levels of the cows (the order of the s_i doesn’t actually matter). s₁ is lowest skill. Now consider an n × n grid where the ith row and jth column of the grid is a 1 if the match between cow i and cow j is flipped. The grid is initially all zeros and Farmer John’s query simply flips a rectangle of the form [a, b] × [a, b].

We can process these queries and compute the number of wins for each cow using a vertical sweep line on the grid and updating with a seg tree on the interval [1,n]. The seg tree needs to handle queries of the form \begin{enumerate} \item Flip all numbers (0->1, 1->0) in a range [a, b]. \item Query number of 1’s in a range [a, b]. \end{enumerate} Note that given this seg tree we can compute the number of wins for each cow at every point in the sweep line as (Number of 1’s in range [1,i — 1]) + (Number of 0’s in range [i + 1, n]). There are O(m) queries so this solution takes time.

The problem was written by abacadaea.