Special thanks to feysel_mubarek for preparing the contest.
Contest Link: https://codeforces.com/contests/386258
A. Team
By: jo_forces
After having the input as a string we can count the number of the character "1" ether by looping or if you are in python by using list(string).count("1"). Then finally print "yes" if the count is more than 2.
n = int(input())
count = 0
for _ in range(n):
s = input()
count += s.count("1") >= 2
print(count)
Time and space Complexity $$$O(n)$$$
B. White-Black Balanced Subtrees
By: dryeab
from collections import defaultdict
import sys
sys.setrecursionlimit(8000)
count = 0
def dfs(i, s):
global count
res = 1 if s[i - 1] == 'W' else -1
for neighbor in graph[i]:
res += dfs(neighbor, s)
if res == 0:
count += 1
return res
for _ in range(int(input())):
count = 0
n = int(input())
a = [int(x) for x in input().split()]
s = input()
graph = defaultdict(list)
for i in range(n-1):
graph[a[i]].append(i + 2)
dfs(1, s)
print(count)
C. Sort the Array
By: feysel_mubarek
First we save original indices of the numbers. Then we sort them. After that we compare old and new indices. In order this question to be true, there must be either not difference between all old and new indices or there must be only one sub array in the new indices and the summation between all the indices in that sub array should be equal.
import java.util.*;
public class Solution{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
String[] line = sc.nextLine().split(" ");
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < n; i++){
map.put(Integer.parseInt(line[i]), i);
}
Arrays.sort(line, (a, b) -> Integer.parseInt(a) - Integer.parseInt(b));
boolean found = false, continued = false;
int sum = 0, start = 1, end = 1;
for(int i = 0; i < n; i++){
int prevIdx = map.get(Integer.parseInt(line[i]));
if(prevIdx != i){
if(!found){
found = true;
continued = true;
sum = prevIdx + i;
end = prevIdx + 1;
}else if(continued && prevIdx + i == sum){
start = prevIdx + 1;
}else{
System.out.println("no");
return;
}
}
if(prevIdx + i != sum){
continued = false;
}
}
System.out.println("yes");
System.out.println(start + " " + end);
}
}
Time complexity — $$$O(nlogn)$$$ Space complexity — $$$O(n)$$$
D. Equalize the Array
By: jo_forces
First we need a frequency list for each value. Then in order to delete few elements we need to keep as many as possible. and each kept value need to have the same frequency. Thinking the frequency as a height then we are looking for the largest rectangle.
How about the largest frequency combined with the second largest frequency and so on? Great lets give it a try.
let [3,8,7,5] was our frequency list first the largest frequency. 8 ==> area will 8*1 largest with second largest. 8, 7 ==> area will 7*2(14) and so on 8, 7, 5 ==> 5*3(15) 8, 7, 4, 3 ==> 3*4(12)
here we can see 15 is the largest rectangle possible. lets sort freq_list in reversed way. Then each value will be making possibly the largest rectangle with width as its index +1 and height the value.
// max([val*(i+1) for val in enumerate(sorted(freq_list))]) will give us the largest rectangle possible. This is it. except for returning the appropirate value which is length of the given array minus the largest rectangle possible.
from collections import Counter
from collections import defaultdict
t = int(input())
for _ in range(t):
n = input()
arr = list(map(int, input().split()))
freq = sorted(Counter(arr).values(), reversed=True)
remaining = max([val*i for i, val in enumerate(freq, 1)])
print(n - remaining)
Time and Space Complexity — $$$O(N)$$$
Sounds like interesting problems, but please post the actual contest invitation link. I am not able to access the gym from your link :(