Single Round Match 726 Editorials

By in Community Stories February 7, 2018

Some of the SRM 726 Editorials are now published. Thanks to OB3LISK , nitish_ and square1001 for contributing to the editorials. If you wish to discuss the problems or editorials you may do it in the discussion forum here.

SRM 726 Round 1 – Division II, Level One – StringHalving  –  by OB3LISK

In this problem, we have a string where each letter appears exactly twice, and we want to remove the duplicate letters in such a way that the first letter is lexicographically smallest.

A naive approach is to generate all possible ways of removing the duplicate letters and check which of those ways has the smallest beginning letter. But that’s not necessary.

Notice that, for our string, we’re only interested in the characters that can appear in beginning of the string. For a character to appear in the beginning of a string, it must appear before every other character and its duplicate both appear. For example:

abcddeeabc

When we consider the above string, a, b, c, and d can all be characters that appear at the beginning of the string after we remove duplicates. The reason that ‘e’ can’t be chosen is because ‘d’ shows up twice before ‘e’ does. That means no matter which ‘d’ is removed, it will appear before any ‘e’s can show up.

So now we know that to solve our problem, we just need to find which characters appear in the string before any other character has its duplicate show up. Then, we can choose the smallest character from that set as our answer.

To solve this problem, we’re going to make use of a frequency array. We create an array where each index represents a character. For example, index 0 represents ‘a’, index 1 represents ‘b’, and index 25 represents ‘z’. Inside of each of these indices will be a number that represents the number of times we see a particular character.

For this problem, we’ll look at each character in the string, from left to right, updating our frequency array as we go, and once we find a frequency of 2 for any character, we know that we can only choose a letter from the letters we’ve visited before. We then check our frequency array for the letters we’ve seen to find which letter was the smallest, and return that as our answer.

The time complexity for this solution is O(N) (specifically O(N/2 + 1) ), since at worst we have to check half of the letters in our string until we find the duplicate. The space complexity is O(1), since the only extra space we use is a frequency array to represent the count of 26 characters.

Code:

[cpp]
#include<iostream>
#include<string>
using namespace std;

class StringHalving
{
public:
string lexsmallest(string);
};

string StringHalving::lexsmallest(string s)
{
string answer = ""; // The string that we return.

// Create a frequency array for each character we see.
// For example, ‘a’ = index 0, and if it shows up 3 times
// then freq[0] = 3;
int freq[26] = {0}; // Initialize each index to 0.

// Go through each character in our string and mark our frequency array.
for(int i = 0; i < s.length(); i++)
{
char c = s[i];
freq[c-‘a’] += 1;
// If we find a duplicate (since the letter shows up twice now). Stop checking letters.
if(freq[c-‘a’] == 2)
{
break;
}
}

// Find which of the letters we found so far is the "smallest".
for(int i = 0; i < 26; i++)
{
char c = ‘a’ + i;
// The first letter we find based on our indexing (‘a’ = 0 is lowest, 1 is next lowest, etc.)
// is going to be our best answer.
if(freq[i] > 0)
{
answer = c;
break;
}
}

return answer;
}
[/cpp]

(Notice the useful indexing trick used in the code.
‘a’ – ‘a’ = 0
‘b’ – ‘a’ = 1
‘z’ – ‘a’ = 25
You can easily get the correct index by simply subtracting char variables.)


SRM 726 Round 1 – Division II, Level Two – TurtleGame   –  by nitish_

Given a n x m matrix, and the constraint that a player can move only either down side or right side, the length of the turtle friendly path is fixed, which is (n+m-1).

It is given that the board is initially at a turtle friendly path. Because they are playing optimally, we can fix these (n+m-1) blocks and remove everything else. Therefore, if the difference between the number of available blocks and (n+m-1) is Odd, then we return ‘Win’ else ‘Lose’.

Complexity is O(n*m).

C++ Code:

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

class TurtleGame {
public:
string getwinner(vector <string> board) {
int valid_moves = 0,n = board.size(),m = board[0].length() ;
for(int i =0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
if(board[i][j] == ‘.’) ++valid_moves;
}
int diff = valid_moves – (n+m-1);
if(diff&1)
return "Win";
else
return "Lose";
}
};

[/cpp]


SRM 726 Round 1 – Division II, Level Three – HeroicScheduled2  –  by nitish_

The problem statement says that you have to find the count of all the possible schedules that can take place. The solution to this problem is greedy + dynamic programming.

First, it is wise to first choose a task to do whose deadline is closer. Thus, we will be able to do more number of tasks.

So, sort the schedules based on the finish time of each schedule.

The state of DP will be {index of schedule, bitmask which tracks which day has been used till now}.

Thus, if we can find a day vacant between the start[i] and finish[i], then we can schedule that task that day. Or, we can skip that task without scheduling that. Both of the cases increase result by 1.

Complexity: O(N*M), where N = number of tasks and M = 216 (bitmask).

C++ code:

[cpp]
#include <bits/stdc++.h>
using namespace std;
#define ll long long

class HeroicScheduled2 {
public:
int N;
vector <pair<int,int> >S;
ll DP[60][1<<16];

ll f(int idx, int mask)
{
if(idx == N)
return 1;
if(DP[idx][mask] != -1)
return DP[idx][mask];
ll res = 0;
res += f(idx+1, mask);
for(int i =S[idx].second; i <= S[idx].first; ++i)
{
if(!(mask&(1<<i)))
{
res += f(idx+1, mask|(1<<i));
break;
}
}

return DP[idx][mask] = res;
}

long long getcount(vector <int> start, vector <int> finish) {
memset(DP, -1, sizeof DP);
for(int i =0; i < start.size(); ++i)
S.push_back({finish[i], start[i]});
sort(S.begin(), S.end());
N = finish.size();
ll ans = f(0,0);
return ans;
}
};
[/cpp]


SRM 726 Round 1 – Division I, Level One – Unpacking  –  by square1001

Simple Explanation of Problem
There are N boxes which contains red and blue candies. The i-th box has three values: a[i], b[i], and cost[i]. It means, to buy i-th box costs cost[i], and (number of red candies, number of blue candies) = (a[i], b[i]), (a[i]+1, b[i]–1), or (a[i]–1, b[i]+1) are possible. What is the minimum cost if you want to guarantee that you can get at least K candies of same color? If you cannot guarantee even if you buy any set of boxes, answer -1 instead. You can assume, 1 ≤ N ≤ 50, and 1 ≤ a[i], b[i], K ≤ 10000.

Solution and Approach
First, the problem seems complicated. So, let’s think about the following problem instead: “if you buy all boxes, can you guarantee that you can get at least K candies of same color?” Actually, it’s not so hard. You can guarantee that you can get at least K candies if and only if it satisfies one of the three following condition:
1. The sum of a[i]-1 is at least K.
2. The sum of b[i]-1 is at least K.
3. The sum of a[i]+b[i] is at least 2K-1.

You can prove easily if you take following process. First, take a[i]-1 red candies and b[i]-1 blue candies from each box. Now, there are 2 candies remaining in each box and any color configuration is possible. Then, take all the remaining 2N candies to empty the boxes. Now, for any pair of non-negative integers (x, y) that satisfies x + y = 2N, “you took (sum of a[i]-1)+x red candies and (sum of b[i]-1)+y blue candies” is possible. If you solve the inequalities over the integers, 0≤x≤2N, (sum of a[i]-1)+x<K, (sum of b[i]-1)+(2N-x)<K simultaneously, the answer is “(the sum of a[i]-1)<K and (the sum of b[i]-1)<K and (the sum of a[i]+b[i])≤2K-2”. Therefore, you can guarantee that you can get at least K candies if and only if it satisfies one of the condition a, b, or c.

Now the problem became simple. You can take the minimum value of “what is the minimal cost subset of boxes that the sum of a-1 is at least K?”, “what is the minimal cost subset of boxes that the sum of b-1 is at least K?”, and “what is the minimal cost subset of boxes that the sum of a+b is at least 2K-1?”. All three problem has the same form: “There are N non-negative integers v[0], v[1],…, v[N-1]. Selecting value v[i] costs c[i]. What is the minimum cost of taking integers so that sum of integers is at least K?” (let’s call this “sub-problem”).

You can easily solve with knapsack-like dynamic programming. Therefore, you can solve in O(NK) and it runs much quicker than time limit.

Time Complexity: O(NK)
Memory Complexity: O(NK), and it can be reduced to O(N+K)

Useful Concepts
If you don’t know about dynamic programming, I suggest reading a Topcoder data science tutorial, Dynamic Programming: From Novice to Advanced.

C++ code:

[cpp]
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
class Unpacking {
public:
int solve(vector<int> v, vector<int> c, int K) {
int N = v.size();
vector<vector<int> > dp(N + 1, vector<int>(K + 1));
fill(dp[0].begin() + 1, dp[0].end(), inf);
dp[0][0] = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= K; j++) dp[i + 1][j] = dp[i][j];
for (int j = 0; j <= K; j++) dp[i + 1][min(j + v[i], K)] = min(dp[i + 1][min(j + v[i], K)], dp[i][j] + c[i]);
}
return dp[N][K];
}
int getcost(vector<int> a, vector<int> b, vector<int> cost, int K) {
int N = a.size();
vector<int> v1(N), v2(N), v3(N);
for (int i = 0; i < N; i++) {
v1[i] = a[i] – 1;
v2[i] = b[i] – 1;
v3[i] = a[i] + b[i];
}
int ret = min({ solve(v1, cost, K), solve(v2, cost, K), solve(v3, cost, 2 * K – 1) });
return ret == inf ? -1 : ret;
}
};
[/cpp]