September 30, 2018 Single Round Match 738 Editorials

The round was held on 30th Sept, 2018. Thanks to wild_hamster for the interesting problem set and editorials. Thanks to Petr for recording his screen during the round. Click here to see Petr’s screencast of the round.

Div2Easy: DriveTheCarEasy

Increasing speed by speedi before the second momentsi leads to increase speed by speedi during S–momentsi+1 seconds. So for each pair speedi, momentsi we need to add S–momentsi+1 * speedi to the answer.
Code:

public class DriveTheCarEasy {
	public long calculateDistance(int S, int N, int[] speed_changes, int[] moments) {
		long ans = 0;
		for (int i = 0; i < N; i++)
			ans += (long)(S - moments[i] + 1) * speed_changes[i];
		return ans;
	}
	

Time complexity O(N).

Div2Medium: EnergySource

There can be at most 10^5 possible divisions under given constraints. We can generate all of them recursively. For each division, we can take every element not equal to 1 and try to split this element it into g > 1 new elements and go recursively to the new generated division if we didn’t already visit it recursively. Doing it straightforward will not fit in TL, so there are possible ways to fit in TL:
1. Precalculate all values from 1 to 90 inclusive.
2. Remember not all the elements of the division, but for each distinct element, we can remember the only number of occurrences of it in a division.
3. Precalculate divisors of each number from 1 to 90 and for each element in the division we can try to split it only in the number of divisors parts.
 

import java.util.*;
public class EnergySource {
	long ans1 = 0;
	long ans2 = 0;
	int itr = 0;
	ArrayList[] divisors = new ArrayList[105];
	ArrayList g = new ArrayList();
	HashSet f = new HashSet();
	int[] get_idx = new int[105];
	int[] cur_divisors = new int[105];
	long get() {
		int sz = g.size();
		long ans = 0, mul = 1;
		for (int i = sz-1; i>= 0; i--) {
			ans += mul*(g.get(i)+1);
			mul *= (cur_divisors[sz-i-1]+2);
		}
		return ans;
	}
	void go() {
		itr++;
	    	if (f.contains(get())) {
        		return;
		}
	    	f.add(get());
		ans1++;
		long cur = 1;
		for (int i = 1; i < g.size(); i++) {
			for (int j = 0; j < g.get(i); j++)
				cur *= cur_divisors[i];
		}
		ans2 += cur;
    		for (int i = 1; i < g.size(); i++) { if (g.get(i) > 0) {
            			for (int j = 1; j < divisors[cur_divisors[i]].size(); j++) {
					int cur_div = divisors[cur_divisors[i]].get(j);
                			int diff = cur_divisors[i]/cur_div;
			                g.set(get_idx, g.get(get_idx) + cur_div);
	                		g.set(i, g.get(i)-1);
			                go();
	                		g.set(i, g.get(i)+1);
                			g.set(get_idx, g.get(get_idx) - cur_div);
        	    		}
	        	}
    		}
	}
	void solve(int n) {
		for (int i = 1; i < divisors[n].size(); i++) {
			g.add(0);
		}
		g.add(1);
		for (int i = 0; i < divisors[n].size(); i++) {
		        get_idx[divisors[n].get(i)] = i;
		        cur_divisors[i] = divisors[n].get(i);
		}
		go();
	}
	public long[] countDifferentSources(int power) {
		for (int n = 1; n<= 100; n++) {
			divisors[n] = new ArrayList();
			for (int i = 1; i<= n; i++)
				if (n % i == 0) {
					divisors[n].add(i);
				}
		}
		solve(power);
		long[] ans = {ans1, ans2};
		System.out.println(f.size());
		return ans;
	}
}

Div2Hard: MovingByPoints

For any pair of points (x1, y1), (x2, y2) the minimal number of added points between them needed to get from one point to another not using another given points is equal to |x2–x1|+|y2–y1|–1.
Let¢s define every point as node of graph and make edge between any pair of points with distance equal to distance between points. After that we can use Dijkstra to find the shortest path between 1 and N.

public class MovingByPoints {
	int d[][] = new int[1005][];
	int w[] = new int[1005];
	int used[] = new int[1005];
	int Abs(int x) {
		return (x>0?x:-x);
	}
	public int countMinimumPoints(int N, int[] X, int[] Y) {
		for (int i = 0; i < N; i++)
			d[i] = new int[1005];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				d[i][j] = Math.max(0, Abs(X[j] - X[i]) + Abs(Y[j] - Y[i]) - 1);
		for (int i = 0; i < N; i++)
			w[i] = 1000000000;
		w[0] = 0;
		for (int i = 0; i < N; i++) {
			int min1 = 1000000000;
			int idx = -1;
			for (int j = 0; j < N; j++) {
				if (used[j] == 0 && w[j] < min1) {
					min1 = w[j];
					idx = j;
				}
			}
			used[idx] = 1;
			for (int j = 0; j < N; j++) {
				w[j] = Math.min(w[j], w[idx] + d[idx][j]);
			}
		}
		return w[N-1];
	}
	public String checkData(int N, int[] X, int[] Y) {
		if (N < 1 || N > 500) {
			return "N must be between 1 and 500, inclusive.";
		}
		if (X.length != N || Y.length != N) {
			return "X and Y must have exactly N elements.";
		}
		for (int i = 0; i < N; i++) {
			if (X[i] < 1 || X[i] > 1000000 || Y[i] < 1 || Y[i] > 1000000) {
				return "Each element of X and Y must be between 1 and 10^6, inclusive.";
			}
		}
		return "";
	}
}

Time complexity O(N^2)

Div1Easy: FindThePerfectTriangle

We can notice, that if one of the sides of the triangle will be irrational number, than perimeter will be irrational too. So we need to find all possible such vectors (vx, vy), where vx^2+vy^2 = k^2) (for some positive integer k £ P, vx and vy are integers). We will call such vectors good vectors.
There will be not many such vectors(not more than 10^4). We can construct two sides of the triangle using good vectors (vx1, vy1) and (vx2, vy2) on such set of points:
0, 0, vx1, vy1, vx1+vx2, vy1+vy2 ((vx1+vx2, vy1+vy2) must be also good vector).
In that way we can construct all possible triangles with integer coordinates, integer area and integer perimeter. After that we can check if (P, S) belongs to that possible triangles.

public class FindThePerfectTriangle {
	int[] a = new int[1005000];
	int[][] good = new int[1005][];
	int mx[] = new int[5005];
	int my[] = new int[5005];
	int segment_sz = 0;
	int Abs(int x) {
    		return (x>0?x:-x);
	}
	int S(int x1, int y1, int x2, int y2, int x3, int y3) {
    		int ans = (x1+x2)*(y1-y2)+(x2+x3)*(y2-y3)+(x3+x1)*(y3-y1);
	    	return Abs(ans);
	}
	public int[] constructTriangle(int area, int perimeter) {
		for (int i = 0; i <= 1000000; i++)
			a[i] = 0;
		for (int i = 1; i <= 1000; i++) {
			a[i*i] = i;
		}
		for (int i = 0; i <= 1000; i++) {
			good[i] = new int[1005];
			for (int j = 0; j <= 1000; j++) {
				good[i][j] = 0;
			}
		}
		for (int i = 0; i <= 1000; i++) {
			for (int j = 0; j <= 1000; j++) {
				int x = i*i + j*j;
				if (x <= 1000000 && a[x] > 0) {
					mx[segment_sz] = i;
					my[segment_sz] = j;
					good[i][j] = good[j][i] = a[x];
					segment_sz++;
				}
			}
		}
		for (int i = 0; i < segment_sz; i++) {
			for (int j = 0; j< segment_sz; j++) { int x1 = mx[i] + mx[j]; int y1 = my[i] + my[j]; int ar = S(0, 0, mx[i], my[i], x1, y1); if (ar > 0 && ar % 2 == 0 && x1 <= 1000 && y1 <= 1000 && good[x1][y1] > 0) {
					int P = good[mx[i]][my[i]] + good[mx[j]][my[j]] + good[x1][y1];
					if (P == perimeter && ar/2 == area) {
						int[] ans = {1, 1, mx[i]+1, my[i]+1, x1+1, y1+1};
						return ans;
					}
				}
				x1 = mx[i] - mx[j];
				y1 = my[i] + my[j];
				ar = S(0, 0, mx[i], my[i], x1, y1);
				if (ar > 0 && ar % 2 == 0 && Abs(x1) <= 1000 && y1 <= 1000 && good[Abs(x1)][y1] > 0) {
					int P = good[mx[i]][my[i]] + good[mx[j]][my[j]] + good[Abs(x1)][y1];
					if (P == perimeter && ar/2 == area) {
						int x = Math.max(1, -x1+1);
						int[] ans = {x, x, mx[i]+x, my[i]+x, x1+x, y1+x};
						return ans;
					}
				}
			}
		}
		int[] ans = {};
		return ans;
	}
	int find_int_dist(int x1, int y1, int x2, int y2) {
		int dist = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
		for (int i = 1; i <= 5000; i++) if (i*i == dist) return i; return -1; } boolean in_range(int x) { return (x >= 0 && x <= 3000);
	}
}

Div1Medium: LightBulbGame

As this is a combinatorial game and the state space is too large to solve it using brute force, we have to look for a more clever solution. One of the traditional tools that often works is the Sprague-Grundy theory that can be efficiently applied whenever the game can be split into a collection of independent smaller games.
The main challenge in this problem was to realize that this is indeed the case here. At the first glance, this is not obvious because it seems that the lightbulbs cannot be independent if you can sometimes
turn two of them off in one move.
Imagine that instead of lightbulbs we play the game with pebbles: add a pebble instead of turning the lightbulb on, and remove a pebble instead of turning it off. Then, “just turning lightbulb L off” is the same as “just removing the pebble from L”. I now claim that “turning off L and toggling L'” is equivalent to “moving a pebble
from L to L'”.
Why is that the case? If I turned L’ on, the equivalence is obvious. If I turned L’ off, I now have two different situations: in the lightbulb game the lightbulb is off, while in the pebble game I now have two pebbles at L’.
Why are these two situations equivalent? Because the two pebbles at the same location can safely be ignored, as if they weren¢t there. More precisely, imagine the two pebbles are not there and find out which player has the winning strategy. That player still has a winning strategy if we add those two pebbles back. Said strategy: follow the original strategy with the original pebbles, and copy your opponent’s moves on the two extra pebbles.
Thus, we can use simple dynamic programming to compute the Sprague-Grundy value for each lit lightbulb, xor them to get the Sprague-Grundy value of the entire board, and then we can examine all
possible first moves and evaluate each of them independently.

import java.util.*;
public class LightbulbGame {
    public int countWinningMoves(String[] board) {
        int R = board.length, C = board[0].length();
        int[][] SG = new int[R][C];
        for (int r=R-1; r>=0; --r) for (int c=C-1; c>=0; --c) {
            HashSet reachable = new HashSet();
            reachable.add(0);
            for (int nr=r+1; nr<R; ++nr) reachable.add( SG[nr] );
            for (int nc=c+1; nc<C; ++nc) reachable.add( SG[r][nc] );
            SG[r] = 0;
            while (reachable.contains(SG[r])) ++SG[r];
        }
        int sg = 0;
        for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) if (board[r].charAt(c) == '1') sg ^= SG[r];
        int answer = 0;
        for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) if (board[r].charAt(c) == '1') {
            int needed = sg ^ SG[r];
            if (needed == 0) ++answer;
            for (int nr=r+1; nr<R; ++nr) if (SG[nr] == needed) ++answer;
            for (int nc=c+1; nc<C; ++nc) if (SG[r][nc] == needed) ++answer;
        }
        return answer;
    }
}

Div1Hard: DriveTheCarHard

We can notice, that increasing speed before i-th second(0-indexed) by K meters/second leads to increasing passed distance in the end by (totalTime–i)*K.
So we have obvious dynamic programming solution with O(distance^2*log(distance)) time complexity:
let dp[distance][time] be optimal answer for time seconds and distance meters, then for each non-negative K we can update dp[time+1][distance+(time+1)*K] with min(dp[time+1][distance+(time+1)*K], dp[time][distance] + K^2).
But it is not fast enough under given constraints. So we can do following optimizations:
Let¢s define array a where a[i] means increasing speed by a[i] before second with number i.
We can notice that when (time+1)*time/2 ³ distance, we can construct an array of increasing speed for each second consisting only with zeros and ones that will lead to moving for exactly distance meters in time seconds.
After constructing it we can improve the amount of fuel greedily by trying to add 2 at the start of the array.
It can be proven that it is never optimal to add 3 for that case.
We can also observe that for time>= 261 and distance £ 30000 we can construct an array of increasing speed for each second consisting only with zeros and ones without even adding 2 to the array and calculate the answer as the number of ones in the array.
This is because:
1. You can always take a smaller value in the last iteration of the adding one to the array to produce the exact distance you need. That solution is clearly the optimal solution that only uses speedup by 1.
2. For these constraints you never need to increase your speed by more than 1. This is because for time ³ 261 even if you use the above greedy for distance = 30000, the three largest unused effects of a speedup by 1 will still be at least as large as the effect of changing the speedup at the beginning from 1 to 2.
Now we need to solve the problem for (time+1)*time/2 < distance. Let’s try to solve this problem in non-integer values:
If we need to move for distance meters in time seconds, the total distance travelled will be equal to
time*x1 + (time–1)*x2 + (time–2)*x3 + … + 1*xtime,
for time*x1 meters will be wasted x1^2 fuel, for (time–1)*x2 will be wasted x2^2 fuel and so on.
To minimize the amount of used fuel we need to maximize the amount of meters travelled for 1 unit of fuel. So we need to maximize values time/x1,
(time–1)/x2, (time–2)/x3, ¼, 1/xtime and they all must be equal.
 
We have x1 = time*x, x2 = (time–1)*x, ¼ ,xtime = 1*x, and x1*time + x2*(time–1) + ¼ + xtime*1 = distance, leading to x*(1^2+2^2+¼+time^2) = distance, and minimal amount of fuel is equal to x^2*(1^2+2^2+…+time^2) = distance^2/(1^2+…+time^2).
Now we can calculate this values for all distance £ 30000 and time £ 261 and compare it with dp[time][distance] counted in O(distance^2*log(distance)) and find out that the maximum difference is 30.
We also can get that for dp[time][distance] the optimal K taken in double value in dp[time–1][distance–K*time]+K*K is equal to x1 = time*x = 6*distance/((time+1)*(2*time+1)).
Values of dp[time–1][distance–K*time]+K*K in double values will be monotonous sequence on segments [K, +infinity) and (–infinity, K], so we can iterate K down and up in integer while dp[time–1][distance–K*time]+K*K will be not bigger than optimal_double_solution(time, distance) + 30 and it leads to less than 10^8 operations for distance £ 3*10^4.

public class DriveTheCarHard {
	int dp[][] = new int[305][];
	double calc(int i, int j) {
    		return (1.*j*j/(1.*(i)*(i+1)*(2*i+1)/6));
	}
	int solve_fast(int x, int y) {
   		for (int i = 1; i <= 30000; i++)
	        	dp[1][i] = i*i;
		for (int i = 2; i <= 250; i++)
		        for (int j = 1; j <= 30000; j++)
			            dp[i][j] = 1000000000;
    		int cnt = 0;
		for (int i = 2; i <= 250; i++) {
		        for (int j = 0; j <= 30000; j++) { double pre = calc(i,j); int optK = (int)(6.*j/(1.*(i+1)*(2*i+1))); for (int k = optK; j-k*i >= 0; k++) {
			                if (dp[i-1][j-k*i] + k*k < pre + 30) { dp[i][j] = Math.min(dp[i][j], dp[i-1][j-k*i] + k*k); } else { break; } } for (int k = optK; k >= 0; k--) {
			                if (dp[i-1][j-k*i] + k*k < pre + 30) { dp[i][j] = Math.min(dp[i][j], dp[i-1][j-k*i] + k*k); cnt++; } else { break; } } } } return dp[x][y]; } int solve_over_sqrt(int T, int D) { int cur_cnt = T; int[] ones = new int[1050]; int cur_sz = 0; while (D > 0) {
		        int val = Math.min(D, cur_cnt);
		        D -= val;
		        ones[cur_sz++] = val;
		        cur_cnt--;
	        }
		int ans = cur_sz;
		int pnt = 0;
		int left = 0;
		while (true) {
	        	if (cur_sz < 3) break; int sz = cur_sz; if (ones[pnt]+left >= ones[sz-1] + ones[sz-2] + ones[sz-3]) {
				left += ones[pnt];
		        } else {
			        break;
		        }
		        ans += 3;
		        while (ones[cur_sz-1] <= left) {
		        	left -= ones[cur_sz-1];
				cur_sz--;
			        ans--;
	        	}
	        	pnt++;
    		}
		return ans;
	}
	public int findMinimumFuel(int total_time, int distance) {
		for (int i = 0; i < 300; i++)
			dp[i] = new int[30500];
		if (total_time <= 250) {
			return solve_fast(total_time, distance);
		}
		return solve_over_sqrt(total_time, distance);
	}
};