Both a participant and a contest organizer sometimes wants to stress test their solution with the brute force. Sometimes random tests are quite weak and one needs many thousands (and sometimes millions) of them to become sure about the correctness. The thing is that running a program is quite slow itself, what may hurt if the computation part is fast. On my laptop running a C++ program with empty main() one thousand times takes 1.3s, what doesn't satisfy me. How to make it faster?

I recently prepared a problem with a binary grid (SRM 699, div1-hard TwoSquares) and I wanted to be very careful about the correctness. I wrote slow solutions in C++ and the intended one in Java. Only then I realized how slow usual stress testing is. If they all were in one language, I would quite easily get everything into one program with classes (structs) and I would just run it once, without any overheads. But since the languages were different, I had to rewrite one solution, what not only requires time, but also is a possible place for a mistake.

Does running a program on Windows take the similar amount of time? Is it possible to run a program on Ubuntu or Windows faster than in a milisecond? Given two programs in C++, how to automatically merge them into one program and test them (this feature would be awesome in Polygon I think, where stress testing is able to process only thousands of tests too)?

Regarding my last question (automatically merging two programs) some idea is to wrap everything except includes into a struct and creating one global instance of such a struct. It should be automatically zero-ed (all global variables should be 0, as the user intended).

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

Struct P1 {
	int s, t[100000];
	int main() {
		int n;
		scanf("%d", &n);
		for(int i = 0; i < n; ++i) {
			scanf("%d", &t[i]);
			s += t[i];
		}
		printf("%d\n", s);
		return 0;
	}
} P1_global;

struct P2 {
	// something similar
} P2_global;

int main() {
	for(int rep = 0; rep < 1000; ++rep) {
		// generate the test and either print it to the file or put it to some stream
		auto p1 = P1_global;
		p1.main();
		auto p2 = P2_global;
		p2.main();
		// compare outputs
	}
}

The good thing is that the memory doesn't become huge if we process many tests (or does it?). But mnbvmar noticed that it won't work for static variables. Any way to make it work? Any other ideas?

Four participants will advance to the finals. Check the exact time.

EDIT: 15 minutes to the start.

Remember to register.

--- EDIT, the contest is over ---

BearBall, 250 points

There is a special case when all points are in one line. Otherwise, for any pair of bears the number of throws is 1 or 2.

So, for each points you should count how many points are directly reachable from this one. You achieve it by sorting other points. The complexity should be .

import java.util.Arrays;

public class BearBall {
	public int countThrows(int[] x, int[] y) {
		int n = x.length;
		int answer = 0;
		for(int i = 0; i < n; ++i) {
			// sort other points by angle
			Point[] p = new Point[n-1];
			int tmp = 0;
			for(int j = 0; j < n; ++j) if(i != j)
				p[tmp++] = new Point(x[j] - x[i], y[j] - y[i]);
			Arrays.sort(p);
			// check if all are collinear
			if(p[0].compareTo(p[n-2]) == 0) {
				answer = 0; // forget what was calculated so far
				for(int a = 0; a < n; ++a)
					for(int b = a + 1; b < n; ++b)
						answer += 2 * (b - a);
				return answer;
			}
			for(int j = 0; j < n - 1; ++j) {
				++answer; // the first point in this direction
				while(j + 1 < n - 1 && p[j].compareTo(p[j+1]) == 0) {
					answer += 2; // not the first point in this direction
					++j;
				}
			}
		}
		return answer;
	}
}

class Point implements Comparable<Point> {
	int x, y;
	Point(int _x, int _y) { x = _x; y = _y; }
	public int compareTo(Point other) {
		if(isRight() != other.isRight())
			return isRight() ? 1 : -1;
		return x * other.y - y * other.x;
	}
	void write() {
		System.out.println(x + " " + y);
	}
	boolean isRight() {
		return x > 0 || (x == 0 && y > 0);
	}
}

BearGridRect, 600 points

Hint: use flows, maybe mincost.

import java.util.*;

public class BearGridRect {
	int n, m;
	int row(int i) { return i; }
	int column(int i) { return n + i; }
	int query1(int i) { return 2 * n + i; }
	int query2(int i) { return 2 * n + m + i; }
	public int[] findPermutation(int tmp_n, int[] r1, int[] r2, int[] c1, int[] c2, int[] cnt) {
		n = tmp_n;
		m = r1.length;
		int s = 2 * n + 2 * m;
		int t = 2 * n + 2 * m + 1;
		int total = 2 * n + 2 * m + 2;
		MinCostMaxFlow f = new MinCostMaxFlow();
		f.init(total);
		
		boolean visited[][] = new boolean[n][n];
		int cnt_sum = 0;
		
		for(int i = 0; i < m; ++i) {
			cnt_sum += cnt[i];
			f.add(query1(i), query2(i), cnt[i], 0);
			for(int r = r1[i]; r <= r2[i]; ++r)
				for(int c = c1[i]; c <= c2[i]; ++c) {
					f.add(row(r), query1(i), 1, 0);
					f.add(query2(i), column(c), 1, 0);
					visited[r][c] = true;
				}
		}
		for(int r = 0; r < n; ++r)
			for(int c = 0; c < n; ++c)
				if(!visited[r][c])
					f.add(row(r), column(c), 1, 1);
		
		for(int r = 0; r < n; ++r)
			f.add(s, row(r), 1, 0);
		for(int c = 0; c < n; ++c)
			f.add(column(c), t, 1, 0);
		
		int[] ans = f.findFlow(s, t);
		int total_flow = ans[0];
		int total_cost = ans[1];
		if(total_flow != n || cnt_sum + total_cost != n) {
			int tmp[] = {-1};
			return tmp;
		}
		ans = new int[n];
		for(int r = 0; r < n; ++r) {
			for(int c = 0; c < n; ++c) {
				if(f.flow[row(r)][column(c)] > 0)
					ans[r] = c;
				for(int i = 0; i < m; ++i)
					if(f.flow[row(r)][query1(i)] > 0 && f.flow[query2(i)][column(c)] > 0) {
						ans[r] = c;
						f.flow[row(r)][query1(i)] = f.flow[query2(i)][column(c)] = 0;
					}
			}
		}
		return ans;
	}
}

class MinCostMaxFlow { // from http://web.mit.edu/~ecprice/acm/acm08/MinCostMaxFlow.java
	boolean found[];
	int N, cap[][], flow[][], cost[][], dad[], dist[], pi[];
	
	void init(int N) {
		this.N = N;
		cap = new int[N][N];
		cost = new int[N][N];
	}
	void add(int from, int to, int ca, int cos) {
		cap[from][to] = ca;
		cost[from][to] = cos;
	}
	
	static final int INF = Integer.MAX_VALUE / 2 - 1;
	
	boolean search(int source, int sink) {
		Arrays.fill(found, false);
		Arrays.fill(dist, INF);
		dist[source] = 0;

		while (source != N) {
			int best = N;
			found[source] = true;
			for (int k = 0; k < N; k++) {
				if (found[k]) continue;
				if (flow[k][source] != 0) {
					int val = dist[source] + pi[source] - pi[k] - cost[k][source];
					if (dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if (flow[source][k] < cap[source][k]) {
					int val = dist[source] + pi[source] - pi[k] + cost[source][k];
					if (dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if (dist[k] < dist[best]) best = k;
			}
			source = best;
		}
		for (int k = 0; k < N; k++)
			pi[k] = Math.min(pi[k] + dist[k], INF);
		return found[sink];
	}
	
	int[] findFlow(int source, int sink) {
		found = new boolean[N];
		flow = new int[N][N];
		dist = new int[N+1];
		dad = new int[N];
		pi = new int[N];
		
		int totflow = 0, totcost = 0;
		while (search(source, sink)) {
			int amt = INF;
			for (int x = sink; x != source; x = dad[x])
				amt = Math.min(amt, flow[x][dad[x]] != 0 ? flow[x][dad[x]] :
			cap[dad[x]][x] - flow[dad[x]][x]);
			for (int x = sink; x != source; x = dad[x]) {
				if (flow[x][dad[x]] != 0) {
					flow[x][dad[x]] -= amt;
					totcost -= amt * cost[x][dad[x]];
				} else {
					flow[dad[x]][x] += amt;
					totcost += amt * cost[dad[x]][x];
				}
			}
			totflow += amt;
		}
		return new int[]{ totflow, totcost };
	}
}

BearCircleGame, 800 points

Dynamic programming. Iterate over the number of remaining players, from n to 1. In each moment, you need an array of size with probabilities — for each number of bears what is the probability that Limak is this far from the starting bear. Then, for each bear we need probability that he loses and thus we will know the next array (for remaining - 1 remaining bears).

a loses with probability .

Try to first write O(n³) approach — find cycle in a sequence of indices a + 1 - k, a + 1 - 2k, a + 1 - 3k... and then over indices in the cycle sum up where c is the size of cycle and d says which place this index has in the cycle.

To make it faster, notice that the answer for a and for a + k will be similar. It's enough to multiply (or divide, whatever) by the sum by two, and then add one value.

public class BearCircleGame {
	int mod = 1000 * 1000 * 1000 + 7;
	int mul(int a, int b) {
		return (int) ((long) a * b % mod);
	}
	int my_pow(int a, int b) {
		int r = 1;
		while(b > 0) {
			if(b % 2 == 1) r = (int) ((long) r * a % mod);
			a = (int) ((long) a * a % mod);
			b /= 2;
		}
		return r;
	}
	int inv(int a) { return my_pow(a, mod - 2); }
	
	public int winProbability(int n, int k) {
		int dp[] = new int[n];
		dp[0] = 1; // probability that Limak starts
		for(int remaining = n; remaining >= 2; --remaining) {
			int old[] = dp;
			dp = new int[remaining - 1];
			boolean vis[] = new boolean[remaining];
			for(int starting = 0; starting < remaining; ++starting) if(!vis[starting]) {
				int p = 0;
				int x = starting;
				int div = 1;
				int cycle_size = 0;
				do {
					vis[x] = true;
					++cycle_size;
					div = mul(div, inv(2));
					p = (p + mul(old[x], div)) % mod;
					x = ((x - k) % remaining + remaining) % remaining;
				} while(x != starting);
				
				int power_two = 1;
				for(int i = 0; i < cycle_size; ++i)
					power_two = 2 * power_two % mod;
				if(power_two == 1) {
					System.out.println("assert inv(0)");
					return -1;
				}
				// multiply by 2^c/(2^c-1) (because it's geometric  series)
				int mul_by = mul(power_two, inv(power_two - 1));
				
				do {
					int dead = (x + k - 1) % remaining;
					if(dead != 0) {
						int nxt = (dead == remaining-1) ? 0 : dead;
						dp[nxt] = mul(p, mul_by);
					}
					p = (p - mul(old[x], inv(2)) + mod) % mod;
					p = 2 * p % mod;
					p = (p + mul(old[x], div)) % mod; // div == inv(2)^c
					x = ((x - k) % remaining + remaining) % remaining;
				} while(x != starting);
			}
		}
		return dp[0];
	}
}

WINNERS

1. liymsheep, who solved all three problems
2. ACRush
3. kriii

And congratulations to Petr for solving all problems and thus winning the parallel round.

680A - Bear and Five Cards

Iterate over all pairs and triples of numbers, and for each of them check if all two/three numbers are equal. If yes then consider the sum of remaining numbers as the answer (the final answer will be the minimum of considered sums). Below you can see two ways to implement the solution.

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t[5];
	int s = 0;
	for(int i = 0; i < 5; ++i) {
		scanf("%d", &t[i]);
		s += t[i];
	}
	int best = s;
	
	// discard 2 cards
	for(int a = 0; a < 5; ++a)
		for(int b = a + 1; b < 5; ++b)
			if(t[a] == t[b])
				best = min(best, s - 2 * t[a]);
	
	// or discard 3 cards
	for(int a = 0; a < 5; ++a)
		for(int b = a + 1; b < 5; ++b)
			for(int c = b + 1; c < 5; ++c)
				if(t[a] == t[b] && t[a] == t[c])
					best = min(best, s - 3 * t[a]);
	
	printf("%d\n", best);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t[5];
	for(int i = 0; i < 5; ++i)
		scanf("%d", &t[i]);
	sort(t, t + 5);
	int best_remove = 0;
	for(int i = 0; i < 5; ++i) {
		if(i + 1 < 5 && t[i] == t[i+1])
			best_remove = max(best_remove, 2 * t[i]);
		if(i + 2 < 5 && t[i] == t[i+2])
			best_remove = max(best_remove, 3 * t[i]);
	}
	printf("%dn", t[0]+t[1]+t[2]+t[3]+t[4]-best_remove);
	return 0;
}

680B - Bear and Finding Criminals

Limak can't catch a criminal only if there are two cities at the same distance and only one of them contains a criminal. You should iterate over the distance and for each distance d check if a - d and a + d are both in range [1, n] and if only one of them has t_i = 1.

#include<bits/stdc++.h>
using namespace std;
const int nax = 1005;
int t[nax];
int main() {
	int n, a;
	scanf("%d%d", &n, &a);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &t[i]);
	int answer = 0;
	for(int i = 1; i <= n; ++i) if(t[i]) {
		// can we catch criminal in city i?
		int distance = i - a; // distance from a
		int j = a - distance; // the other city at the same distance
		if(j < 1 || j > n || t[i] == t[j])
			++answer;
	}
	printf("%dn", answer);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int nax = 1005;
int t[nax];
bool impossible[nax];
int main() {
	int n, a;
	scanf("%d%d", &n, &a);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &t[i]);
	for(int i = 1; i <= n; ++i)
		for(int j = i + 1; j <= n; ++j)
			if(abs(i - a) == abs(j - a) && t[i] != t[j]) {
				// i and j have the same distance to a
				// also, there is a criminal in exactly one of them
				impossible[i] = impossible[j] = true;
			}
	int answer = 0;
	for(int i = 1; i <= n; ++i)
		if(t[i] == 1 && !impossible[i])
			++answer;
	printf("%dn", answer);
	return 0;
}

679A - Bear and Prime 100

If a number is composite then it's either divisible by p² for some prime p, or divisible by two distinct primes p and q. To check the first condition, it's enough to check all possible p² (so, numbers 4, 9, 25, 49). If at least one gives "yes" then the hidden number if composite.

If there are two distinct prime divisors p and q then both of them are at most 50 — otherwise the hidden number would be bigger than 100 (because for p ≥ 2 and q > 50 we would get p·q > 100). So, it's enough to check primes up to 50 (there are 15 of them), and check if at least two of them are divisors.

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

bool isPrime(int a) {
	for(int i = 2; i * i <= a; ++i)
		if(a % i == 0)
			return false;
	return true;
}

bool divisible(int a) {
	printf("%dn", a);
	fflush(stdout);
	char sl[10];
	scanf("%s", sl);
	return sl[0] == 'y' || sl[0] == 'Y';
}

int HIGH = 100;

int main() {
	int counter = 0; // we print "composite" if counter >= 2
	for(int a = 2; a <= HIGH/2 && counter < 2; ++a)
		if(isPrime(a))
			if(divisible(a)) {
				++counter;
				if(a * a <= HIGH && divisible(a * a))
					++counter;
			}
	puts(counter >= 2 ? "composite" : "prime");
	return 0;
}

from sys import stdout

PRIMES = [x for x in range(2,100) if 0 not in [x%i for i in range(2,x)]]

NORMAL = PRIMES[:15]
SQUARES = [x*x for x in PRIMES[:4]]

for ele in SQUARES:
    print(ele)
    stdout.flush()
    x = input()
    if x == "yes":
        print("composite")
        exit(0)

yes = 0
for ele in NORMAL:
    print(ele)
    stdout.flush()
    x = input()
    if x == "yes":
        yes += 1

print("prime" if yes < 2 else "composite")

679B - Bear and Tower of Cubes

Let's find the maximum a that a³ ≤ m. Then, it's optimal to choose X that the first block will have side a or a - 1. Let's see why.

• If the first block has side a then we are left with m₂ = m - first_block = m - a³.
• If the first block has side a - 1 then the initial X must be at most a³ - 1 (because otherwise we would take a block with side a), so we are left with m₂ = a³ - 1 - first_block = a³ - 1 - (a - 1)³
• If the first blocks has side a - 2 then the initial X must be at most (a - 1)³ - 1, so we are left with m₂ = (a - 1)³ - 1 - first_block = (a - 1)³ - 1 - (a - 2)³.

We want to first maximize the number of blocks we can get with new limit m₂. Secondarily, we want to have the biggest initial X. You can analyze the described above cases and see that the first block with side (a - 2)³ must be a worse choice than (a - 1)³. It's because we start with smaller X and we are left with smaller m₂. The situation for even smaller side of the first block would be even worse.

Now, you can notice that the answer will be small. From m of magnitude a³ after one block we get m₂ of magnitude a². So, from m we go to m^2 / 3, which means that the answer is O(loglog(m)). The exact maximum answer turns out to be 18.

The intended solution is to use the recursion and brutally check both cases: taking a³ and taking (a - 1)³ where a is maximum that a³ ≤ m. It's so fast that you can even find a in O(m^1 / 3), increasing a by one.

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

pair<ll,ll> best;

ll my_pow(ll x) { return x * x * x; }

void rec(ll m, ll steps, ll subtracted) {
	if(m == 0) {
		best = max(best, make_pair(steps, subtracted));
		return;
	}
	ll x = 1;
	while(my_pow(x+1) <= m) ++x;
	rec(m - my_pow(x), steps+1, subtracted + my_pow(x));
	if(x - 1 >= 0)
		rec(my_pow(x)-1-my_pow(x-1), steps+1, subtracted + my_pow(x-1));
}

int main() {
	ll m;
	scanf("%lld", &m);
	rec(m, 0, 0);
	printf("%lld %lldn", best.first, best.second);
	return 0;
}

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

ll my_pow(ll x) { return x * x * x; }

ll steps(ll m) { // works in O(m^(1/3))
	if(m <= 7) return m;
	ll x = 1;
	while(my_pow(x+1) <= m) ++x;
	return 1 + steps(max(m - my_pow(x), my_pow(x)-1-my_pow(x-1)));
}

int main() {
	ll m;
	scanf("%lld", &m);
	ll subtracted = 0, steps_so_far = 0;
	while(m) {
		++steps_so_far;
		ll x = 1;
		while(my_pow(x+1) <= m) ++x;
		if(steps(m) == 1 + steps(m - my_pow(x))) {
			m -= my_pow(x);
			subtracted += my_pow(x);
		}
		else {
			m = my_pow(x) - 1 - my_pow(x-1);
			subtracted += my_pow(x-1);
		}
	}
	printf("%lld %lldn", steps_so_far, subtracted);
	return 0;
}

#include "bits/stdc++.h"

using namespace std;

#define ll long long

vector <ll> X;
map <ll, pair <int, ll> > M;

pair <int, ll> go(ll x)
{
  if(x <= 1)
    return {x,x};
  if(M.find(x) != M.end())
    return M[x];
  int i = upper_bound(X.begin(), X.end(), x) - X.begin() - 1;
  int p1, p2;
  long long q1, q2;
  tie(p1, q1) = go(x - X[i]);
  tie(p2, q2) = go(X[i] - 1);
  return M[x] =  max(make_pair(p1+1, q1+X[i]), {p2, q2});
}

int main()
{
  for(int i=0; i<=1e5+7; i++)
    X.push_back(1LL*i*i*i);
  ll x;
  cin >> x;
  int a;
  long long b;
  tie(a,b) = go(x);
  cout << a << " " << b << "n";
}

679C - Bear and Square Grid

Let's first find CC's (connected components) in the given grid, using DFS's.

We will consider every possible placement of a k × k square. When the placement is fixed then the answer is equal to the sum of k² the the sum of sizes of CC's touching borders of the square (touching from outside), but for those CC's we should only count their cells that are outside of the square — not to count something twice. We will move a square, and at the same time for each CC we will keep the number of its cells outside the square.

We will used a sliding-window technique. Let's fix row of the grid — the upper row of the square. Then, we will first place the square on the left, and then we will slowly move a square to the right. As we move a square, we should iterate over cells that stop or start to belong to the square. For each such empty cell we should add or subtract 1 from the size of its CC (ids and sizes of CC's were found at the beginning).

And for each placement we consider, we should iterate over outside borders of the square (4k cells — left, up, right and down side) and sum up sizes of CC's touching our square. Be careful to not count some CC twice — you can e.g. keep an array of booleans and mark visited CC's. After checking all 4k cells you should clear an array, but you can't do it in O(number_of_all_components) because it would be too slow. You can e.g. also add visited CC's to some vector, and later in the boolean array clear only CC's from the vector (and then clear vector).

The complexity is O(n²·k).

#include<bits/stdc++.h>
using namespace std;
const int nax = 505;
int n;
char grid[nax][nax]; // input
int cc[nax][nax]; // id of CC in which this cell is
int cc_size[nax*nax]; // size of CC
int when_added[nax*nax];

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const char EMPTY = '.';

bool inside(int x, int y) {
	return 0 <= min(x, y) && max(x, y) < n;
}

void dfs(int x, int y, int which_cc) {
	cc[x][y] = which_cc;
	++cc_size[which_cc];
	for(int i = 0; i < 4; ++i) { // iterate of 4 adjacent cells
		int x2 = x + dx[i];
		int y2 = y + dy[i];
		if(inside(x2, y2) && grid[x2][y2] == EMPTY && cc[x2][y2] == 0)
			dfs(x2, y2, which_cc);
	}
}

void add(int x, int y, int & answer, int current_time) {
	if(inside(x, y) && grid[x][y] == EMPTY) {
		int id = cc[x][y];
		if(when_added[id] != current_time) {
			when_added[id] = current_time;
			answer += cc_size[id];
		}
	}
}

int main() {
	int k;
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; ++i)
		scanf("%s", grid[i]);
	
	// run DFS many times to find CC's (connected components)
	int how_many_cc = 0;
	for(int x = 0; x < n; ++x)
		for(int y = 0; y < n; ++y)
			if(grid[x][y] == EMPTY && cc[x][y] == 0)
				dfs(x, y, ++how_many_cc);
	
	int cur_time = 1;
	int best_answer = 0;
	
	for(int y_low = 0; y_low + k <= n; ++y_low) {
		// first we put a square with corner in (0, y_low)
		for(int x = 0; x < k; ++x)
			for(int y = y_low; y < y_low + k; ++y)
				--cc_size[cc[x][y]]; // subtract cells inside a square
		
		for(int x_low = 0; x_low  + k <= n; ++x_low) {
			int answer = k * k; // all cells inside a square
			// consider one row: below, above, left, right
			for(int x = x_low; x < x_low + k; ++x) {
				add(x, y_low - 1, answer, cur_time);
				add(x, y_low + k, answer, cur_time);
			}
			for(int y = y_low; y < y_low + k; ++y) {
				add(x_low - 1, y, answer, cur_time);
				add(x_low + k, y, answer, cur_time);
			}
			++cur_time;
			best_answer = max(best_answer, answer);
			
			if(x_low + k != n) {
				// move a square to increase x_low by 1
				for(int y = y_low; y < y_low + k; ++y) {
					++cc_size[cc[x_low][y]]; // remove cells with x = x_low
					--cc_size[cc[x_low+k][y]]; // insert cells with x = x_low+k
				}
			}
		}
		
		for(int x = n - k; x < n; ++x)
			for(int y = y_low; y < y_low + k; ++y)
				++cc_size[cc[x][y]]; // we don't need cells inside to be subtracted
	}
	printf("%dn", best_answer);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 500 + 5;
const int nax2 = nax * nax;

int n,k;

int ile_na_zew, akt_stan = 1;

char t[nax][nax];
int ojc[nax][nax];
int ilosc[nax2], lewo[nax2], prawo[nax2], gora[nax2], dol[nax2];
int suma[nax][nax], kol[nax], stan[nax2];
bool bylo[nax][nax];

vector<pair<pii, int> > wiersz[nax];

int ruchi[] = {-1, 0, 1, 0};
int ruchj[] = {0, -1, 0, 1};

void dfs(int i, int j, int wsk) {
  ilosc[wsk]++;
  ojc[i][j] = wsk;
  bylo[i][j] = true;
  lewo[wsk] =  min(lewo[wsk], j);
  prawo[wsk] = max(prawo[wsk], j);
  gora[wsk] =  min(gora[wsk], i);
  dol[wsk] =   max(dol[wsk], i);  
  
  REP(g,4) {
    int ni = i + ruchi[g];
    int nj = j + ruchj[g];
    
    if (t[ni][nj] == '.' && bylo[ni][nj] == false)
      dfs(ni,nj,wsk);
  }
}

void check(int o) {
  if (stan[o] != akt_stan)
    ile_na_zew += ilosc[o];
  stan[o] = akt_stan;  
}

int main() {	
  scanf("%d%d",&n,&k);
  FOR(i,1,n) scanf(" %s",t[i]+1);
  
  int wsk = 1;
  FOR(i,1,n) FOR(j,1,n) if (t[i][j] == '.' && !bylo[i][j]) {
    lewo[wsk] = prawo[wsk] = j;
    gora[wsk] = dol[wsk] = i;
    dfs(i,j,wsk);
    //printf("%dn",ilosc[wsk]);
    if (prawo[wsk] - lewo[wsk] + 1 <= k && dol[wsk] - gora[wsk] + 1 <= k) {
      //puts("DD");
      int x = max(1, dol[wsk] - k + 1);
      wiersz[x].pb(mp(mp(lewo[wsk], prawo[wsk]), ilosc[wsk]));
      wiersz[gora[wsk]+1].pb(mp(mp(lewo[wsk], prawo[wsk]), -ilosc[wsk]));
    }
    ++wsk;
  }
  
  FOR(i,1,n) FOR(j,1,n) suma[i][j] = suma[i-1][j] + suma[i][j-1] - suma[i-1][j-1] + (t[i][j] == '.');
  //FOR(i,1,n) FOR(j,1,n) printf("(%d,%d): %dn",i,j,suma[i][j]);
  
  int res = 0;
  FOR(i,1,n-k+1) {
    for (auto p: wiersz[i]) {
      int l = max(1, p.st.nd - k + 1);
      //printf("%d %d %dn",l,p.st.st,p.nd);
      kol[l] += p.nd;
      kol[p.st.st + 1] -= p.nd;
    }
    
    int suma_s = 0;
    FOR(j,1,n-k+1) {
      suma_s += kol[j];
      int ile_w_s = suma[i+k-1][j+k-1] - suma[i-1][j+k-1] - suma[i+k-1][j-1] + suma[i-1][j-1];
      ile_na_zew = 0;
      REP(g,k) {
        check(ojc[i-1][j+g]);
        check(ojc[i+k][j+g]);
        check(ojc[i+g][j-1]);
        check(ojc[i+g][j+k]);
      }
      
      int x = ile_na_zew + (k * k  - ile_w_s) + suma_s;
      //printf("(%d,%d) : %d %d %d %dn",i,j,ile_na_zew, ile_w_s, suma_s, x);
      
      res = max(res, x);
      ++akt_stan;
    }
  }
  printf("%dn",res);
	return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AlexFetisov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE_356 solver = new TaskE_356();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE_356 {
        int n;
        int k;
        boolean[][] f;
        List<Integer> componentCellCount;
        int[][] color;
        int x = 0;
        int y = 0;
        int totalEmpty = 0;
        int sumInComponents = 0;
        int[] amInComponents;
        int[] flag;
        int currentFlagColor = 0;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            k = in.nextInt();
            f = new boolean[n][n];
            color = new int[n][n];
            ArrayUtils.fill(color, -1);
            for (int i = 0; i < n; ++i) {
                char[] c = in.nextString().toCharArray();
                for (int j = 0; j < n; ++j) {
                    f[i][j] = (c[j] == '.');
                }
            }

            // Caclulate all CC
            int res = 0;
            componentCellCount = new ArrayList<Integer>();
            int currentComponentId = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (color[i][j] == -1) {
                        int count = dfs(i, j, currentComponentId++);
                        componentCellCount.add(count);
                        res = Math.max(res, count);
                    }
                }
            }

            flag = new int[currentComponentId];
            amInComponents = new int[currentComponentId];
            // Preprocess first square
            for (int i = 0; i < k; ++i) {
                for (int j = 0; j < k; ++j) {
                    addCell(i, j);
                }
            }

            res = Math.max(res, checkResult());

            for (int i = 0; i <= n - k; ++i) {
                int delta = i % 2 == 0 ? 1 : -1;
                for (int j = 0; j < n - k; ++j) {
                    moveSquare(0, x, y, x, y + delta);
                    y += delta;
                    res = Math.max(res, checkResult());
                }
                if (i != n - k) {
                    moveSquare(1, x, y, x + 1, y);
                    ++x;
                    res = Math.max(res, checkResult());
                }
            }
            out.println(res);
        }

        void moveSquare(int type, int cx, int cy, int nx, int ny) {
            if (type == 0) {
                if (ny < cy) {
                    for (int i = 0; i < k; ++i) {
                        removeCell(cx + i, cy + k - 1);
                        addCell(cx + i, ny);
                    }
                } else {
                    for (int i = 0; i < k; ++i) {
                        removeCell(cx + i, cy);
                        addCell(cx + i, ny + k - 1);
                    }
                }
            } else {
                for (int i = 0; i < k; ++i) {
                    removeCell(cx, cy + i);
                    addCell(nx + k - 1, cy + i);
                }
            }
        }

        void removeCell(int cx, int cy) {
            if (f[cx][cy]) {
                --totalEmpty;
                amInComponents[color[cx][cy]]--;
                if (amInComponents[color[cx][cy]] == 0) {
                    sumInComponents -= componentCellCount.get(color[cx][cy]);
                }
            }
        }

        void addCell(int cx, int cy) {
            if (f[cx][cy]) {
                ++totalEmpty;
                amInComponents[color[cx][cy]]++;
                if (amInComponents[color[cx][cy]] == 1) {
                    sumInComponents += componentCellCount.get(color[cx][cy]);
                }
            }
        }

        int dfs(int cx, int cy, int cId) {
            if (cx < 0 || cx >= n || cy < 0 || cy >= n) return 0;
            if (color[cx][cy] != -1) return 0;
            if (!f[cx][cy]) return 0;
            color[cx][cy] = cId;
            int am = 1;
            am += dfs(cx - 1, cy, cId);
            am += dfs(cx + 1, cy, cId);
            am += dfs(cx, cy - 1, cId);
            am += dfs(cx, cy + 1, cId);
            return am;
        }

        int checkResult() {
            ++currentFlagColor;
            int res = k * k - totalEmpty + sumInComponents;
            for (int i = 0; i < k; ++i) {
                res += checkCell(x - 1, y + i);
                res += checkCell(x + k, y + i);
                res += checkCell(x + i, y - 1);
                res += checkCell(x + i, y + k);
            }
            return res;
        }

        int checkCell(int cx, int cy) {
            if (cx < 0 || cx >= n || cy < 0 || cy >= n) return 0;
            if (!f[cx][cy]) return 0;
            if (amInComponents[color[cx][cy]] > 0) return 0;
            if (flag[color[cx][cy]] == currentFlagColor) return 0;
            flag[color[cx][cy]] = currentFlagColor;
            return componentCellCount.get(color[cx][cy]);
        }

    }

    static class ArrayUtils {
        public static void fill(int[][] f, int value) {
            for (int i = 0; i < f.length; ++i) {
                Arrays.fill(f[i], value);
            }
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String nextString() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }
}

679D - Bear and Chase

Check my code below, because it has a lot of comments.

First, in O(n³) or faster find all distances between pairs of cities.

Iterate over all g1 — the first city in which you use the BCD. Then, for iterate over all d1 — the distance you get. Now, for all cities calculate the probability that Limak will be there in the second day (details in my code below). Also, in a vector interesting let's store all cities that are at distance d1 from city g1.

Then, iterate over all g2 — the second city in which you use the BCD. For cities from interesting, we want to iterate over them and for each distinct distance from g2 to choose the biggest probability (because we will make the best guess there is).

Magic: the described approach has four loops (one in the other) but it's O(n³).

Proof is very nice and I encourage you to try to get it yourself.

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
typedef double T;
const int nax = 1005;
int dist[nax][nax];
vector<int> w[nax];
T p_later[nax]; // p[v] - probability for city v in the second day
T p_dist_max[nax];
bool vis[nax];

void max_self(T & a, T b) {
	a = max(a, b);
}

T consider_tomorrow(int n, int g1, int dist1) {
	T best_tomorrow = 0;
	// we need complexity O(n * x)
	// where x denotes the number of v that |dist1-dist[g1][v]| <= 1
	for(int i = 1; i <= n; ++i) {
		p_later[i] = 0;
		vis[i] = false;
	}
	vector<int> interesting;
	for(int v = 1; v <= n; ++v) if(dist[g1][v] == dist1)
		for(int b : w[v]) {
			// Limak started in v with prob. 1/n
			// he then moved to b with prob. 1/degree[v]
			p_later[b] += (T) 1 / n / w[v].size();
			if(!vis[b]) {
				vis[b] = true;
				interesting.push_back(b);
			}
		}
	
	// interesting.size() <= x, where x is defined above (needed for complexity)
	for(int g2 = 1; g2 <= n; ++g2) {
		T local_sum = 0; // over situations with fixed g1, dist1, g2
		
		for(int b : interesting)
			max_self(p_dist_max[dist[g2][b]], p_later[b]);
		for(int b : interesting) {
			local_sum += p_dist_max[dist[g2][b]];
			p_dist_max[dist[g2][b]] = 0; // so it won't be calculated twice
		}
		max_self(best_tomorrow, local_sum);
	}
	return best_tomorrow;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	FOR(i,1,n) FOR(j, 1, n) if(i != j)
		dist[i][j] = n + 1; // infinity
	FOR(i,1,m) {
		int a, b;
		scanf("%d%d", &a, &b);
		w[a].push_back(b);
		w[b].push_back(a);
		dist[a][b] = dist[b][a] = 1;
	}
	// Floyd-Warshall
	FOR(b,1,n)FOR(a,1,n)FOR(c,1,n)
		dist[a][c] = min(dist[a][c], dist[a][b] + dist[b][c]);
	
	// g1 is the first guess
	T answer = 0;
	FOR(g1, 1, n) {
		T sum_over_dist1 = 0;
		FOR(dist1, 0, n) {
			int cnt_cities = 0;
			FOR(i, 1, n) if(dist[g1][i] == dist1)
				++cnt_cities;
			if(cnt_cities == 0) continue; // there are no cities within distance dist1
			
			// 1) consider guessing immediately
			T immediately = (T) 1 / n; // how much it counts towards the answer
			// 2) consider waiting for tomorrow
			T second_day = consider_tomorrow(n, g1, dist1);
			sum_over_dist1 += max(immediately, second_day);
		}
		max_self(answer, sum_over_dist1);
	}
	printf("%.12lfn", (double) answer);
	return 0;
}

679E - Bear and Bad Powers of 42

The only special thing in numbers 1, 42, ... was that there are only few such numbers (in the possible to achieve range, so up to about 10¹⁴).

Let's first solve the problem without queries "in the interval change all numbers to x". Then, we can make a tree with operations (possible with lazy propagation):

• add on the interval
• find minimum in the whole tree

In a tree for each index let's keep the distance to the next power of 42. After each "add on the interval" we should find the minimum and check if it's positive. If not then we should change value of the closest power of 42 for this index, and change the value in the tree. Then, we should again find the minimum in the tree, and so on. The amortized complexity is O((n + q) * log(n) * log₄₂(values)). It can be proved that numbers won't exceed (n + q) * 1e9 * log.

Now let's think about the remaining operation of changing all interval to some value. We can set only one number (the last one) to the given value, and set other values to INF. We want to guarantee that if t[i] ≠ t[i + 1] then the i-th value is correctly represented in the tree. Otherwise, it can be INF instead (or sometimes it may be correctly represented, it doesn't bother me). When we have the old query of type "add something to interval [a, b]" then if index a - 1 or index b contains INF in the tree then we should first retrieve the true value there. You can see that each operation changes O(1) values from INF to something finite. So, the amortized complexity is still O((n + q) * log(n) * log₄₂(values).

One thing regarding implementation. In my solution there is "set < int > interesting" containing indices with INF value. I think it's easier to implemement the solution with this set.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e6 + 5;
const int pot = 256 * 1024;
const ll INF = 3e18L;
ll cur_power[nax]; // the least power of 42 larger than the current value
// true_value + remaining = cur_power,  where remaining=tr[pot+i]

struct Node {
	ll local;
	ll lazy;
	ll smallest() { return local + lazy; } // smallest value in this subtree
} tr[2*pot];

void propagate(int i) {
	assert(i < pot);
	tr[2*i].lazy += tr[i].lazy;
	tr[2*i+1].lazy += tr[i].lazy;
	tr[i].local += tr[i].lazy;
	tr[i].lazy = 0;
}
void act(int i) {
	assert(i < pot);
	assert(tr[i].lazy == 0);
	tr[i].local = min(tr[2*i].smallest(), tr[2*i+1].smallest());
}

void change(int i, int low, int high, int q_low, int q_high, ll val) {
	if(q_low <= low && high <= q_high) {
		tr[i].lazy += val;
		return;
	}
	propagate(i);
	int mid1 = (low + high) / 2;
	if(q_low <= mid1)
		change(2*i, low, mid1, q_low, q_high, val);
	if(q_high >= mid1+1)
		change(2*i+1, mid1+1, high, q_low, q_high, val);
	act(i);
}
void change(int q_low, int q_high, ll val) {
	change(1, 0, pot - 1, q_low, q_high, val);
}

int where_smallest(int i = 1) {
	if(i >= pot) return i - pot;
	propagate(i);
	int ret;
	if(tr[2*i].smallest() < tr[2*i+1].smallest())
		ret = where_smallest(2*i);
	else
		ret = where_smallest(2*i+1);
	act(i);
	return ret;
}

ll move_power(int i, ll rem) {
	assert(rem <= 0);
	while(rem < 0) {
		ll cur_value = cur_power[i] - rem;
		cur_power[i] *= 42;
		rem = cur_power[i] - cur_value;
	}
	return rem;
}

set<int> interesting; // the set of indices i that t[i] != t[i+1] (and maybe few others)
// all other indices have value INF in the tree

ll get_value(int i) {
	assert(interesting.count(i));
	vector<int> w;
	for(int x = (pot + i) / 2; x >= 1; x /= 2)
		w.push_back(x);
	reverse(w.begin(), w.end());
	for(int x : w) propagate(x); // top-down
	return tr[pot+i].smallest();
}

const int SET_TYPE = 10042;
const int INC_TYPE = 10043;
void set_or_inc(int i, ll val, const int type) {
	vector<int> w;
	for(int x = (pot + i) / 2; x >= 1; x /= 2)
		w.push_back(x);
	reverse(w.begin(), w.end());
	for(int x : w) propagate(x); // top-down
	if(type == SET_TYPE) {
		tr[pot+i].lazy = 0;
		tr[pot+i].local = val;
	}
	else if(type == INC_TYPE) {
		tr[pot+i].local += val;
	}
	else assert(false);
	reverse(w.begin(), w.end());
	for(int x : w) act(x); // bottom-up
}

void re_insert(int i) {
	int j = *interesting.lower_bound(i);
	if(i == j) return;
	cur_power[i] = cur_power[j];
	set_or_inc(i, get_value(j), SET_TYPE);
	interesting.insert(i);
}

void init_value(int i, int val) {
	cur_power[i] = 1;
	ll how_much_remains = 1 - val; // how much remains to cur_power[i]
	ll rem = move_power(i, how_much_remains);
	set_or_inc(i, rem, SET_TYPE);
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	for(int i = 0; i < 2 * pot; ++i)
		tr[i].local = INF;
	for(int i = 1; i <= n; ++i) {
		interesting.insert(i); // we don't mind that maybe t[i] = t[i+1]
		int val;
		scanf("%d", &val);
		init_value(i, val);
	}
	// queries
	while(q--) {
		int type;
		scanf("%d", &type);
		if(type == 1) { // print value
			int i;
			scanf("%d", &i);
			i = *interesting.lower_bound(i);
			printf("%lldn", cur_power[i] - get_value(i));
		}
		else if(type == 2) { // set interval to x
			int low, high, val;
			scanf("%d%d%d", &low, &high, &val);
			// t[low] = t[low+1] = ... = t[high-1] = INF
			// t[high] = val
			if(low - 1 >= 1)
				re_insert(low - 1);
			interesting.insert(high);
			init_value(high, val);
			while(true) {
				auto it = interesting.lower_bound(low);
				assert(it != interesting.end());
				int i = *it;
				assert(i <= high);
				if(i == high) break; // we only want [low, high-1]
				interesting.erase(it);
				set_or_inc(i, INF, SET_TYPE);
			}
		}
		else { // increase by x
			assert(type == 3);
			int low, high, val;
			scanf("%d%d%d", &low, &high, &val);
			if(low - 1 >= 1)
				re_insert(low - 1);
			re_insert(high);
			bool ok = false;
			while(!ok) {
				ok = true;
				change(low, high, -val);
				while(true) {
					int i = where_smallest();
					ll rem = tr[pot+i].smallest();
					assert(1 <= i && i <= n);
					if(rem > 0) break;
					if(rem == 0) {
						ok = false;
						break;
					}
					ll new_rem = move_power(i, rem);
					set_or_inc(i, new_rem, SET_TYPE);
				}
			}
		}
	}
	return 0;
}

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

int n, q;

vector <long long> poty;

int n1;

long long inf=(long long)1000000000*1000000000;

long long narz[1000007];
int czybom[1000007];
long long bom[1000007];

long long maxd[1000007];
long long mind[1000007];
long long zos[1000007];

int typ, p1, p2, p3;

inline int potenga(int v)
{
    for (int i=1; 1; i<<=1)
    {
        if (i>=v)
        {
            return i;
        }
    }
}

inline long long wie(long long v)
{
    return poty[lower_bound(poty.begin(), poty.end(), v)-poty.begin()];
}

inline long long brak(long long v)
{
    return wie(v)-v;
}

inline void pusz(int v)
{
    if (v>=n1)
    {
        czybom[v]=1;
        bom[v]+=narz[v];
        narz[v]=0;
        maxd[v]=bom[v];
        mind[v]=bom[v];
        zos[v]=brak(bom[v]);
        return;
    }
    int cel1, cel2;
    cel1=(v<<1);
    cel2=(cel1^1);
    if (czybom[v])
    {
        czybom[cel1]=1;
        bom[cel1]=bom[v];
        narz[cel1]=0;

        czybom[cel2]=1;
        bom[cel2]=bom[v];
        narz[cel2]=0;

        czybom[v]=0;
        bom[v]=0;
    }
    narz[cel1]+=narz[v];
    narz[cel2]+=narz[v];
    narz[v]=0;

    mind[v]=inf;
    maxd[v]=-inf;
    zos[v]=inf;

    for (int h=0; h<2; h++)
    {

        if (czybom[cel1])
        {
            bom[cel1]+=narz[cel1];
            narz[cel1]=0;
            maxd[v]=max(maxd[v], bom[cel1]);
            mind[v]=min(mind[v], bom[cel1]);
            zos[v]=min(zos[v], brak(bom[cel1]));
        }
        else
        {
            maxd[v]=max(maxd[v], maxd[cel1]+narz[cel1]);
            mind[v]=min(mind[v], mind[cel1]+narz[cel1]);
            zos[v]=min(zos[v], zos[cel1]-narz[cel1]);
        }

        swap(cel1, cel2);
    }
}

void dod(int v, int a, int b, int graa, int grab, long long w)
{
    if (a>=graa && b<=grab)
    {
        narz[v]+=w;
        return;
    }
    if (a>grab || b<graa)
    {
        return;
    }
    pusz(v);
    dod((v<<1), a, (a+b)>>1, graa, grab, w);
    dod((v<<1)^1, (a+b+2)>>1, b, graa, grab, w);
    pusz(v);
}

void zmi(int v, int a, int b, int graa, int grab, long long w)
{
    if (a>=graa && b<=grab)
    {
        narz[v]=0;
        czybom[v]=1;
        bom[v]=w;
        return;
    }
    if (a>grab || b<graa)
    {
        return;
    }
    pusz(v);
    zmi((v<<1), a, (a+b)>>1, graa, grab, w);
    zmi((v<<1)^1, (a+b+2)>>1, b, graa, grab, w);
    pusz(v);
}

void popr(int v)
{
    pusz(v);
    if (zos[v]>=0)
    {
        return;
    }
    if (mind[v]==maxd[v])
    {
        czybom[v]=1;
        bom[v]=mind[v];
        narz[v]=0;
        pusz(v);
        return;
    }
    popr((v<<1));
    popr((v<<1)^1);
    pusz(v);
}

long long wyn;

void czyt(int v, int a, int b, int cel)
{
    if (a>cel || b<cel)
    return;
    pusz(v);
    if (a==b)
    {
        wyn=bom[v];
        return;
    }
    czyt((v<<1), a, (a+b)>>1, cel);
    czyt((v<<1)^1, (a+b+2)>>1, b, cel);
}

int main()
{
    scanf("%d%d", &n, &q);
    n1=potenga(n+2);
    poty.push_back(1);
    for (int i=1; i<=11; i++)
    poty.push_back(poty.back()*42);
    zmi(1, 1, n1, 1, n1, 0);
    for (int i=1; i<=n; i++)
    {
        scanf("%d", &p1);
        zmi(1, 1, n1, i, i, p1);
    }
    while(q--)
    {
        scanf("%d", &typ);
        if (typ==1)
        {
            scanf("%d", &p1);
            czyt(1, 1, n1, p1);
            printf("%lldn", wyn);
        }
        if (typ==2)
        {
            scanf("%d%d%d", &p1, &p2, &p3);
            zmi(1, 1, n1, p1, p2, p3);
        }
        if (typ==3)
        {
            scanf("%d%d%d", &p1, &p2, &p3);
            dod(1, 1, n1, p1, p2, p3);
            while(1)
            {
                popr(1);
                if (zos[1]==0)
                {
                    dod(1, 1, n1, p1, p2, p3);
                }
                else
                {
                    break;
                }
            }
        }
    }
    return 0;
}

Hello Codeforces.

The CF Round #356 will happen on 8-th June (exact time). You will get five problems to solve in two hours. The round is rated.

I encourage you to read other problems if you don't like or can't solve something. The scoring distribution will be announced.

MikeMirzayanov and GlebsHP make the round possible. Also, thanks for Radewoosh, kostka, johnasselta, AlexFetisov and (more to be added?) for their amazing help. And I want to thank my girlfriend because there would be no Limak without her.

It's my first standard round. Still, you should get nice interesting problems. You will meet Limak, who is usually a little polar bear. Here he is, preparing one of problems.

I wish you great fun and no frustrating bugs.

EDIT — It's recommended for both divisions to read the Interactive Problems Guide before the round.

EDIT2, SCORING

div2: 500-1000-1750-2250-2750
div1: 750-1250-1500-2000-2500

EDIT3

The editorial with codes is ready.

WINNERS, congratulations!

1. Petr
2. ainta
3. halyavin
4. jcvb
5. brandnewnode

and Division 2:

1. Y_UME
2. kaq
3. BehtarinFake
4. Zoli9
5. Jeannette

Thank you all for participation and see you next time. And regards from Limak, a bear.

I'm not able to find any link. I think that this problem was used in the last day of the camp (Petrozavodsk, Winter 2015). I didn't manage to solve it during the contest and I still don't see a solution.

Given n ≤ 10⁶, find the standard deviation (or variance) of a_n, with allowed precision 10^- 6. A sequence a₁, a₂, ..., a_n is generated as follows:

a[1] = 1
for(int i = 2; i <= n; i++) {
	int j = rand(1, i-1); // random integer from interval [1, i-1]
	int k = rand(1, i-1);
	a[i] = a[j] + a[k];
}

I'm not sure about constraints but I think it doesn't matter (I would appreciate any polynomial solution). Also, maybe the answer was required modulo some number, instead of a real number with some precision — I don't know, sorry. And yes, the expected value is n.

Hi everybody.

May Clash 2016 has just started. You have 24 hours to solve 6 problems, including an approximation one (tie breaker). The submission time doesn't matter so you can join whenever you want.

You get points for each test passed so do your best even if you can't solve the problem for the given constraints. Remember that not all tests are max-tests.

This time, problems are invented by niyaznigmatul so you can expect a very high quality of the problemset. I was a tester. Also, thanks to YakutovDmitriy and lightning for ideas for problems.

Top3 gets amazon gift cards, top5 gets t-shirts, top50 gets their handles showed in the first page of the leaderboard (I know, it's awesome).

I wish you great fun and no frustrating bugs.

WINNERS

So much red.

1. HellKitsune
2. FatalEagle
3. zeliboba
4. Xellos
5. Lewin

Top3 got nice scores in an approximation problem, congrats. Not only top5 solved all non-aproximation problems so I want to also mention Fcdkbear, rajat1603 and eatmore.

Thank you for participating!

Hi everybody.

The VK Cup Round 3 is coming (exact time).

The duration will be longer than usual, likely 3 hours.

As usually in VK Cup, there will be three contests — div1, div2, official one. All of them are rated. Div1 and div2 versions are for individual participants, not for teams.

Setters are Radewoosh, Errichto and qwerty787788. I think that (some) problems are extremely interesting and I really wish I could participate. Thanks to GlebsHP and MikeMirzayanov, we wouldn't have a round without them. Also, thanks to AlexFetisov and winger for testing.

We will later inform about the final duration. Maybe we will inform about the number of problems and scoring.

I wish you great fun and no frustrating bugs. And Limak wishes you good luck!

UPD

• The contest will last 3 hours.
• ADJUSTED POINTS DROP — Points will decrease with such a speed that submitting a problem at the end would give you the same number of points as in standard 2-hour rounds.
• I updated testers above.
• Top50 in the "Div1 Edition" contest will get t-shirts. Have I already said "I wish I could participate"?

UPD 2

There are 9 problems. Div2 gets problems 1 - 6, and Div1+R3 gets 3 - 9. It means that there are 4 shared problems.
Division 2: 500 750 1000 1500 2250 3000
R3 & Div1: 500 1000 1750 2250 2250 3000 3000

UPD 3

Enjoy the editorial

UPD 4

The system testing is over. Congratulations to winners. Later I will try to put winners here in some nice format.

Codes in nicer format will be uploaded later.
658A - Bear and Reverse Radewoosh and 639A - Bear and Displayed Friends — codes.
639B - Bear and Forgotten Tree 3 and 639C - Bear and Polynomials — codes.
639D - Bear and Contribution — codes.
639E - Bear and Paradox — codes.
639F - Bear and Chemistry — codes.

658A - Bear and Reverse Radewoosh — Iterate once from left to right to calculate one player's score and then iterate from right to left. It's generally good not to write something similar twice because you are more likely to make mistakes. Or maybe later you will find some bug and correct it only in one place. So, try to write calculating score in a function and run them twice. Maybe you will need to reverse the given arrays in some moment.

639A - Bear and Displayed Friends — You should remember all friends displayed currently (in set or list) and when you add someone new you must check whether there are at most k people displayed. If there are k + 1 then you can iterate over them (over k + 1 people in your set/list) and find the worst one. Then — remove him. The intended complexity is O(n + q*k).

639B - Bear and Forgotten Tree 3 — You may want to write some special if for n = 2. Let's assume n ≥ 3. If d = 1 or d > 2h then there is no answer (it isn't hard to see and prove). Otherwise, let's construct a tree as follows.

We need a path of length h starting from vertex 1 and we can just build it. If d > h then we should also add an other path from vertex 1, this one with length d - h. Now we have the required height and diameter but we still maybe have too few vertices used. But what we built is one path of length d where d ≥ 2. You can choose any vertex on this path other than ends of the path (let's call him v), and add new vertices by connecting them all directly with v. You can draw it to see that you won't increase height or diameter this way. In my code I sometimes had v = 1 but sometimes (when d = h) I needed some other vertex and v = 2 was fine.

639C - Bear and Polynomials, my favorite problem in this contest. Let's count only ways to decrease one coefficient to get the required conditions (you can later multiply coefficient by  - 1 and run your program again to also calculate ways to increase a coefficient).

One way of thinking is to treat the given polynomial as a number. You can find the binary representation — a sequence with 0's and 1's of length at most . Changing one coefficient affects up to consecutive bits there and we want to get a sequence with only 0's. We may succeed only if all 1's are close to each other and otherwise we can print 0 to the output. Let's think what happens when 1's are close to each other.

Let's say that we got a sequence with two 1's as follows: ...00101000.... Decreasing by 5 one coefficient (the one that was once in a place of the current first bit 1) will create a sequence of 0's only. It's not complicated to show that decreasing coefficients on the right won't do a job (because the first 1 will remain there) but you should also count some ways to change coefficients on the left. We can decrease by 10 a coefficient on the left from first 1, or decrease by 20 a coefficient even more on the left, and so on. Each time you should check whether changing the original coefficient won't exceed the given maximum allowed value k.

One other solution is to go from left to right and keep some integer value — what number should be added to the current coefficient to get sum equal to 0 on the processed prefix. Then, we should do the same from right to left. In both cases maybe in some moment we should break because it's impossible to go any further. In one case it happens when we should (equally) divide an odd number by 2, and in the other case it happens when our number becomes too big (more than 2·10⁹) because we won't be able to make it small again anyway.

639D - Bear and Contribution — It isn't enough to sort the input array and use two pointers because it's not correct to assume that the optimal set of people will be an interval. Instead, let's run some solution five times, once for each remainder after dividing by 5 (remainders 0, 1, 2, 3, 4). For each remainder r we assume that we should move k people to some value x that (and at the end we want at least k people to have contribution x). Note that x must be close to some number from the input because otherwise we should decrease x by 5 and for sure we would get better solution. The solution is to iterate over possible values of x from lowest to highest (remember that we fixed remainder ). At the same time, we should keep people in 5 vectors/lists and do something similar to the two pointers technique. We should keep two pointers on each of 5 lists and always move the best among 5 options. The complexity should be O(n·5).

639E - Bear and Paradox — It's good to know what to do with problems about optimal order. Often you can use the following trick — take some order and look at two neighbouring elements. When is it good to swap? (When does swapping them increase the score?) You should write some simple formula (high school algebra) and get some inequality. In this problem it turns out that one should sort problems by a fraction and it doesn't depend on a constant c. There may be many problems with the same value of and we can order them however we want (and the question will be: if there is a paradox for at least one order). Let's call such a set of tied problems a block.

For each problem you can calculate its minimum and maximum possible number of granted points — one case is at the end of his block and the other case is to solve this problem as early as possible so at the beginning of his block. So, for fixed c for each problem we can find in linear time the best and worst possible scores (given points).

When do we get a paradox? Where we have two problems i and j that p_i < p_j (p_i was worth less points) we solved problem i much earlier and later we got less points for problem p_j. We can now use some segment tree or sort problems by p_i and check whether there is a pair of problems with inequalities we are looking for — p_i < p_j and max_i > min_j where max_i and min_j we found in the previous paragraph.

We can do the binary search over the answer to get complexity or faster. Can you solve the problem in linear time?

639F - Bear and Chemistry — Task is about checking if after adding some edges to graph, some given subset of vertices will be in one biconnected component. Firstly, let's calculate biconnected components in the initial graph. For every vertex in each query we will replace it with index of its bicon-component (for vertices from subset and for edges endpoints). Now we have a forest. When we have a list of interesting vertices in a new graph (bicon-components of vertices from subset or edges) we can compress an entire forest, so it will containg at most 2 times more vertices than the list (from query) and will have simillar structure to forest. To do it, we sort vertices by left-right travelsal order and take LCA of every adjacent pair on the sorted list. If you have compressed forest, then you just have to add edges and calculate biconnected components normally, in linear time.

Problems ABCG will be described better soon.

problem A — watch out for test like "1 1 1 2 2 2 2 3 3 3". It shows that it's not enough to sort number and check three neighbouring elements. You must remove repetitions. The easier solution is to write 3 for-loops, without any sorting. Do you see how?

problem B — you should generate all 6ⁿ possible starting strings and for each of them check whether you will get "a" at the end. Remember that you should check two first letters, not last ones (there were many questions about it).

653C - Медвежонок, взлёты и падения — Let's call an index i bad if the given condition about t_i and t_i + 1 doesn't hold true. We are given a sequence that has at least one bad place and we should count ways to swap two elements to fix all bad places (and not create new bad places). The shortest (so, maybe easiest) solution doesn't use this fact but one can notice that for more than 4 bad places the answer is 0 because swapping t_i and t_j can affect only indices i - 1, i, j - 1, j.

With one iteration over the given sequence we can find and count all bad places. Let x denote index of the first bad place (or index of some other bad place, it's not important). We must swap t_x or t_x - 1 with something because otherwise x would still be bad. Thus, it's enough to consider O(n) swaps ~-- for t_x and for t_x - 1 iterate over index of the second element to swap (note that "the second element" doesn't have to be bad and samples show it). For each of O(n) swaps we can do the following (let i and j denote chosen two indices):

1. Count bad places among four indices: i - 1, i, j - 1, j. If it turns out that these all not all initial bad places then we don't have to consider this swap — because some bad place will still exist anyway.
2. Swap t_i and t_j.
3. Check if there is some bad place among four indices: i - 1, i, j - 1, j. If not then we found a correct way.
4. Swap t_i and t_j again, to get an initial sequence.

Be careful not to count the same pair of indices twice. In the solution above it's possible to count twice a pair of indices (x - 1, x) (where x was defined in the paragraph above). So, add some if or do it more brutally — create a set of pairs and store sorted pairs of indices there.

TODO — add codes.

CHALLENGE — can you solve this problem if the initial sequence is already nice (if it doesn't have bad places)?

653D - Медвежья доставка — invented and prepared by Lewin, also the editorial.

Java code: 16825205
C++ code solving also the harder version: 16825257

Let's transform this into a flow problem. Here, we transform "weight" into "flow", and each "bear" becomes a "path".

Suppose we just want to find the answer for a single x. We can do this binary search on the flow for each path. To check if a particular flow of F is possible, reduce the capacity of each edge from c_i to . Then, check if the max flow in this graph is at least x. The final answer is then x multiplied by the flow value that we found.

MUCH HARDER VERSION — you are also given an integer k (1 ≤ k ≤ 10⁴) and your task is to find the answer for x paths, for x + 1 paths, ..., and for x + k - 1 paths. There should be k real values on the output.

653E - Медвежонок и забытое дерево 2

C++ code: 16826422

You are given a big graph with some edges forbidden, and the required degree of vertex 1. We should check whether there exists a spanning tree. Let's first forget about the condition about the degree of vertex 1. The known fact: a spanning tree exists if and only if the graph is connected (spend some time on this fact if it's not obvious for you). So, let's check if the given graph is connected. We will do it with DFS.

We can't run standard DFS because there are maybe O(n²) edges (note that the input contains forbidden edges, and there may be many more allowed edges then). We should modify it by adding a set or list of unvisited vertices s. When we are at vertex a we can't check all edges adjacent to a and instead let's iterate over possible candidates for adjacent unvisited vertices (iterate over s). For each b in s we should check whether a and b are connected by a forbidden edge (you can store input edges in a set of pairs or in a similar structure). If they are connected by a forbidden edge then nothing happens (but for each input edge it can happen only twice, for each end of edge, thus O(m) in total), and otherwise we get a new vertex. The complexity is where is from using set of forbidden edges.

Now we will check for what degree of vertex 1 we can build a tree. We again consider a graph with n vertices and m forbidden edges. We will first find out what is the minimum possible degree of vertex 1 in some spanning tree. After removing vertex 1 we would get some connected components and in the initial graph they could be connected to each other only with edges to vertex 1. With the described DFS we can find c (1 ≤ c ≤ n - 1) — the number of created connected components. Vertex 1 must be adjacent to at least one vertex in each of c components. And it would be enough to get some tree because in each component there is some spanning tree — together with edges to vertex 1 they give us one big spanning tree with n vertices (we assume that the initial graph is connected).

And the maximum degree of vertex 1 is equal to the number of allowed edges adjacent to this vertex. It's because more and more edges from vertex 1 can only help us (think why). It will be still possible to add some edges in c components to get one big spanning tree.

So, what is the algorithm? Run the described DFS to check if the graph is connected (if not then print "NO"). Remove vertex 1 and count connected components (e.g. starting DFS's from former neighbours of vertex 1). Also, simply count d — the number of allowed edges adjacent to vertex 1. If the required degree k is between c and d inclusive then print "YES", and otherwise print "NO".

653F - Бумажная работа — invented and prepared by k790alex, also the editorial.

Java code (modify-SA-solution): 16821422
C++ code (compressing-solution): 16826803

There are two solutions. The first and more common solution required understanding how do SA (suffix array) and LCP (longest common prefix) work. The second processed the input string first and then run SA+LCP like a blackbox, without modifying or caring about those algorithms.

Modify-SA-solution — The main idea is to modify the algorithm for computing the number of distinct substrings using SA + LCP.

Let query(L, R) denote the number of well formed prefixes of substring(L, R). For example, for substring(L, R) = "(())()(" we would have query(L, R) = 2 because we count (()) oraz (())().

How to be able to get query(L, R) fast? You can treat the opening bracket as  + 1 and the ending bracket as  - 1. Then you are interested in the number of intervals starting in L, ending not after R, with sum on the interval equal to zero. Additionally, the sum from L to any earlier right end can't be less than zero. Maybe you will need some preprocessing here, maybe binary search, maybe segment trees. It's an exercise for you.

We can iterate over suffix array values and for each suffix we add query(suffix, N) - query(suffix, suffix + LCP[suffix] - 1) to the answer. In other words we count the number of well formed substrings in the current suffix and subtract the ones we counted in the previous step.

The complexity is but you could get AC with very fast solution with extra .

Compressing-solution — I will slowly compress the input string, changing small well-formed substrings to some new characters (in my code they are represented by integer numbers, not by letters). Let's take a look at the example:

or equivalently:

Whenever I have a maximum (not possible to expand) substring with single letters only, without any brackets, then I add this substring to some global list of strings. At the end I will count distinct substrings in the found list of strings (using SA+LCP). In the example above I would first add a string "a" and later I would add "baa". Note that each letter represents some well formed substring, e.g. 'b' represents (()) here.

I must make sure that the same substrings will be compressed to the same letters. To do it, I always move from left to right, and I use trie with map (two know what to get from some two letters).

problem G — you can consider each prime number separately. Can you find the answer if there are only 1's and 2's in the input? It may be hard to try to iterate over possible placements of the median. Maybe it's better to think how many numbers we will change from 2^p to 2^{p+1}.

Hi everybody.

The IndiaHacks finals will take place tomorrow (on Saturday). The contest is being organized by HackerEarth. Just after the official finals, the CF round will start (check-your-time) with almost the same problems. You can treat it as a standard CF round — there will be 5 problems in each of 2 divisions, and 2 hours to solve them. Two divisions will compete together on the problem set with 7 problems, with 2 hours to solve them.

I want to especially thank I_love_Tanya_Romanova for testing the problems, GlebsHP for help with making the CF round possible, and MikeMirzayanov for his awesome attitude and for the Polygon system. Setters: Lewin, k790alex, Sokolov, Errichto. Testers: I_love_Tanya_Romanova, Errichto. Small help: belowthebelt, raviojha2105, johnasselta, Radewoosh. And my big thanks to HackerEarth for inviting me to Bangalore, it's truly a vibrant city.

Some info only for 40 official finalists — Remember not to discuss anything until the CF round ends (so, at least 2 hours after the official contest ends). You will find all important information at link-to-the-contest. You can ask me questions by PM on CF or on HE, and I will put answers in the "Challenge Details" at the link provided. Do not use comments here because it can only confuse others. You can use some old blog about the IndiaHacks semifinals if you want to discuss something.

I wish you great fun and no frustrating bugs. Enjoy the contest.

Scoring: 500-1000-1500-2000-2500-3500-3500.

WINNERS

1. jqdai0815, the only one to solve all 7 problems!
2. JoeyWheeler
3. jcvb
4. andrew.volchek
5. ikatanic

In the official finals there were technical issues with the stack size (it was again only 8MB) and constraints in E weren't correct at the beginning. We want to fix it as much as possible, without any guessing though — we can't say how much time did you waste because of something. If you were affected then write to me PM with the description of the situation. Your time penalties will be canceled (and maybe some earlier submission will be accepted, if only the stack size didn't allow you to get AC).

Editorial is being created here.

If you don't know what the dynamic scoring is, you can read about it here. In my opinion it's a useful alternative. With smoother steps (250 instead of 500) it doesn't work so bad. Or does it? The main advantage is that organizers don't have to correctly estimate the difficulty. What are drawbacks? And should it be changed and improved in some way?

Hi. I want to invite you to HourRank 6. The contest will take place tomorrow (exact time) on the HackerRank platform. The duration is exactly one hour. I think that both beginners and experienced participants will find problems interesting for them.

There are problems from me and from forthright48. I want to thank Radewoosh for helping me with preparing problems, and for testing. I also thank malcolm, wanbo and Shafaet for testing and the technical help.

Limak needs you! I wish you great fun and no frustrating bugs. Looking forward to seeing you!

Besides fun, top 10 will get HR t-shirts. Good luck.

WINNERS

1. Endagorion
2. LayCurse
3. riadwaw
4. I_love_Tanya_Romanova
5. tabasz

It happened to me twice to skip a CF round because of the registration. Once I was too late, and once I even implemented A and tried to submit — but it turned out I haven't registered. It also happened to some of my friends.

For standard CF rounds the registration ends 5 minutes before the contest. The reason is that participants must be divided into rooms, to be able to hack. But hacking isn't so important, right? It's some extra possibility and many would enjoy a round even without hacks.

Let's allow participating without having a room. All people registered at least 5 minutes before should be assigned to rooms as usually. And after that, one should be able to register "out of room" — to participate without hacking and being hacked. A round should be rated for everybody. So, one could register after reading problems, and maybe even after implementing something.

Note that hacks are only a privilege. It's good to be hacked instead of getting WA on systests, and it's good to be able to hack others. So, it will be optimal to register before a round, if possible.

Does anybody see any drawbacks? If not, then make this change please. @CF_TEAM

Hi again.

Tomorrow (exact time) the Semifinals of IndiaHacks-Algorithms will start — link. You can participate only if you got any points in at least one of qualifiers. You will get 24 hours and 10 problems, including an approximation one to break ties. The submitting time doesn't matter unless you have a tie in an approximation problem (very unlikely).

In my opinion problems are unusually interesting. They were prepared by kostya_by, k790alex, and by me. Thanks for johnasselta and belowthebelt for helping me with testing and checking everything.

Top20 Indians advance to onsite finals. Top20 non-Indians advance to finals but will participate remotely, still fighting for prizes. Finals will happen somewhen in March.

I wish you great fun and no frustrating bugs. Looking forward to seeing you! Below, you can see prizes for top contestants in the final round.

WINNERS OF THE SEMIFINALS

1. tourist
2. eatmore
3. Al.Cash
4. mugurelionut
5. Romka

And congratulations for all advancing to the final round. The unofficial list of advancers is in the comments below.

Good morning everybody.

January Clash '16 will start tomorrow (check your time zone). Duration is 24 hours and submitting time doesn't matter so you can join whenever you want.

Note the unusual starting time (compared to previous Clashes). We moved it a bit because of colliding with Facebook Hacker Cup.

You will be given 5 algorithmic problems and one approximate (optimization) one. All problems will have partial scoring (points for each test passed) and easier subtasks. Thus, everybody should find something for themselves. Getting full points on all 5 problems should be hard for everyone. Remember to solve as many subtasks as possible if you want to get to the top.

Problems were prepared by Lewin. He is an author of numerous contests, including many SRM's on TopCoder (link) so you don't have to worry about the quality of the problem set. I am a tester and an editorialist.

Problems are interesting and so do smaller subtasks. Don't expect them to be very easy though — some of them are far from being straightforward. Anyway, solve them first if you don't see a 100-points-solution.

There are prizes — t-shirts and Amazon gift cards. And the eternal glory of course.

Enjoy a contest.

WINNERS

Congratulations:

1. Egor
2. Kostroma
3. HellKitsune
4. anta
5. akashdeep
6. ishraq

I want to congratulate anta for solving the hardest problem and Egor for almost solving it — but well, he won anyway. Kostroma had the best score in an approximate problem and HellKitsune was very close to that.

What was your approach to an approximate problem?

Hello Codeforces!

HackerEarth invites you to a unique Artificial Intelligence type contest — Bot Challenge. The contest will start on January 8, 3:30 PM MSK and will last for almost a week.

You have to build a bot that plays a two-player game (like Tic-tac-toe or Chess) with a bot built by another user. Your bot has to read what happens and play (print) its moves against the opponent. At the end of challenge, your bot will be played in a tournament against all other bots, and the bot that wins the tournament will be declared the winner.

Also, while the contest is running, you can challenge other people who have submitted their bots to play against you.

Register at https://www.hackerearth.com/bot-challenge-india-hacks-2016/ and fight for prizes:

You can practice in previous Bot contests(#1 and #2), to understand more about the problem statement and the format of the contest. Gullesnuffs won last two Bot challenges. Will you allow him to take the first place again?

You can check out this gameplay between Gullesnuffs and uwi in one of previous Bot challenges. Hit the replay button there and just watch it.

This challenge is a part of IndiaHacks 2016 tracks. Don't miss qualifications for the other track — algorithms. Check out date of the next qualification round at the link provided. I'm responsible for the final round (problems will be prepared by many setters though) — 24 hours, 10 problems, including an approximate one. And the same set of prizes!

Participate and have fun!

611A - New Year and Days

There are two ways to solve this problem.

The first is to hard-code numbers of days in months, check the first day of the year and then iterate over days/months — http://ideone.com/4TYPCc

The second way is to check all possible cases by hand. The 2016 consists of 52 weeks and two extra days. The answer for "x of week" will be either 52 or 53. You must also count the number of months with all 31 days and care about February. http://ideone.com/Bf9QLz

611B - New Year and Old Property

Each number with exactly one zero can be obtained by taking the number without any zeros (e.g. 63₁₀ = 111111₂) and subtracting some power of two, e.g. 63₁₀ - 16₁₀ = 111111₂ - 10000₂ = 101111₂. Subtracting a power of two changes one digit from '1' to '0' and this is what we want. But how can we iterate over numbers without any zeros? It turns out that each of them is of form 2^x - 1 for some x (you can check that it's true for 63₁₀).

What should we do to solve this problem? Iterate over possible values of x to get all possible 2^x - 1 — numbers without any zeros. There are at most values to consider because we don't care about numbers much larger than 10¹⁸. For each 2^x - 1 you should iterate over powers of two and try subtracting each of them. Now you have candidates for numbers with exactly one zero. For each of them check if it is in the given interval. You can additionally change such a number into binary system and count zeros to be sure. Watch out for overflows! Use '1LL << x' instead of '1 << x' to get big powers of two. http://ideone.com/Kfu8sF

611C - New Year and Domino

How would we solve this problem in O(wh + q) if a domino would occupy only one cell? Before reading queries we would precalculate dp[r][c] — the number of empty cells in a "prefix" rectangle with bottom right corner in a cell r, c. Then the answer for rectangle r1, c1, r2, c2 is equal to dp[r2][c2] - dp[r2][c1 - 1] - dp[r1 - 1][c2] + dp[r1 - 1][c1 - 1]. We will want to use the same technique in this problem.

Let's separately consider horizontal and vertical placements of a domino. Now, we will focus on horizontal case.

Let's say that a cell is good if it's empty and the cell on the right is empty too. Then we can a place a domino horizontally in these two cells. The crucial observation is that the number of ways to horizontally place a domino is equal to the number of good cells in a rectangle r1, c1, r1, c2 - 1.

You should precalculate a two-dimensional array hor[r][c] to later find the number of good cells quickly. The same for vertical dominoes. http://ideone.com/wHsZej

611D - New Year and Ancient Prophecy

By {x... y} I will mean the number defined by digits with indices x, x + 1, ..., y.

Let dp[b][c] define the number of ways to split some prefix (into increasing numbers) so that the last number is {b... c} We will try to calculate it in O(n²) or . The answer will be equal to the sum of values of dp[i][n] for all i.

Of course, dp[b][c] = 0 if digit[b] = 0 — because we don't allow leading zeros.

We want to add to dp[b][c] all values dp[a][b - 1] where the number {a... b - 1} is smaller than {b... c}. One crucial observation is that longer numbers are greater than shorter ones. So, we don't care about dp[a][b - 1] with very low a because those long numbers are too big (we want {a... b - 1} to be smaller than our current number {b... c}). On the other hand, all a that (b - 1) - a < c - b will produce numbers shorter than our current {b... c}. Let's add at once all dp[a][b - 1] for those a. We need . Creating an additional array with prefix sums will allow us to calculate such a sum in O(1).

There is one other case. Maybe numbers {a... b - 1} and {b... c} have the same length. There is (at most) one a that (b - 1) - a = c - b. Let's find it and then let's compare numbers {a... b - 1} and {b... c}. There are few ways to do it.

One of them is to store hashes of each of n·(n + 1) / 2 intervals. Then for fixed a, b we can binary search the first index where numbers {a...} and {b... } differ. http://ideone.com/Rrgk8T. It isn't an intended solution though. Other way is to precalculate the same information for all pairs a, b with dynamic programming. I defined nxt[a][b] as the lowest x that digit[a + x] ≠ digit[b + x]. Now, either nxt[a][b] = nxt[a + 1][b + 1] + 1 or nxt[a][b] = 0. http://ideone.com/zczsc3

611E - New Year and Three Musketeers

The answer is  - 1 only if there is some criminal stronger than a + b + c. Let's deal with this case and then let's assume that a ≤ b ≤ c.

Let's store all criminal- s in a set (well, in a multiset). Maybe some criminals can be defeated only by all musketeers together. Let's count and remove them. Then, maybe some criminals can be defeated only by b + c or a + b + c (no other subsets of musketeers can defeat them). We won't use a + b + c now because it's not worse to use b + c because then we have the other musketeer free and maybe he can fight some other criminal. Greedily, let's remove all criminals which can be defeated only by b + c and at the same time let a defeat as strong criminals as possible. Because why would he rest?

Now, maybe some criminals can be defeated only by a + c or b + c or a + b + c. It's not worse to use a + c and to let the other musketeer b defeat as strong criminals as possible (when two musketeers a + c fight together).

We used a + b + c, b + c, a + c. We don't know what is the next strongest subset of musketeers. Maybe it's a + b and maybe it's c. Previous greedy steps were correct because we are sure that .

Now in each hour we can either use a, b, c separately or use a + b and c. Let's say we will use only pair a + b and c. And let's say that there are x criminals weaker than a + b and y criminals weaker than c. Then the answer is equal to . The explanation isn't complicated. We can't be faster than because we fight at most two criminals in each hour. And maybe e.g. y (because c is weak) so c will quickly defeat all y criminals he can defeat — and musketeers a + b must defeat x - y criminals.

Ok, we know the answer in O(1) if we're going to use only a + b and c. So let's assume it (using only these two subsets) and find the possible answer. Then, let's use a, b, c once. Now we again assume that we use only a + b and c. Then we use a, b, c once. And so on.

What we did is iterating over the number of times we want to use a, b, c. http://ideone.com/R3Oy3F

611F - New Year and Cleaning

Let's not care where we start. We will iterate over robot's moves.

Let's say the first moves are LDR. The very first move 'L' hits a wall only if we started in the first column. Let's maintain some subrectangle of the grid — starting cells for which we would still continue cleaning. After the first move our subrectangle lost the first column. The second move 'D' affects the last row. Also, all cells from the last row of our remaining subrectangle have the same score so it's enough to multiply the number of cells there and an index of the current move. The third move 'R' does nothing.

Let's simulate all moves till our subrectangle becomes empty. To do it, we should keep the current x, y — where we are with respect to some starting point. We should also keep max_x, max_y, min_x, min_y — exceeding value of one of these four variables means that something happens and our subrectangle losts one row or one column.

But how to do it fast? You can notice (and prove) that the second and and each next execution of the pattern looks exactly the same. If we have pattern RRUDLDU and the first letter 'U' affects out subrectangle in the second execution of the pattern, then it will also affect it in the third execution and so on. If and only if.

So, we should simalate the first n moves (everything can happen there). Then, we should simulate the next n moves and remember all places where something happened. Then we should in loop iterate over these places. Each event will decrease width or height of our subrectangle so the complexity of this part is O(w + h). In total O(w + h + n). http://ideone.com/xrU9u2

CHALLENGE FOR PROBLEM F (CLEANING ROBOT) — I was considering an alternative version of this problem, harder one. The same constraint for n but this time h, w ≤ 10⁹. Describe a solution in comments and optionally implement it (it should get AC on this problem, right?). I will mention here the first person to solve this challenge.

611G - New Year and Cake

We are given a polygon with vertices P₁, P₂, ..., P_n. Let Poly(i, j) denote the doubled area of a polygon with vertices P_i, P_i + 1, P_i + 2, ..., P_j - 1, P_j. While implementing you must remember that indices are in a circle (there is 1 after n) but I won't care about it in this editorial.

We will use the cross product of two points, defined as A × B = A.x·B.y - A.y·B.x. It's well known (and you should remember it) that the doubled area of a polygon with points Q₁, Q₂, ..., Q_k is equal to Q₁ × Q₂ + Q₂ × Q₃ + ... + Q_k - 1 × Q_k + Q_k × Q₁.

Let smaller denote the area of a smaller piece, bigger for a bigger piece, and total for a whole polygon (cake).
smaller + bigger = total
smaller + (smaller + diff) = total
diff = total - 2·smaller (the same applies to doubled areas)
And the same equation with sums:
where every sum denotes the sum over possible divisions.

In O(n) we can calculate total (the area of the given polygon). So, the remaining thing is to find and then we will get (this is what we're looking for).

For each index a let's find the biggest index b that a diagonal from a to b produces a smaller piece on the left. So, .

To do it, we can use two pointers because for bigger a we need bigger b. We must keep (as a variable) the sum S = P_a × P_a + 1 + ... + P_b - 1 × P_b. Note that S isn't equal to Poly(a, b) because there is no P_b × P_a term. But S + P_b × P_a = Poly(a, b).

To check if we should increase b, we must calculate Poly(a, b + 1) = S + P_b × P_b + 1 + P_b + 1 × P_a. If it's not lower that then we should increase b by 1 (we should also increase S by P_b × P_b + 1). When moving a we should decrease S by P_a × P_a + 1.

For each a we have found the biggest (last) b that we have a smaller piece on the left. Now, we will try to sum up areas of all polygons starting with a and ending not later than b. So, we are looking for Z = Poly(a, a + 1) + Poly(a, a + 2) + ... + Poly(a, b). The first term is equal to zero but well, it doesn't change anything.

Let's talk about some intuition (way of thinking) for a moment. Each area is equal so the sum of cross products of pairs of adjacent (neighboring) points. We can say that each cross product means one side of a polygon. You can take a look at the sum Z and think — how many of those polygons have a side P_aP_a + 1? All b - a of them. And b - a - 1 polygons have a side P_a + 1P_a + 2. And so on. And now let's do it formally:

Poly(a, a + 1) = P_a × P_a + 1 + P_a + 1 × P_a
Poly(a, a + 2) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a
Poly(a, a + 3) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a + 3 + P_a + 3 × P_a
...
Poly(a, b) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a + 3 + ... + P_b - 1 × P_b + P_b × P_a

Z = Poly(a, a + 1) + Poly(a, a + 2) + ... + Poly(a, b) = 
 = (b - a)·(P_a × P_a + 1) + (b - a - 1)·(P_a + 1 × P_a + 2) + (b - a - 2)·(P_a + 2 × P_a + 3) + ... + 1·(P_b - 1 × P_b) + 
 + P_a + 1 × P_a + P_a + 2 × P_a + ... + P_b × P_a

The last equation is intentionally broken into several lines. We have two sums to calculate.

1. The first sum is (b - a)·(P_a × P_a + 1) + (b - a - 1)·(P_a + 1 × P_a + 2) + ... + 1·(P_b - 1 × P_b). We can calculate it in O(1) if we two more variables sum_product and sum_product2. The first one must be equal to the sum of P_i × P_i + 1 for indices in an interval [a, b - 1] and the second one must be equal to the sum of (P_i × P_i + 1)·(i + 1). Then, the sum is equal to sum_product * (b + 1) - sum_product2.

2. The second sum is P_a + 1 × P_a + P_a + 2 × P_a + ... + P_b × P_a = SUM_POINTS × P_a where SUM_POINTS is some fake point we must keep and SUM_POINTS = P_a + 1 + P_a + 2 + ... + P_b. So, this fake point's x-coordinate is equal to the sum of x-coordinates of P_a + 1, P_a + 2, ..., P_b and the same for y-coordinate. In my code you can see variables sum_x and sum_y.

Implementation. http://ideone.com/RUY5lF

611H - New Year and Forgotten Tree

There are at most k = 6 groups of vertices. Each grouped is defined by the number of digits of its vertices.

It can be probed that you can choose one vertex (I call it "boss") in each group and then each edge will be incident with at least one boss. We can iterate over all k^k - 2 possible labeled trees — we must connect bosses with k - 1 edges. Then we should add edges to other vertices. An edge between groups x and y will "kill" one vertex either from a group x or from a group y. You can solve it with flow or in O(2^k) with Hall's theorem. http://ideone.com/7KuS1l

Hi everybody.

The last round of the 2015 will take place on the 30-th of December (starting time). The contest will last 3 hours.

It won't be a usual round. Both divisions will compete together. You will get 8 problems to solve in 3 hours. Points will decrease slower than usually — otherwise you would get eps for solving a problem at the end. Scoring will be announced just before a contest. So will the speed of the points/minute loss.

My goal was to provide you a diverse problemset with interesting problems for all contestants. During a contest you should consider reading not only the next problem but the few next ones.

You will get this round thanks to work of many people. I am a problem setter. GlebsHP helps me with everything (a lot). AlexFetisov, johnasselta and Zlobober are testers (thanks guys!). Delinur translates everything into Russian. Last but not least, MikeMirzayanov provides two awesome platforms — CF and Polygon. And there are so many people involved in Codeforces. Thank you all.

Let me give you more motivation to compete. The New Year is coming for Limak and he needs your help! Limak is a little polar bear by the way. You will help him, won't you?

I wish you great fun and no frustrating bugs. Looking forward to seeing you!

SCORING

Points will decrease with such a speed that submitting a problem at the end would give you the same number of points as in standard 2-hours rounds. Points for problems are 500-750-1250-1750-2500-2500-3000-3500. Enjoy the last contest in this year!

EDITORIAL

Instead of refreshing standings you can read an editorial. I will keep polishing it.

WINNERS

I'm amazed by the number of high-rated participants today. Fight was really tough and winners truly deserve respect.

1. tourist
2. Petr
3. Egor
4. rng_58
5. black_horse2014
6. step5
7. I_love_Tanya_Romanova
8. bmerry
9. W4yneb0t
10. V--o_o--V

It was the last Codeforces round in the 2015. Thanks for participating. And kudos for Mike for creating CF.

I wish you all an awesome year. Let the 2016 be (even) better than the passing year. Cheers.

Hello Codeforces Community!

I invite you to December Clash 2015. It will take place on Dec, 19-th at 9:30 MSK. Duration is 24 hours and submitting time doesn't matter so you can start whenever you want.

You will be given 5 algorithmic problems and one approximate (optimization) one. Some problems should be hard even for very strong competitors. All problems will have partial scoring (points for each test passed) and easier subtasks. Thus, everybody should find something for themselves.

EDIT — Problems are not necessarily sorted by the difficulty! Each problem is worth 100 points but scoring is partial so try to pass as many tests as possible! There is no penalty for incorrect submissions.

In my opinion problems are interesting and I hope you will have nice time solving them. It shouldn't be a typing competition for anybody. I'm very curious about the number of people with all 5 problems solved and about your scores in an approximate problem. We'll see.

I want to thank Akul Sareen (akulsareen) for his amazing help as a tester. He will also provide you editorials after a contest. And big thanks to HackerEarth admins — Arjit Srivastava (belowthebelt) and Ravi Ojha (raviojha2105).

Enjoy problems!

Oh, and there prizes. 5 T-shirts and 3 Amazon gift cards for the best participants. I guess it will make a fight for top spots a bit more interesting.

The contest is over! I hope you enjoyed it. Congratulations for top5, good job.

1. mugurelionut
2. Marcin_smu
3. LayCurse
4. zeliboba
5. Carsten Eilks (HE account)

Is it a coincidence that top6 has nicely distributed scores? Roughly, the i-th place has score 510 - 10i.

Div2

Codes for all Div2 problems

BearSong (250p.)

There are two ways to solve this problem. The first way is to create an array T of size 1000 to count occurrences of each note. For each number x in the given sequence we should do T[x]++. After that, we should iterate over T and count the number of indices with value 1.

There is an alternative O(N²) solution. For each element of the given sequence we can iterate over other elements to check whether some of them is equal to the current one.

BearSlowlySorts (500p.)

Again, there are two ways to solve a problem. The first one is quite boring. One could notice that the answer must be small and we can simulate first few moves in any possible way. Some extra observation is that after sorting the first N-1 we shouldn't sort them again in the next move. So we should either do moves in the order {first, last, first, last, ...} or {last, first, last, first, ...} — there are only two possibilities.

With some cases analysis you can find solve this problem even without sorting. The crucial observation is that we care mostly about the smallest number and the largest one.
- The answer is 0 only if the sequence is already sorted.
- If the first number is the smallest one (thus, we don't have to move it), then the answer is 1.
- If the last number is the largest one, the answer is 1.
- If the first number is unfortunately the largest and the last number is the smallest one, the answer is 3.
- Otherwise, we can sort a sequence in 2 moves.

BearPermutations2 (1000p.)

O(N⁴) solutions should get AC but I will describe a O(N²) solution. We want to find an answer for all n up to given N.

For fixed n let's iterate over all n possible places to put the smallest number. Let where denote an index of the smallest number. The smallest number divides n numbers into two almost independent groups A and B and the equation |A| + |B| + 1 = n holds (moreover, |A| = where - 1, |B| = n - where). There are ways to divide numbers into two groups. For fixed division of numbers and for fixed position of the smallest number in A there are (|A| - 1)!·|B|! ways to arrange numbers. Note that it doesn't matter what "position of the smallest number in A" we chose.

For nonempty A and B for any arrangement the difference between indices of the smallest numbers in A and in B could be written as a sum of two terms:
- the difference between an index of the smallest number in B and a value where defined before. Note that such a distance is in interval [1, |B|].
- the difference between where and an index of the smallest number in A

Calculating the two terms above separately allows us to calculate everything for A and for B separately. Now, we can sum up for all so it's enough to add to the result. There is |A| - 1 because the smallest elements is chosen and placed already. More details in my code.

Div1

Codes for all Div1 problems

BearCavalry (300p.)

For each horse let's assume that it is assigned to Bravebeart and let's calculate the number of ways to assign other horses to other warriors.

For each case let's sort all other warriors and all other horses. With two pointers we can find for each warrior what horses he can get (it's limited by the strength of the Bravebeart's unit). We now know the number of ways (let a denote it) to assign a horse to the strongest warrior. He takes one horse and it was one of the horses the next (second strongest) warrior could get. We calculated that the second strongest warrior can take one of b horses but one was taken so he can b - 1 possibilities. The third warrior could take c horses but two are taken so we multiply some variable (result for this case) by c - 2. And so on. For each case we should add a·(b - 1)·(c - 2)·... to the result.

BearPermutations (600p.)

Read the Div2-Hard editorial first. The task there was to sum up scores for the given N.

In O(N⁴·S²) we could do the following dynamic programming. dp[n][where][S] is the number of n-permutations with the smallest number in position (index) where and the score equal to S. The main line of our program would be:

dp[n1+n2+1][n1+1][S1+S2 + n1+1+where2 - where1] +=  binom[n1+n2][n1] * dp[n1][where1][S1] * dp[n2][where2][S2]

We can notice that terms S2 and where2 appear only in one dimension of the resulting dp[][][]. The same for S1 and where1. Thus, we can create an array dpLeft[n][sw] to store the sum of dp[n][where][s] that where - s = sw. Similarly, we should create an array dpRight[n][sw]. You can additionally notice that these two arrays are similar and we need only one of them.

BearGirls (1000p.)

Backwards dynamic programming. What is hard to calculate is f(k, r) denoting the expected value of the r-th biggest number among k randomly chosen ones. It turns out to be simple to calculate because f(k, r) = p·f(k + 1, r + 1) + (1 - p)·f(k + 1, r) for . Don't be misled by words "simple to calculate". It took me literally weeks to solve this problem and I don't say that it is easy to find the formula above.

Looks like binomial coefficient, right? And this is how we can prove its correctness. When we have k numbers and the r-th biggest one is marked, we can still add other numbers one by one. The new number will be greater with probability . You can find my code above.

You may wonder why there was some cost given. The problem would be fine without it but well written O(N³) solution could be squeezed to pass then.

Good morning, Codeforces.

On Sunday, Nov 8-th at 11:30 MSK the ACM ICPC training (link) will be hosted on HackerEarth. Gather your team up to 3 members and try to solve as many problems as you can (and solve them fast).

You will be provided 10-12 problems to solve in 5 hours. Problems are of decent difficulty, hard enough for any contestants. My more precise estimation is that there is not more than one team in the world able to solve all problems in 2-3 hours. Of course, beginners will find something interesting too.

Poland has an acm-preparing camp right now so you will compete with all Polish teams going to CERC. Rumors say that all(?) Croatians will be present too. Some more countries for which one warm-up is not enough? (Don't miss the official CERC warm-up, starting one hour from now — link.)

All people, teams and countries are invited to participate. Though there are some small-ish prizes for top European teams! (that's why you can see a word "Europe" in the contest's name)

ACM rules apply. Binary scoring, 20 minutes, one computer per team, teams up to 3 members. To be more precise: a team can't use two computers at any moment of time. You can code in some different places though — you must communicate then e.g. using some chat (yes, you can use chat at the same time).

Finally, I want to mention all people involved in the preparation. For setting problems thanks and maybe praise go to: akulsareen, allllekssssa, dalex, desert97, k790alex, mexmans, asteri, nezametdinov, Sokolov, Xellos. For their patience: belowthebelt, raviojha2105. For writing the longest announcement in the world, for talking, and for testing things: Errichto. Finally, you will be provided editorials by pkacprzak — he is the next reason to participate because (as far as I know and read) he provides awesome editorials.

Btw. at least some of problems are nice in my humble opinion.

EDIT: We know about collisions but it's impossible to avoid them all. This date was the best possible choice.

HackerEarth will host the ACM ICPC Practice contest in the first half of November. You can remember the recent easier contest focused on Indian teams. This one will be focused on European teams and those can win small prizes. I am a coordinator and tester.

As you can guess by title, we are looking for problems, especially the hard ones. Write me PM and we will discuss your ideas (likely by gchat). Write problems in brief, no need to invent story now. You can propose one problem, you can propose 5 of them. No need to be experienced ;)

Cheers!

UPD: Thanks guys! No more proposals needed.

Sorry for long testing queues and timeouts. I hope it won't repeat.

Congratulations for the winners — tourist, Petr, Egor, and snuke. They managed to solve all three problems!

Thanks for helping Limak again. What do you think about problems? Feedback will be appreciated.

Div2

250, BearPaints — Iterate over one side of desired blue rectangle and in constant time calculate maximum possible second side. code

500, BearDartsDiv2 — Iterate over three numbers. For found value of a*b*c we must know how many times it occurs in some suffix of a sequence. We need an array or a map. code

1000, BearDestroysDiv2 — Dynamic programming with bitmasks, O(2^W·H·W). Iterate over cells in the given order (first row, then second row and so on) and consider all possible state of the next W + 1 cells. code

Div1

300, BearCries — Dynamic programming in O(N³). dp[i][A][B] where A is number of started emoticons already with at least one underscore (ready for being closed by second semicolon) and B is number of started emoticons with single semicolon only (without underscores). code

500, BearDarts — Rewrite given condition as t[a] / t[b] = t[d] / t[c]. Use map of pairs — irreducible fractions. code

900, BearDestroys — Problem would be easier with small W and big H. But it can be proved that we can consider Limak's walk in some other order, diagonal by diagonal:

1247..
358..
69..

Now we can use the same technique as in div2hard to get complexity O(2^H·H·W). code

Hello Codeforces Community!

I invite you to October Easy '15 on first day of October at 19:00 MSK. Contest will be of difficulty similar to div2 CF round. Will you manage to solve all 6 problems in 3 hours? Will anybody do it in 1 hour?

Problems will be given in random order. Each problem is worth 100 points but scoring is partial so try to pass as many tests as possible!

I want to thank Arjit Srivastava (belowthebelt) for his great help with HackerEarth's system and website. And big thanks go to Akul Sareen (akulsareen) — it was so nice to work with him. He is a tester and editorials' writer. I hope I will work again with these two guys.

Enjoy problems!