June 30, 2017 Single Round Match 715 Editorials

Hey Programmers!
Some of the SRM 715 Editorials are now published. Challenges to contribute to the rest of the editorials are still open. If you would like to contribute for an editorial for those problems you may do so by submitting to their respective challenges.
Thanks to Shizhouxing, marcose18 and samjia2000 for contributing to the SRM 715 Editorials. You may discuss the editorials in the match discussion forum.
SRM 715 Round 1 – Division II, Level One ImageCompression – by marcose18
In this problem, we can do exactly what the problem statement mentions. Iterate through all the k x k blocks, and for each block, we check if that block contains all ones or zeroes.
Java code:

public class ImageCompression {
   public boolean check(int startx, int starty, int k, char array[][]) {
       for (int i = startx; i < startx + k; i++) {
           for (int j = starty; j < starty + k; j++) {
               if (array[startx][starty] != array[i][j]) return false;
           }
       }
       return true;
   }
   public String isPossible(String[] image, int k) {
       char array[][] = new char[image.length][image[0].length()];
       for (int i = 0; i < image.length; i++) {
           for (int j = 0; j < image[0].length(); j++) {
               array[i][j] = image[i].charAt(j);
           }
       }
       boolean ans = true;
       for (int i = 0; i < image.length / k; i++) {
           for (int j = 0; j < image[0].length() / k; j++) {
               ans &= check(i * k, j * k, k, array);
           }
       }
       if (ans) return "Possible";
       return "Impossible";
   }
}

Single Round Match 715 Round 1 – Division II, Level Two MaximumRangeDiv2 – by Shizhouxing

We can solve the problem using dynamic programming.
Let dp[i][min][max][val] be whether we can reach a state where we have chosen a subsequence from the first i characters of the given string, and the smallest value is min, the largest value is max, and the current value is val. The DP value is true if we can reach the corresponding state.
The DP recurrence is simple. If dp[i][min][max][val] is true, we can choose to append the (i+1)-st character to our subsequence, or not. After that, we can get the new min, max, val, say new_min, new_max, new_val, so we set dp[i+1][new_min][new_max][new_val] to true.
Finally, choose (min, max, val) so that dp[|s|][min][max][val] is true and max-min is maximum. This max-min is exactly the maximal range that we want to find.
C++ code:

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define drep(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = ~0U >> 1;
const ll INF = ~0ULL >> 1;
int dp[2][120][120][120];
 
class MaximumRangeDiv2
{
public:
    int findMax(string s)
    {
        memset(dp, 0, sizeof(dp));
        dp[0][50][50][50] = true;
        for (int i = 0; i < s.size(); ++i) {
            int cur = i & 1, nxt = (i + 1) & 1;
            memset(dp[nxt], 0, sizeof(dp[nxt]));
            for (int min = -50; min <= 50; ++min)
                for (int max = -50; max <= 50; ++max)
                    for (int val = -50; val <= 50; ++val)
                        if (dp[cur][min + 50][max + 50][val + 50]) {
                            dp[nxt][min + 50][max + 50][val + 50] = true;
                            int nxt_val = val + ((s[i] == '+') ? 1 : -1);
                            int nxt_min = std::min(min, nxt_val);
                            int nxt_max = std::max(max, nxt_val);
                            dp[nxt][nxt_min + 50][nxt_max + 50][nxt_val + 50] = true;
                        }
        }
        int ans = 0;
        for (int min = -50; min <= 50; ++min)
            for (int max = -50; max <= 50; ++max)
                for (int val = -50; val <= 50; ++val)
                    if (dp[s.size() & 1][min + 50][max + 50][val + 50])
                        ans = std::max(ans, max - min);
        return ans;
    }
};

 
SRM 715 Round 1 – Division II, Level Three InPrePost – by samjia2000
Let’s write the following function:
bool possible(vector<int> a[], vector<string> modes)
where each of the {a[0], a[1], a[2]} is a tree traversal and and {modes[0], modes[1], and modes[2]} are their respective traversal modes (“pre”, “in”, or “post”) as described in the problem statement.
The function works as following:

• If the length of these three traversals are not all the same, the function returns false.
• If there is some node x which appears in one traversal but not in all three traversals, the function returns false.
• If there exist a pair of indices i and j (i ≠ j), where modes[i] == modes[j] but a[i] != a[j], it’s contradictory and therefore the function returns false.
• If all modes are the same, it means these traversals are all the same and there must be at least one solution, so the function returns true.
• Otherwise, we need to the root of the tree as described below.

Let’s observe this very important constraint from the problem statement:
You are guaranteed that among {s[0], s[2], s[4]} and also among {s[1], s[3], s[5]} each of the strings “pre”, “in”, and “post” appears exactly once.
Notice that in each step, the left subtrees will receive modes {s[0], s[2], s[4]}, and the right subtrees will receive modes {s[1], s[3], s[5]}. It means that in each step, modes will always contain “pre”, “in”, and “post”. This observation makes it easy to determine the root:

• the first element of a[i] for which modes[i] == “pre”, or equivalently
• the last element of a[i] for which modes[i] == “post”.

After figuring out the root, we have to split the tree into two parts: left subtree and the right subtree. We can do this by examining the i-th traversal for which modes[i] == “in” (again, there must be such i). All nodes that appear before the root in that travesal will go to the left, and all nodes that appear after the root in that traversal will go to the right.
Finally, all we need to do is to check if the subtrees are both valid simply by recursively calling possible() for both subtrees.
We can find the only root of the tree each time if the traversal is possible. Once x become the root of the tree, obviously it won’t be the root of its subtrees. Therefore we will call possible() at most N times. And it takes O(N) time per call to find the root. So, the time complexity is O(N^2).
My code is as follows. Note that for simplicity:

• I replace the first parameter (a) with w. The i-th traversal is denoted by the w[i][0] … w[i][1] elements of a[i].
• I replace “pre”, “in”, “post” with integers 0, 1, 2 for the second parameter (t, denoting the modes).

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<vector>
#include<map>
 
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long LL;
typedef double db;
const int N = 55;
int n;
vector <int> s[3];
vector <int> a[3];
int position[3][N];
int vis[N],tim;
class InPrePost{
    public:
    void resize(vector <int> *a,int v){
        fo(i,0,2)a[i].resize(v);
    }
    bool possible(vector <int> *w,vector <int> t){
        int len=w[0][1]-w[0][0]+1;
        fo(i,1,2)
        if (w[i][1]-w[i][0]+1!=len)return 0;
        if (len==0)return 1;
        tim++;
        fo(i,0,2)
            fo(j,w[i][0],w[i][1])
            if (vis[a[i][j]]<tim){
                vis[a[i][j]]=tim;
                len--;
            }
        if (len<0)return 0;
        fo(i,0,2)
            fo(j,i+1,2)
            if (t[i]==t[j]){
                fo(x,1,len)
                if (a[i][w[i][0]+x-1]!=a[j][w[j][0]+x-1])return 0;
            }
        if (t[0]==t[1]&&t[1]==t[2])return 1;
        int rt=0;
        fo(i,0,2){
            if (t[i]==0)rt=rt==0?a[i][w[i][0]]:(rt!=a[i][w[i][0]]?-1:rt);
            if (t[i]==2)rt=rt==0?a[i][w[i][1]]:(rt!=a[i][w[i][1]]?-1:rt);
        }
        if (rt==-1)return 0;
        vector<int> interval0[3],interval1[3],t0(4),t1(4);
        resize(interval0,3);resize(interval1,3);
        fo(i,0,2){
            t0[i]=s[t[i]][0];
            t1[i]=s[t[i]][1];
        }
        int l=0;
        fo(i,0,2)
        if (t[i]==1){
            l=position[i][rt]-w[i][0];
            interval0[i][0]=w[i][0];
            interval0[i][1]=position[i][rt]-1;
            interval1[i][0]=position[i][rt]+1;
            interval1[i][1]=w[i][1];
        }
        fo(i,0,2){
            if (t[i]==0){
                interval0[i][0]=w[i][0]+1;
                interval0[i][1]=w[i][0]+l;
                interval1[i][0]=w[i][0]+l+1;
                interval1[i][1]=w[i][1];
            }
            if (t[i]==2){
                interval0[i][0]=w[i][0];
                interval0[i][1]=w[i][0]+l-1;
                interval1[i][0]=w[i][0]+l
                interval1[i][1]=w[i][1]-1;
            }
        }
        bool v=possible(interval0,t0)&&possible(interval1,t1);
        return v;
    }
    string isPossible(vector <string> S, vector <int> A1, vector <int> A2, vector <int> A3){
        a[0]=A1;a[1]=A2;a[2]=A3;
        n=A1.size()-1;
        fo(i,0,2)
            fo(j,0,n)position[i][a[i][j]]=j;
        fo(i,0,5){
            if (S[i]=="pre")s[i/2].push_back(0);
            if (S[i]=="in")s[i/2].push_back(1);
            if (S[i]=="post")s[i/2].push_back(2);
        }
        vector<int>t(4);
        vector<int> w[3];
        w[0].resize(3);w[1].resize(3);w[2].resize(3);
        fo(i,0,2)t[i]=i;
        fo(i,0,2)w[i][0]=0,w[i][1]=n;
        if (possible(w,t))return "Possible";
        return "Impossible";
    }
};

SRM 715 Round 1 – Division I, Level One– MaximumRange – by marcose18
In this problem, it’s optimal to take either all ‘+’ or all ‘-’ to maximize the difference between the maximum and the minimum of X. Why? For example, after taking a ‘+’, then taking a ‘-’ will potentially reduce the result by 1 compared to taking ‘+’ immediately instead, as they both are going to cancel each other.
 

Java code:
public class MaximumRange {
   public int findMax(String str) {
       int ans = 0;
       for (int i = 0;i < str.length(); i++){
           if (str.charAt(i) == '+') ++ans;
       }
       return Math.max(ans, str.length() - ans);
   }
}

SRM 715 Round 1 – Division I, Level Two – ClassicalTowers – by Shizhouxing

Let’s first have a think of the shortest solution for a certain configuration. Obviously all disks will be moved to the rod which contains the disk with number n-1. Assume it’s the rod A. Then for other n-1 disks, let’s look at the disk with number n-2. If it’s also at rod A, we don’t need to do anything for this disk, we only need to consider other n-2 disks. Otherwise, assume it’s at the rod B. In order to move all disks to rod A, we need following steps: (1) move disks with number 0..n-3 to rod C; (2) move the disk n-2 to rod A; (3) move disks with number 0..n-3 to A. For step (2), we need one single move. For step (3), all disks that need to be moved are at the same rod at the beginning, this is the original Tower of Hanoi, we know that it needs 2^(n-2)-1 moves. So for step (2) and step(3), we need 2^(n-2) steps in total, the remaining problem becomes to move disks with number 0..n-3 to rod C.
Next we can use Dynamic Programming. Let dp[a][b][r] stands for we have a,b,c disks on rod A,B,C at the beginning respectively, and we need to move all disks to rod r. We have two choices for the disk with number (a+b+c-1):

1. If we put it at rod r, we’ll transfer to a state with a+b+c-1 disks where all disks should be also moved to rod r. In this case, the number of moves required doesn’t change.
2. If we put it at a different rod, say rod r’, we’ll transfer to a state with a+b+c-1 disks where all disks should be moved to another rod (i.e. not r nor r’). In this case, we need 2^(a+b+c-1) moves.

Here if k has 2^(a+b+c-1) in its binary representation, we should choose choice 2, otherwise we should choose choice 1. So that the total moves needed can add up to k.
We record our solution in dp at the same time. Finally, if there is an r that dp[0][0][0][r] has a solution, we have a solution for the problem. We can easily get the solution by going back to the state with a+b+c disks.
You may check out the code for more details.
Code

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define drep(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = ~0U >> 1;
const ll INF = ~0ULL >> 1;
int dp[60][60][60][3], n;
class ClassicTowers
{
public:
    string findTowers(long long k, vector <int> count)
    {
        n = count[0] + count[1] + count[2];
        memset(dp, -1, sizeof(dp));
        if (count[0]) dp[count[0]][count[1]][count[2]][0] = 0;
        if (count[1]) dp[count[0]][count[1]][count[2]][1] = 1;
        if (count[2]) dp[count[0]][count[1]][count[2]][2] = 2;
        if (k >= (1ll << n - 1)) return "";
        drep(i, n, 1) {
            rep(a, 0, count[0])
                rep(b, 0, count[1]) {
                    int c = i - a - b;
                    if (c < 0 || c > count[2]) continue;
                    int cur = bool((1ll << i - 1) & k);
                    if (cur) {
                        if (a && dp[a][b][1] != -1) dp[a - 1][b][2] = 0;
                        if (a && dp[a][b][2] != -1) dp[a - 1][b][1] = 0;
                        if (b && dp[a][b][0] != -1) dp[a][b - 1][2] = 1;
                        if (b && dp[a][b][2] != -1) dp[a][b - 1][0] = 1;
                        if (c && dp[a][b][0] != -1) dp[a][b][1] = 2;
                        if (c && dp[a][b][1] != -1) dp[a][b][0] = 2;
                    }
                    else {
                        if (a && dp[a][b][0] != -1) dp[a - 1][b][0] = 0;
                        if (b && dp[a][b][1] != -1) dp[a][b - 1][1] = 1;
                        if (c && dp[a][b][2] != -1) dp[a][b][2] = 2;
                    }
                }
        }
        rep(k, 0, 2)
            if (dp[0][0][0][k] != -1) {
                string ans = "";
                int a = 0, b = 0, c = 0;
                rep(i, 1, n) {
                    int cur = dp[a][b][k];
                    ans += cur+ 'A';
                    if (k != cur)
                        rep(kk, 0, 2)
                            if (kk != k && kk != cur) {
                                k = kk;
                                break;
                            }
                    if (cur == 0) ++a;
                    else if (cur == 1) ++b;
                    else ++c;                            
                }
                return ans;
            }
        return "";
    }
};