# Codeforces Round #378 Div. 2 review

## A. Grasshopper And the String

• Category: Implementation

Even this is a first problem, I get wrong answer for first time submission. It is necessary to consider a corner case at the “end of the text”.

Some other solution is inserting extra ‘A’ at the end of text so that you can handle it in the same way. (ex. latte0119’s solution)

/*
* Accepted	15 ms	0 KB
*
* Need to take care the corner case at the end - '\0' works similarly with the vowels.
*/
#include <cstdio>
#include <iostream>

using namespace std;

char s[105];

int main(){
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
scanf("%s", s);
int tmp = 0;
int ability = 0;
for (int i = 0; i < 105; ++i) {
tmp++;
if (s[i] == 'A' || s[i] == 'I' || s[i] == 'U' || s[i] == 'E' || s[i] == 'O' || s[i] == 'Y'
|| s[i] == '\0') {
ability  = max(ability, tmp);
tmp = 0;
if (s[i] == '\0') break;
}
}

printf("%d\n", ability);
return 0;
}

Below implementation is a little bit optimized solution for not to use memory of $$O(N)$$, but use $$O(1)$$. But in the contest, it is better to consider solve it as fast as possible rather than optimize too much.
/*
* Accepted	31 ms	0 KB
*/
#include <cstdio>
#include <iostream>

using namespace std;

int main(){
#ifndef ONLINE_JUDGE
freopen("b3.in", "r", stdin);
#endif
int n;
scanf("%d", &n);

int maxb = 0, minb = 0;
int maxIndex = -1, minIndex = -1;
int B = 0; // total

for (int i = 0; i < n; ++i) {
int l, r;
scanf("%d %d", &l, &r);
int tmpb = l - r;
if (tmpb > maxb) { maxb = tmpb; maxIndex = i; }
if (tmpb < minb) { minb = tmpb; minIndex = i;}
B += tmpb;
}
int ans = 0;
int maxB = abs(B);
if (maxB < abs(B-2*maxb)) { maxB = abs(B-2*maxb); ans = maxIndex+1; }
if (maxB < abs(B-2*minb)) { maxB = abs(B-2*minb); ans = minIndex+1; }

printf("%d\n", ans);
return 0;
}

## C. Epidemic in Monstropolis

When we compare the sequence of $$a$$ and $$b$$, we notice that $$b_1$$ is made of the group from $$a_1$$ to $$a_{k_1}$$, $$b_2$$ is made of the group from $$a_{k_1+1}$$ to $$a_{k_2}$$, and so on. So we can just check it can be done or not with greedy algorithm.

The implementation amount is big, so it is difficult to solve it in time for me.

/*
* Accepted	15 ms	0 KB
*/
#include <cstdio>
#include <iostream>
#include <list>

using namespace std;

int a[505];
int b[505];

int x[505]; // index #of the monster eat
char direction[505]; // eat direction

int main(){
#ifndef ONLINE_JUDGE
freopen("c2.in", "r", stdin);
#endif
int n, k;
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
scanf("%d", &k);
for (int i = 0; i < k; ++i) scanf("%d", &b[i]);

int scanAL = 0, scanA = 0, scanB = 0;
int action = 0;

int A = 0;
bool possible = true;

while (scanA != n && scanB != k) {
A += a[scanA];
if (A == b[scanB]) {
int maxA = 0;
int winner = -1;
bool left = false; // start to eat from left.

for (int i = scanAL; i <= scanA; ++i) {
maxA = max(maxA, a[i]);
}

if (scanAL == scanA) {
// corner case: if already only 1 winner exists in this group
// do nothing
} else {
for (int i = scanAL; i <= scanA; ++i) {
if (a[i] == maxA) {
//cout << "maxA " << maxA << ", a[i] " << a[i] << endl;
if (i != scanAL && a[i-1] < a[i]) {
winner = i - scanAL;
left = true;
break;
} else if (i != scanA && a[i+1] < a[i]) {
winner = i - scanAL;
left = false;
break;
}
}
}

if (winner == -1) {
possible = false;
break;
} else {
for (int i = 0; i < scanA - scanAL; ++i) {
// winner eat all the other monsters.
if (winner > 0 && left) {
// eat L
x[action] = scanB + winner + 1;
direction[action] = 'L';
action++;

winner--;
} else {
// eat R
x[action] = scanB + winner + 1;
direction[action] = 'R';
action++;
left = true;// now possible to eat left monster
}
//cout << "scanB: " << scanB << " " << "winner: " << winner << endl;
}
}
}

scanAL = scanA+1;
scanB++;
A = 0;
} else if (A > b[scanB]) {
// impossible
possible = false;
break;
}
scanA++;
}
if (scanA != n || scanB != k) possible = false;

if (possible) {
printf("YES\n");
for (int i = 0; i < n - k; ++i) {
printf("%d %c\n", x[i], direction[i]);
}
} else {
printf("NO\n");
}
return 0;
}

## D. Kostya the Sculptor

• Category: data structures – use map, normalized representaion.

Since this problem restricts to consider only 1 or 2 parallelepipe combination, we can check all the posibility. To check 2 parallelepipe combination, it takes $$O(n^2)$$ with straight-forward implementation, but by using map we can reduce the search time and it can be done in $$O(nlog(n))$$ time.

map‘s key must be comparable, so I used pair<int, int>.

/*
* Accepted	264 ms	11800 KB
*
* O(n log(n))
*/
#include <cstdio>
#include <iostream>
#include <map>

using namespace std;

typedef pair<int, int> P;
map<P, P> stoneMap; // key (1, 2): edge 1 and edge 2. value (first, second): 1st = edge 3, 2nd = index.

int ansNum = 0;
int ans1 = 0, ans2 = 0;
int maxR = 0;

P make_normalized_pair(int a, int b) {
if (a <= b) return make_pair(a, b);
else return make_pair(b, a);
}

void check_combination(int a, int b, int c, int i) {
auto it = stoneMap.find(make_normalized_pair(a,b));
if (it != stoneMap.end()) {
P key = it->first;
P value = it->second;

// key.first <= key.second always, no need to check key.second
int r = min(key.first, value.first + c);
if (maxR < r) {
maxR = r;
ansNum = 2;
ans1 = value.second;
ans2 = i;
}
if (value.first < c) stoneMap[make_normalized_pair(a,b)] = make_pair(c, i);  // update this map
stoneMap[make_normalized_pair(a,b)] = make_pair(c, i);
}
}

int main(){
#ifndef ONLINE_JUDGE
freopen("d2.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
int a, b, c;

for (int i = 1; i <= n; ++i) {
scanf("%d %d %d", &a, &b, &c);
int r = min(min(a, b), c);

// check this parallelepiped
if (maxR < r) {
maxR = r;
ansNum = 1;
ans1 = i;
}
// check 2 combination
check_combination(a, b, c, i);
check_combination(b, c, a, i);
check_combination(c, a, b, i);
}

printf("%d\n", ansNum);
if (ansNum == 1) {
printf("%d\n", ans1);
} else {
printf("%d %d\n", ans1, ans2);
}

return 0;
}