Problems
Problems can be downloaded here.
You can also submit your code to the official judge on the archived contest site here.
Solutions
Rectangle
We find the x-coordinate and y-coordinate of the fourth point separately. Observe that for any rectangle with sides parallel to the x and y axes, the corners can be split into two pairs, each pair with the same x-coordinate. We have the x-coordinates of three points, with two of them being the same. The fourth point’s x-coordinate is the x-coordinate which is different. We can find the y-coordinate analogously.
Python 3
def fourth(c1, c2, c3):
"""Returns the fourth coordinate given three others."""
if c1 == c2:
return c3
elif c1 == c3:
return c2
else:
return c1
x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())
x4 = fourth(x1, x2, x3)
y4 = fourth(y1, y2, y3)
print(x4, y4)
C++
#include <iostream>
using namespace std;
int main() {
int x[3], y[3];
for (int i = 0; i < 3; i++) {
cin >> x[i] >> y[i];
}
int ans_x, ans_y;
if (x[0] == x[1]) ans_x = x[2];
else if (x[0] == x[2]) ans_x = x[1];
else ans_x = x[0];
if (y[0] == y[1]) ans_y = y[2];
else if (y[0] == y[2]) ans_y = y[1];
else ans_y = y[0];
cout << ans_x << " " << ans_y << '\n';
return 0;
}
Complete the Equation
We can try all permutations of operators which are allowed. There are only 8 cases to consider, which we can enumerate by hand. We can further reduce to 6 cases by observing that a=b+c is equivalent to a-b=c, and a=b*c is equivalent to a/b=c – however, this is not necessary.
Python 3
a, b, c = map(int, input().split())
if a == b + c:
op1 = '='
op2 = '+'
elif a == b - c:
op1 = '='
op2 = '-'
elif a == b * c:
op1 = '='
op2 = '*'
elif a == b / c:
op1 = '='
op2 = '/'
elif a + b == c:
op1 = '+'
op2 = '='
elif a - b == c:
op1 = '-'
op2 = '='
elif a * b == c:
op1 = '*'
op2 = '='
elif a / b == c:
op1 = '/'
op2 = '='
else:
raise Exception('No valid equation found.')
print(str(a) + op1 + str(b) + op2 + str(c))
C++
#include <bits/stdc++.h>
int a,b,c;
int main() {
scanf("%d %d %d", &a, &b, &c);
if(a+b==c) {
printf("%d+%d=%d\n", a, b, c);
} else if (a-b==c) {
printf("%d-%d=%d\n", a, b, c);
} else if (a*b==c) {
printf("%d*%d=%d\n", a, b, c);
} else if (a/b==c) {
printf("%d/%d=%d\n", a, b, c);
} else if (a==b+c) {
printf("%d=%d+%d\n", a, b, c);
} else if (a==b-c) {
printf("%d=%d-%d\n", a, b, c);
} else if (a==b*c) {
printf("%d=%d*%d\n", a, b, c);
} else if (a==b/c) {
printf("%d=%d/%d\n", a, b, c);
} else {
printf("NO VALID EQUATION FOUND\n");
}
}
Bahasa F
We can do as the task statement says – the tricky part is the implementation.
Python 3
def f(s):
"""Returns the translation of syllable s in Bahasa F."""
c = first_consonant(s)
f_s = s.replace(c, 'f', 1) if c else 'f' + s
return s + f_s
def first_consonant(s):
"""Returns the first consonant (if exist) in syllable s."""
consonants = 'bcdfghjklmnpqrstvwxyz'
for c in s:
if c in consonants:
return c
words = input().split()
for i in range(len(words)):
word = words[i]
syllables = word.split('/')
for j in range(len(syllables)):
syllable = syllables[j]
syllables[j] = f(syllable)
words[i] = "".join(syllables)
print(" ".join(words))
C++
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main() {
string S;
getline(cin, S);
string syllable, answer;
S += '/';
int consonant = -1;
for (int i = 0; i < S.size(); i++) {
if (S[i] == '/' || S[i] == ' ') {
answer += syllable;
if (consonant == -1) {
syllable = 'f'+syllable;
}
else {
syllable[consonant] = 'f';
}
answer += syllable;
if (S[i] == ' ') {
answer += ' ';
}
consonant = -1;
syllable = "";
}
else {
syllable = syllable + S[i];
if (S[i] != 'a' && S[i] != 'e' && S[i] != 'i' && S[i] != 'o' && S[i] != 'u' && consonant == -1) {
consonant = syllable.size() - 1;
}
}
}
cout << answer << '\n';
return 0;
}
Isthmus
A naive brute force solution tests whether each piece of land is a peak or valley. For each piece of land, we check the K pieces of land to its left and K pieces of land to its right to find out if it is a peak. There are N pieces of land to process, and 2*K pieces of land to be processed, resulting in an O(NK) algorithm. This will yield approximately 48% of the total score.
To get full marks, we can observe that there is no need to continue processing the pieces of land if we have already determined that the piece of land in the center is neither a peak nor a valley. Then, for each peak/valley, we will process O(2*K) = O(K) pieces of land, and for each of the 2*K pieces of land on the “slope” of the peak/valley we will only process the 2 adjacent pieces of land (after which we break the loop), summing up to O(2*2*K) = O(K) in total. The worst case is when we have a peak/valley in the middle which is formed by all N pieces of land, yielding an algorithm with run-time O(N+2*N) = O(N).
Python 3
O(NK)
def strict_inc(L):
"""Checks if L is a stricly increasing sequence."""
for i in range(len(L)-1):
if L[i] >= L[i+1]:
return False
return True
def strict_dec(L):
"""Checks if L is a stricly decreasing sequence."""
for i in range(len(L)-1):
if L[i] <= L[i+1]:
return False
return True
def has_land(i, K):
"""Checks if there is at least K pieces of land at both sides of i."""
return i - K >= 0 and i + K <= N-1
def is_peak(i, K):
"""Checks if i is an order-K peak."""
return has_land(i, K) and strict_inc(L[i-K:i+1]) and strict_dec(L[i:i+K+1])
def is_valley(i, K):
"""Checks if i is an order-K valley."""
return has_land(i, K) and strict_dec(L[i-K:i+1]) and strict_inc(L[i:i+K+1])
N = int(input())
K = int(input())
L = list(map(int, input().split()))
settlements = 0
for i in range(len(L)):
if is_valley(i, K) or is_peak(i, K):
settlements += 1
print(settlements)
O(N)
def has_land(i, K):
"""Checks if there is at least K pieces of land at both sides of i."""
return i - K >= 0 and i + K <= N-1
def is_peak(i, K):
"""Checks if i is an order-K peak."""
if not has_land(i, K):
return False
for j in range(1, K + 1):
if L[i + j] >= L[i + j - 1] or L[i - j] >= L[i - j + 1]:
return False
return True
def is_valley(i, K):
"""Checks if i is an order-K valley."""
if not has_land(i, K):
return False
for j in range(1, K + 1):
if L[i + j] <= L[i + j - 1] or L[i - j] <= L[i - j + 1]:
return False
return True
N = int(input())
K = int(input())
L = list(map(int, input().split()))
settlements = 0
for i in range(len(L)):
if is_valley(i, K) or is_peak(i, K):
settlements += 1
print(settlements)
C++
O(NK)
#include <bits/stdc++.h>
#define MAXN 1234567
int n, k;
int h[MAXN];
int main() {
scanf("%d %d", &n, &k);
for(int i=0;i<n;i++) {
scanf("%d", &h[i]);
}
int sol=0;
bool valley, peak;
for(int i=0;i<n;i++) {
if(i+k >= n || i-k < 0) continue;
valley = peak = true;
for(int j=1;j<=k;j++) {
if(h[i+j] <= h[i+j-1] || h[i-j] <= h[i-j+1] ) valley = false;
if(h[i+j] >= h[i+j-1] || h[i-j] >= h[i-j+1] ) peak = false;
}
if(valley || peak) sol++;
}
printf("%d\n", sol);
}
O(N)
#include <bits/stdc++.h>
#define MAXN 1234567
int n, k;
int h[MAXN];
int main() {
scanf("%d %d", &n, &k);
for(int i=0;i<n;i++) {
scanf("%d", &h[i]);
}
int sol=0;
bool valley, peak;
for(int i=0;i<n;i++) {
if(i+k >= n || i-k < 0) continue;
valley = peak = true;
for(int j=1;j<=k;j++) {
if(h[i+j] <= h[i+j-1] || h[i-j] <= h[i-j+1] ) valley = false;
if(h[i+j] >= h[i+j-1] || h[i-j] >= h[i-j+1] ) peak = false;
if(!valley && !peak) break; // important line!
}
if(valley || peak) sol++;
}
printf("%d\n", sol);
}
Chocolate Bars
The optimal strategy involves taking all adjacent pairs of chocolate bars in any order, since taking some adjacent pair of chocolate bars will never affect the possibility of taking some other pair. The straightforward solution involves scanning through the chocolate bars from left to right until a valid adjacent pair is found. Remove the pair from the list, and repeat the process until no valid adjacent pairs are found. This results in an O(N2) algorithm, yielding 50% of the total score.
To improve the naive algorithm, we can observe that upon removing some adjacent pair, either i) a new pair form where the gap is or ii) the next pair is somewhere after the gap. Hence, there is no need to start from the left again. We can use a stack to simulate this process. We push all processed chocolate bars into the stack, and check if the incoming chocolate bar is the same size as the chocolate bar on the top of the stack. If so, we pop that chocolate bar. Otherwise, we push the incoming chocolate bar onto the stack. This results in an O(N) algorithm and full marks.
Python 3
O(N2)
N = int(input())
bars = list(map(int, input().split()))
def same_length(bars):
"""Returns the first index i where bars[i] and bars[i+1] have the same length."""
for i in range(len(bars)-1):
if bars[i] == bars[i+1]:
return i
cnt = 0
i = same_length(bars)
while(i != None):
cnt += bars[i] + bars[i+1]
bars = bars[:i] + bars[i+2:]
i = same_length(bars)
print(cnt)
O(N)
N = int(input())
bars = list(map(int, input().split()))
cnt = 0
stack = []
for bar in bars:
if len(stack) and stack[-1] == bar:
stack.pop()
cnt += bar * 2 # take 2 adjacent bars
else:
stack.append(bar)
print(cnt)
C++
O(N2)
#include <bits/stdc++.h>
int n, h[1000000], done[1000000];
int main() {
scanf("%d", &n);
for(int i=0;i<n;i++) {
scanf("%d", &h[i]);
done[i] = 0;
}
int ans = 0;
int j = 1;
while(j<n) { // repeat until no adj pairs found
for(int i=0;i<n;i++) {
if(done[i] == 1) continue;
j = i+1;
while(done[j] == 1 && j<n) j++;
if(j==n) break;
if(h[i] == h[j]) {
ans += 2*h[i];
done[i] = 1;
done[j] = 1;
break;
}
}
}
printf("%d\n", ans);
}
O(N)
#include <iostream>
#include <stack>
using namespace std;
int main() {
int n, h[1000000];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> h[i];
}
stack<int> cur;
long long ans = 0;
for (int i = 0; i < n; i++) {
if (!cur.empty() && cur.top() == h[i]) {
cur.pop();
ans += 2 * h[i];
}
else cur.push(h[i]);
}
cout << ans << '\n';
return 0;
}
Authors and Attributions
- Rectangle: Problem 1 from COCI Contest 1, 2007-2008
- Complete the Equation: Problem 1 from COCI Contest 5, 2007-2008
- Bahasa F: Chong Sher Minn, inspired by Challenge #212 of dailyprogrammer
- Isthmus: Yew Jen Khai
- Chocolate Bars: Lim Yun Kai
Two other people submitted problem proposals: How Si Yu and Quah Fu Yong. Problems were curated by Justin Lim Kai Ze and Ong Shien Jin.