As the official editorial is promised to come out later, I will write an unofficial editorial for now. Some of the solutions are from my teammate tcmmichaelb139 orz. Contest: https://www.hackerrank.com/indigo-coding-competition
Easy
These problems are quite trivial, so I will only provide solutions:
n=int(input())
arr=[]
for i in range(n):arr.append(input().strip().replace('x',''))
for i in range(n):
cnt=arr[i].count('y')
arr[i]=arr[i].replace('y','')
arr[i]+=cnt*'y'
arr=sorted(arr,key=lambda x:(-len(x),x))
print('\n'.join(arr))
Michael's solution:
#include "bits/stdc++.h"
using namespace std;
string pi = "31415926535897932384626433832... (truncated copy-paste from internet)";
void solve() {
string s;
cin >> s;
for (int i = 0; i < s.length(); i++)
if (s[i] != pi[i]) {
cout << i << '\n';
return;
}
cout << s.length() << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
n=int(input())
b=int(input())
x=int(input())
y=int(input())
s=4*(n-1)*y+(n-2)*(n-2)*x
// there are 4(n-1) squares on the boundary as it is 4*n - 4 (overcounted squares)
// there are (n-2)*(n-2) squares on the interior as we exclude the boundaries so the side length is n-2
print(["Walter will like this lab","Sorry Mr. Fring, no can do"][s>b])
Michael did this one, but it looks like pain...
#include "bits/stdc++.h"
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
int a = 0, b = 0;
char cur = s[0];
int len = 1;
for (int i = 1; i < s.length(); i++) {
if (cur != s[i]) {
if (len >= 3) {
if (cur == '<')
a -= 20 + (len - 3) * 5;
else if (cur == '>')
a += 20 + (len - 3) * 5;
else if (cur == 'v')
b -= 20 + (len - 3) * 5;
else if (cur == '^')
b += 20 + (len - 3) * 5;
} else {
if (cur == '<')
a -= 2 * len;
else if (cur == '>')
a += 2 * len;
else if (cur == 'v')
b -= 2 * len;
else if (cur == '^')
b += 2 * len;
}
len = 1;
cur = s[i];
} else {
len++;
}
}
if (len >= 3) {
if (cur == '<')
a -= 20 + (len - 3) * 5;
else if (cur == '>')
a += 20 + (len - 3) * 5;
else if (cur == 'v')
b -= 20 + (len - 3) * 5;
else if (cur == '^')
b += 20 + (len - 3) * 5;
} else {
if (cur == '<')
a -= 2 * len;
else if (cur == '>')
a += 2 * len;
else if (cur == 'v')
b -= 2 * len;
else if (cur == '^')
b += 2 * len;
}
cout << "(" << a << "," << b << ")" << '\n';
}
Medium
Explanation coming soon.........
n=int(input())
a=[0]+[int(x)for x in input().split()]
b=0
for i in range(1,n+1):
b+=max(a[i]-a[i-1],0)
print(b)
DFS through the tree, keeping track of time. Keep track of the node with max time and then size as tiebreaker.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <vector>
#include <algorithm>
using namespace std;
int lastlay=-1;
int lastnode=-1;
vector<vector<int>> adj(1000);
void dfs(int v,int p,int lay){
if(lay>lastlay)lastlay=lay,lastnode=v;
else if(lay==lastlay&&v>lastnode)lastnode=v;
for (auto&x:adj[v])if(x!=p)dfs(x,v,lay+1);
}
int main()
{
int r, n; scanf("%d %d", &r, &n);
r--;
for (int i=0;i<n;i++){int u,v;scanf("%d %d",&u,&v);
u--;v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (auto&v:adj)sort(v.begin(),v.end());
dfs(r,r,0);
printf("%d\n",lastnode+1);
}
Michael did this one, so my explanation might not be great. Just brute force while keeping track of visited letters in O(3^26) time. Since the testcases are random, the average time is a lot less, so brute force works.
#include "bits/stdc++.h"
using namespace std;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, m;
vector<string> v;
int ans = 0;
void dfs(int x, int y, vector<int> vis, int done) {
ans = max(ans, done);
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (vis[v[nx][ny] - 'A']) continue;
vector<int> vis2 = vis;
vis2[v[nx][ny] - 'A'] = true;
dfs(nx, ny, vis2, done + 1);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
v.push_back(s);
}
vector<int> vis(27, false);
vis[v[0][0] - 'A'] = true;
dfs(0, 0, vis, 1);
cout << ans << '\n';
}
Use dp: dp[i][j] represents # of ways to create a parenthesis sequence up to index i with j extra left parenthesis (
If you are on a (: Add dp[i][j] to dp[i+1][j+1]
If you are on a ): Add dp[i][j] to dp[i+1][j-1] if j>0
If you are on a B's turn or a ?: Do both
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b) { return (a + b) % MOD; }
int dp[4001][4001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
string s;
cin >> n >> s;
if (s[0] == ')') {
cout << 0 << '\n';
return 0;
}
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (int i = 0; i < n * 2; i++) {
for (int j = 0; j < n * 2; j++) {
if (i & 1) {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
} else {
if (s[i / 2] == ')') {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
} else if (s[i / 2] == '(')
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
else if (s[i / 2] == '?') {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
} else
assert(false);
}
}
}
cout << dp[2 * n][0] << '\n';
}
Hard
This one was fun. We claim that the solution is the same as the previous one pretending that {}[] is the same as (), multiplied by 3 to the power of the # of ?s.
Proof:
First, we can prove that each symbol in A will map to a symbol in B. This is because symbols in A cannot match to other symbols in A, because there are an odd # of symbols in between.
Let us further suppose that there are no ?s. Then, there is a bijection from sequences containing only () restricted by A to sequences containing ()[]{} that are restricted by A because you can change the character (and its matching character in B) back to the original.
For example:
A = ({])}
simplified A = (()))
possible sequence = (((()())))
constrained by original A ({{[]()}})
Each ? means that we have 3x the possibilty for that character ([{ so we multiply by 3^# of ?s.
This is just Michael's code for P8 but modified by me.
// thx michael orz
#include "bits/stdc++.h"
using namespace std;
const ll mod = 1e9 + 7;
ll add(ll a, ll b) { return (a + b) % mod; }
ll dp[4001][4001];
ll binpow(ll x,ll p){
ll r=1,sq=x;
while(p){
if(p&1)r=r*sq%mod;
sq=sq*sq%mod;p>>=1;
}
return r;
}
ll main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
string s;
cin >> n >> s;
if (s[0] == ')') {
cout << 0 << '\n';
return 0;
}
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (ll i = 0; i < n * 2; i++) {
for (ll j = 0; j < n * 2; j++) {
if (i & 1) {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
} else {
if (s[i / 2] == ')'||s[i / 2] == '}'||s[i / 2] == ']') {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
} else if (s[i / 2] == '('||s[i / 2] == '['||s[i / 2] == '{')
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
else if (s[i / 2] == '?') {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
} else
assert(false);
}
}
}
ll wild=0;
for (auto x:s)if(x=='?')wild++;
cout << 1ll*dp[2 * n][0]*binpow(3,wild)%mod << '\n';
}
My favorite problem :) Honestly easier than P9.
Different bounds for rows and columns motivate going through by rows (we assume rows have the smaller of the two dimensions) Note that (by a brute force) there are only 60 valid possibilities for a row. Thus, we can represent bitmasks as numbers between 1-60.
We use bitmask dp: dp[row][mask][mask2] represents the max # of haybales you can get if you are at row i, the current row's haybales are mask2, and the previous row's haybales are mask. Then dp[row][mask][mask2] = max(dp[row-1][pmask][mask] + 1) over all compatible pmasks (compatible meaning that their bits are distinct).
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <vector>
using namespace std;
#define pcnt __builtin_popcount
#define cnt(x) pcnt(tom(x))
int tom(int x) {
switch(x) {
case 0: return 0;case 1: return 1;case 2: return 2;case 3: return 4;case 4: return 8;case 5: return 9;case 6: return 16;case 7: return 17;case 8: return 18;case 9: return 32;case 10: return 33;case 11: return 34;case 12: return 36;case 13: return 64;case 14: return 65;case 15: return 66;case 16: return 68;case 17: return 72;case 18: return 73;case 19: return 128;case 20: return 129;case 21: return 130;case 22: return 132;case 23: return 136;case 24: return 137;case 25: return 144;case 26: return 145;case 27: return 146;case 28: return 256;case 29: return 257;case 30: return 258;case 31: return 260;case 32: return 264;case 33: return 265;case 34: return 272;case 35: return 273;case 36: return 274;case 37: return 288;case 38: return 289;case 39: return 290;case 40: return 292;case 41: return 512;case 42: return 513;case 43: return 514;case 44: return 516;case 45: return 520;case 46: return 521;case 47: return 528;case 48: return 529;case 49: return 530;case 50: return 544;case 51: return 545;case 52: return 546;case 53: return 548;case 54: return 576;case 55: return 577;case 56: return 578;case 57: return 580;case 58: return 584;case 59: return 585;
}
return 99;
}
int compat(int m1,int m2,int m3) {
return pcnt(m1|m2|m3)==pcnt(m1)+pcnt(m2)+pcnt(m3);
}
int main()
{
int n, m; scanf("%d%d",&n,&m);
vector<int>mp(n);
for (int i=0;i<n;i++)for(int j=0;j<m;j++){char x;scanf(" %c",&x);
if(x=='D')mp[i]|=1<<j;
}
for(int i=0;i<n;i++)mp[i]=~mp[i];
if(n == 1) {
int mx=0;
for (int j=0; j<60; j++) {
if(tom(j) & mp[0]) continue;
mx=max(mx,cnt(j));
}
printf("%d\n",mx);
return 0;
}
vector<vector<vector<int>>> dp(n,vector<vector<int>>(60,vector<int>(60)));
for (int j=0; j<60; j++) {
for (int k=0;k<60;k++) {
if(tom(j)&mp[0])continue;
if(tom(k)&mp[1])continue;
if(!compat(0,tom(j),tom(k)))continue;
dp[1][j][k] = cnt(j)+cnt(k);
}
}
for (int i=2; i<n; i++) {
for (int j=0; j<60; j++) {
for (int k=0;k<60;k++) {
if(dp[i-1][j][k]==0)continue;
// printf("dp[%d][%d][%d] = %d\n",i-1,j,k,dp[i-1][j][k]);
for (int x=0;x<60;x++) {
if(tom(x)&mp[i])continue;
if(!compat(tom(j),tom(k),tom(x)))continue;
dp[i][k][x] = max(dp[i][k][x],dp[i-1][j][k] + cnt(x));
// printf("\t=> dp[%d][%d][%d] = %d\n",i,k,x,dp[i-1][j][k]+cnt(x));
}
}
}
}
int mx=0;
for (int j=0;j<60;j++)for(int k=0;k<60;k++)mx=max(mx,dp[n-1][j][k]);
printf("%d\n",mx);
}
:o slay
I wrote my own editorial as well, which builds on your observations while making everything more detailed.
It can be found here
Shout out to Bakry for helping me understand the approach behind problem 9.