Month: September 2015

SRM 669 Div1 250: Subdivided Slimes

After one turn, the maximum number of mascots that we can get is \lfloor S/2 \rfloor \cdot (S-\lfloor S/2 \rfloor). That suggest a greedy algorithm: In each step chose the largest slime, and divide it in two almost equal parts. Unfortunately this algorithm is wrong (it made me lose a lot of time trying to find a proof). Here is a counterexample: S=16, M=85 .

The next idea that I came up was that maybe there exists an optimal way of cutting the slimes such that after k turns, the resulting slimes are almost equal (Note that this is true for k=1).

Let’s think backwards. If after k turns the sizes of the slimes are q_0,q_1,...,q_{k} , then which is the maximum number of mascots that we can get? The process of cutting slimes determines a binary tree, the root is the initial slime, and the two children of a node are the resulting slimes after cutting that node. Let u,v be the left and right child of the root respectively, then [ max mascots from root = max mascots from u + max mascots from v + size of u * size of v ]. With that in mind you can prove that the maximum number of mascots that we can get is \sum_{i<j} q_i \cdot q_j

So the problem is how to divide S in many parts (S=q_0+q_1+...+q_k) such that the sum of the products of pairs is maximized. Let’s suppose that S=q_0+q_1+...+q_k is an optimum partition, if we increase q_i by one and decrease q_j also by one then the change in the number of mascots is q_j-q_i-1. That means that if we can find to elements a,b such that a<b+1 then we can improve that solution. Therefore, the optimum partition is when all the elements are almost the same (when the difference between the maximum and minimum is at most 1).

My awesome implementation:

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

class SubdividedSlimes {
	public:
	int needCut(int s, int m) {
      uli d[2000];
      uli ans=-1;
      for(int k=2;k<=s;k++){
         uli v=s;
         for(int i=0;i<k;i++){
            d[i]=v/(k-i);
            v-=d[i]; 
         }
         uli pets=0;
         uli maxi=d[k-1];
         for(int i=k-2;i>=0 && pets<m;i--){
            pets+=maxi*d[i];
            maxi=maxi+d[i];
         }
         if(pets>=m){
            ans=k-1;
            break;
         }
      }
      return ans;
	}
};

CodeRush 2015

Ranked first at CodeRush 2015 🙂

ranked first coderush

Here is my editorial:

Shinchan and Magical Water Buckets

If Shinchan can fill n buckets, then 1^2+2^2+...+n^2=n*(n+1)*(2*n+1)/6 \leq S
Since the amount needed to fill n buckets increases with n, then we can try to guess n using binary search.
My awesome implementation

Shinchan and Toggling Candles

The number of times that candle x is toggled is equal to the number of divisors of x.
If after the execution of the algorithm candle x is on, then x must have an odd number of divisors.
Let x=p_1^{e_1}*p_2^{e_2}*...*p_n^{e_n} be the prime decomposition of x, the number of divisors of x is d=(e_1 + 1) \cdot (e_2 + 1) \cdot \cdot \cdot (e_n + 1)  Since d is odd, all the exponents must be even, that implies that x must be a perfect square.
So the candles that are on on interval [L,R] are the candles of square indices i.e \lfloor\sqrt{R}\rfloor - \lfloor\sqrt{L-1}\rfloor

My awesome implementation

The Game Of Chess

This problem can be easily solved using dynamic programming.
We can completely determine a game state with a quatern (kx,ky,qx,qy) – the knight is on (kx,ky) and the queen is on (qx,qy) –
Let f[S] be 0 if in the game state S the player that starts always win the, and 1 otherwise.
That means that f[S]=0 if we can move one piece -a knight or a queen- and reach another state S' such that f[S']=1 .
The total number of states is small: 50^4=6250000 , so we can solve the problem for all states.
For each game state there are only two possibilities for the knight, but there are a lot of possibilities for the queen.

One way to solve the problem about the many possibilities of the queen is calculating another function diag[kx][ky][d] that determines if there is a position in which the second player to move wins when the knight is on (kx,ky) and queen is in one cell of diagonal d.
Simmilarly, we can define row[kx][ky][r] and col[kx][ky][c] for rows and columns respectively.

My awesome implementation

Stop not till you get enough
If we want to calculate a query f(x,y)=a_x+a_{x+y}+a_{x+2*y}+... we have to perform about \lfloor N/y \rfloor operations.
Given some y, in order to traverse all the array there should be y-1 queries (each which a different value of x%y).
So in the worst case they can ask for queries of the form (1,1), (1,2),(2,2), (1,3),(2,3),(3,3), ....
That implies that 1^2+2^2+...+t^2 \leq 300000 \rightarrow t \leq 800
We can solve all the queries in an offline way, first sort all the queries first by y descending and then by x ascending. Then use the naive algorithm for calculate the sum, until we arrive to the end of the array or until we arrive to a position that we have already calculated.

My awesome implementation