Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

645A - Amity Assessment

Idea: yummy

One solution is to just brute force and use DFS to try all the possibilities. Alternatively, note that two puzzles can be changed to each other if and only if the A, B, and C have the same orientation—clockwise or counterclockwise—in the puzzle. A third option, since the number of possibilities is so small, is to simply classify all of the 4! = 24 configurations by hand.

Code

#include <bits/stdc++.h>
using namespace std;

string b, b1, b2, e, e1, e2;

int main(){
  cin >> b1 >> b2 >> e1 >> e2;
  swap(b2[0], b2[1]);
  swap(e2[0], e2[1]);
  b = b1 + b2;
  e = e1 + e2;
  b.erase(b.find('X'), 1);
  e.erase(e.find('X'), 1);
  if((b + b).find(e) != string::npos){
	cout << "YESn";
  } else {
	cout << "NOn";
  }
}

645B - Mischievous Mess Makers

Idea: ksun48

Loosely speaking, we’re trying to reverse the array as much as possible.

Intuitively, the optimal solution seems to be to switch the first and last cow, then the second and second-to-last cow, and so on for k minutes, unless the sequence is reversed already, in which case we are done. But how can we show that these moves give the optimal messiness?

It is clear when 2·k ≥ n - 1 that we can reverse the array with this method.

However, when 2·k < n - 1, there are going to be cows that we must not have not moved a single time. Since in each move we swap at most 2 cows, there must be at least n - 2·k cows that we have not touched, with p_i = i. Two untouched cows i and j must have p_i < p_j, so there must be at least $\text{[math]}$ pairs of cows which are ordered correctly.

In fact, if we follow the above process, we get that p_i = (n + 1) - i for the first k and last k cows, while p_i = i for the middle n - 2·k cows. From this we can see that the both i < j and p_i < p_j happen only when i and j are in the middle n - 2·k cows. Therefore we know our algorithm is optimal.

An O(k) solution, therefore, is to count how many incorrectly ordered pairs (i, j) are created at each step and add them up. When we swap cow i and (n + 1) - i in step i, this creates 1 + 2·(n - 2i) more pairs. So the answer will be $\text{[math]}$ .

We can reduce this to O(1) by using our earlier observation, that every pair except those $\text{[math]}$ pairs are unordered, which gives $\text{[math]}$ total pairs (i, j). Note that this does always not fit in a 32-bit integer.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	LL n, k;
	cin >> n >> k;
	LL c = max(n-2*k,0LL);
	LL a = n*(n-1)/2-c*(c-1)/2;
	cout << a << endl;
}

645C - Enduring Exodus

Idea: GlebsHP

First, observe that the k + 1 rooms that Farmer John books should be consecutive empty rooms. Thus we can loop over all such sets of rooms with a sliding window in linear time. To check the next set of rooms, we simply advance each endpoint of our interval to the next empty room. Every time we do this, we need to compute the optimal placement of Farmer John’s room. We can maintain the position of his room with two pointers—as we slide our window of rooms to the right, the optimal position of Farmer John’s room should always move to the right or remain the same. This solution runs in O(n).

Alternatively, we can use binary search or an STL set to find the best placement for Farmer John’s room as we iterate over the intervals of rooms. The complexity of these approaches is $\text{[math]}$ .

Code

#include <bits/stdc++.h>
using namespace std;

int N, K, res = 1e9;
string S;

int next(int i){ // finds the next empty room
  do {
    i += 1;
  } while(i < N && S[i] == '1');
  return i;
}

int main(){
  cin >> N >> K >> S;
  int l = next(-1), m = l, r = l;
  for(int i = 0; i < K; i++){ // sets up the sliding window
    r = next(r);
  }
  while(r < N){
    while(max(m - l, r - m) > max(next(m) - l, r - next(m))){
      m = next(m);
    }
    res = min(res, max(m - l, r - m));
    l = next(l);
    r = next(r);
  }
  cout << res << 'n';
}

645D - Robot Rapping Results Report

Idea: abacadaea

The robots will become fully sorted if and only if there exists a path with n vertices in the directed graph defined by the match results. Because it is guaranteed that the results are not contradictory, this graph must be directed and acyclic—a DAG. Thus we can compute the longest path in this DAG via dynamic programming or a toposort.

We now have two cases. First, if the longest path contains n vertices, then it must uniquely define the ordering of the robots. This means the answer is the time at which the last edge was added to this path. Otherwise, if the longest path has fewer than n vertices, then multiple orderings satisfy the results and you should print - 1. Note that this algorithm runs in O(n + m).

Another solution to this problem binary searches on the answer. For some k, consider only those edges that were added before time k. We can determine if the robots could be totally ordered at time k by running a toposort and checking if the longest path covers all n vertices. This might be more intuitive for some, but has a complexity of $\text{[math]}$ .

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int N, M, dp[MAXN], res[MAXN];
vector<pair<int,int>> adj[MAXN];

int check(int v){
  if(dp[v]) return dp[v];
  dp[v] = 1;
  for(auto p : adj[v]){
    int n = p.first;
    if(check(n) + 1 > dp[v]){
      dp[v] = dp[n] + 1;
      res[v] = max(res[n], p.second);
    }
  }
  return dp[v];
}

int main(){
  scanf("%d%d", &N, &M);
  for(int i = 0; i < M; i++){
    int a, b;
    scanf("%d%d", &a, &b);
    a -= 1, b -= 1;
    adj[a].push_back({b, i + 1});
  }
  for(int i = 0; i < N; i++){
    if(check(i) == N){
      printf("%dn", res[i]);
      return 0;
    }
  }
  printf("-1n");
}

645E - Intellectual Inquiry

Idea: yummy

For simplicity, let’s represent the letters by 1, 2, ..., k instead of actual characters. Let a[i] denote the number of distinct subsequences of the string that end in the letter i. Appending the letter j to a string only changes the value of a[j]. Note that the new a[j] becomes $\text{[math]}$ —we can have the single letter j, or append j to any of our old subsequences.

The key observation is that no matter what character j we choose to append, a[j] will always end up the same. This suggests a greedy algorithm—always appending the character j with the smallest a[j]. But how do we know which a[j] is minimal while maintaining their values modulo 10⁹ + 7?

The final observation is that if the last occurrence of j is after the last occurrence of j' in our string, then a[j] > a[j']. This is true because appending j to the string makes a[j] larger than all other a[i]. So instead of choosing the minimum a[i], we can always choose the letter that appeared least recently. Since the sequence of letters we append becomes periodic, our solution runs in $\text{[math]}$ . Of course, we can also find the least recently used letter with less efficient approaches, obtaining solutions with complexity O((L + n)k).

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const int MAXK = 26;
int N, K, last[MAXK], ord[MAXK];
ll dp[MAXK], sum;
string S;

bool comp(int a, int b){
  return last[a] < last[b];
}

void append(int c){
  sum = (sum - dp[c] + MOD) % MOD;
  dp[c] = (dp[c] + sum + 1) % MOD;
  sum = (sum + dp[c]) % MOD;
}

int main(){
  cin >> N >> K >> S;
  fill(last, last + K, -1);
  for(int i = 0; i < S.size(); i++){
    int c = S[i] - 'a';
    last[c] = i;
    append(c);
  }
  iota(ord, ord + K, 0);
  sort(ord, ord + K, comp);
  for(int i = 0; i < N; i++){
    int c = ord[i % K];
    append(c);
  }
  cout << (sum + 1) % MOD << 'n';
}

645F - Cowslip Collections

Idea: desert97

After each query, the problem is essentially asking us to compute the sum of $\text{[math]}$ for each choice of k flowers. One quickly notes that it is too slow to loop over all choices of k flowers, as there could be up to $\text{[math]}$ choices of k species.

So how can we compute a sum over $\text{[math]}$ terms? Well, we will definitely need to use the properties of the gcd function. If we figure out for each integer a ≤ 10⁶ how many times $\text{[math]}$ occurs in the sum (let this be g(a)), then our answer will be equal to $\text{[math]}$ overall all a.

It seems that if d(a) is the number of multiples of a in our sequence, then there are $\text{[math]}$ k-tuples which have gcd a. Yet there is something wrong with this reasoning: some of those k-tuples can have gcd 2a, or 3a, or any multiple of a. In fact, $\text{[math]}$ , the number of gcds which are a multiple of a.

We will try to write $\text{[math]}$ as a sum of these $\text{[math]}$ . We’ll take an example, when a ranges from 1 to 4. The sum we wish to compute is g(1) + 2g(2) + 3g(3) + 4g(4) which can be written as

(g(1) + g(2) + g(3) + g(4)) + (g(2) + g(4)) + 2(g(3)) + 2(g(4)),

$\text{[math]}$

In general, we want to find coefficients p_i such that we can write $\text{[math]}$ as $\text{[math]}$ . Equating coefficients of g(a) on both sides, we get that $\text{[math]}$ . (The mathematically versed reader will note that p_i = φ(i), Euler's totient function, but this is not necessary to solve the problem.)

We can thus precalculate all p_i in $\text{[math]}$ using a recursive formula: $\text{[math]}$ . We can also precalculate $\text{[math]}$ for each l ≤ 200000, so in order to output $\text{[math]}$ after each query we should keep track of the values of the function d(i), the number of multiples of i. When receiving c_i flowers, we only need to update d for the divisors of c_i and add $\text{[math]}$ . If we precompute the list of divisors of every integer using a sieve or sqrt checking, each update requires O(divisors).

Thus the complexity of this algorithm is $\text{[math]}$ or $\text{[math]}$ preprocessing, and O((n + q)·max(divisors)).

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const int MAXN = 200005;
const int MAXA = 1000005;
int N, K, Q, A[MAXN];
int use[MAXA], phi[MAXA], cnt[MAXA];
vector<int> divisors[MAXA];
ll bin[MAXN], res;

ll inv(ll a, ll p){
  if(a == 1) return 1;
  return (p - p / a) * inv(p % a, p) % p;
}

void read(){
  scanf("%d%d%d", &N, &K, &Q);
  for(int i = 0; i < N + Q; i++){
    scanf("%d", &A[i]);
    use[A[i]] = 1;
  }
}

void init(){
  iota(phi, phi + MAXA, 0);
  for(int i = 1; i < MAXA; i++){
    for(int j = i; j < MAXA; j += i){
      if(i != j) phi[j] -= phi[i];
      if(use[j]) divisors[j].push_back(i);
    }
  }
  bin[K - 1] = 1;
  for(int i = K; i < MAXN; i++){
    bin[i] = bin[i - 1] * i % MOD * inv(i - K + 1, MOD) % MOD;
  }
}

int main(){
  read();
  init();
  for(int i = 0; i < N + Q; i++){
    for(int d : divisors[A[i]]){
      res = (res + bin[cnt[d]] * phi[d]) % MOD;
      cnt[d] += 1;
    }
    if(i >= N){
      printf("%dn", res);
    }
  }
}

645G - Armistice Area Apportionment

Idea: yummy

Thanks to jqdai0815 and Petr for sharing a solution with me that is much more intuitive than the one I originally had in mind! It works as follows:

First, let’s try to solve the smaller case where we only have two points. Let $\text{[math]}$ be the line passing through x_i and x_j. We want to compute the difference of $\text{[math]}$ relative to P and Q. Define P’ as the reflection of P over $\text{[math]}$ . By the triangle inequality, we have |PX - QX| = |P’X - QX| ≤ P’Q. Equality can be achieved when X, P’ and Q are collinear—that is, when X is the intersection of $\text{[math]}$ and line P’Q. (If $\text{[math]}$ and P’Q are parallel, we can imagine that they intersect at infinity.) Therefore, the difference of a line $\text{[math]}$ relative to P and Q is the distance from P’ to Q.

We can also think about P’ in a different way. Let C_i be the circle with center x_i that pases through P. Then P’ is the second intersection of the two circles C_i and C_j. Thus our problem of finding a line with minimum difference becomes equivalent to finding the intersection among {C_i} that lies closest to Q. This last part we can do with a binary search.

Consider the problem of checking if two circles C_i and C_j intersect at a point within a distance r of Q. In other words, we wish to check if they intersect inside a circle S of radius r centered at Q. Let A_i and A_j be the arcs of S contained by C_i and C_j, respectively. Observe that C_i and C_j intersect inside the circle if and only if the two arcs overlap, but do not contain each other. Thus we can verify this condition for all pairs of points with a radial sweep line along the circle. Due to the binary search and the sorting necessary for the sweep line, this solution runs in $\text{[math]}$ , where P is the precision required.

One might also wonder if precision will be an issue with all the calculations that we’re doing. It turns out that it won’t be, since our binary search will always stabilize the problem and get us very close to the answer.

Here’s my original solution using a projective transformation:

We begin by binary searching on the the minimum possible difference. Thus we wish to solve the decision problem "Can a difference of k be achieved?" Consider the hyperbola |PX - QX| = k. Note that our answer is affirmative if and only if a pair of outposts defines a line that does not intersect the hyperbola.

Our next step is a reduction to an equivalent decision problem on a circle through a projective transformation. We express this transformation as the composition of two simpler operations. The first is an affine map that takes the hyperbola |PX - QX| = k to the unit hyperbola. The second maps homogenous coordinates (x, y, z) to (z, y, x). Under the latter, the unit hyperbola x² - y² = z² goes to the unit circle x² + y² = z².

Because projective transformations preserve collinearity, a line intersecting the hyperbola is equivalent to a line intersecting the circle. Thus we want to know if any pair of the outposts' images defines a line that does not intersect the circle. We now map the image of each outpost to the minor arc on the unit circle defined by its tangents. (We disregard any points lying inside the circle.) Observe that our condition is equivalent to the existence of two intersecting arcs, neither of which contains the other. Verifying that two such arcs exist can be done with a priority queue and a radial sweep line in $\text{[math]}$ .

The total complexity of our solution is therefore $\text{[math]}$ , where P is the precision that we need. It turns out that the implementation of this algorithm is actually pretty neat:

Code

#include <bits/stdc++.h>
using namespace std;

typedef long double ld;

const ld EPS = 1e-12;
const ld PI = acos(-1);
const int MAXN = 100005;
int N;
ld A, X[MAXN], Y[MAXN];

bool check(ld m){
  ld u = m / 2;
  ld v = sqrt(A * A - u * u);
  vector<pair<ld,ld>> ev;
  for(int i = 0; i < N; i++){
    ld x = 1, y = Y[i] / v, alpha;
    if(X[i] != 0){
      x *= u / X[i], y *= u / X[i];
      ld r = sqrt(x * x + y * y);
      if(r < 1) continue;
      alpha = acos(1 / r);
    } else {
      alpha = PI / 2;
    }
    ld base = atan2(y, x) - alpha;
    if(base < 0) base += 2 * PI;
    ev.push_back({base, base + 2 * alpha});
  }
  priority_queue<ld, vector<ld>, greater<ld>> pq;
  sort(ev.begin(), ev.end());
  for(int i = 0; i < 2; i++){
    for(int j = 0; j < ev.size(); j++){
      while(pq.size() && pq.top() < ev[j].first) pq.pop();
      if(pq.size() && pq.top() < ev[j].second) return 1;
      pq.push(ev[j].second);
      ev[j].first += 2 * PI;
      ev[j].second += 2 * PI;
    }
  }
  return 0;
}

int main(){
  ios::sync_with_stdio(0);
  cin >> N >> A;
  for(int i = 0; i < N; i++){
    cin >> X[i] >> Y[i];
  }
  ld lo = 0, hi = 2 * A;
  while(hi - lo > EPS){
    ld mid = (lo + hi) / 2;
    (check(mid) ? hi : lo) = mid;
  }
  cout << fixed << setprecision(10);
  cout << (lo + hi) / 2 << 'n';
}

Full text and comments »