Solutions to div 2 problems:
/* Solution to problem A (div 2) by williamx */
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a, int b) {
return a > b;
}
int main () {
int n, m;
scanf("%d %d", &n, &m);
int *a = (int *)malloc(n*sizeof(int));
for (int i = 0; i < n; i++) scanf("%d", a+i);
sort(a, a+n, cmp);
int sum = 0;
int ans = 0;
while (sum < m) {
sum += a[ans];
ans++;
}
printf("%d\n", ans);
free(a);
}
/* Solution to problem B (div 2) by williamx */
#include <bits/stdc++.h>
using namespace std;
int main () {
int n, m, a, freq[11] = {}, ans = 0;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &a);
freq[a]++;
}
for (int i = 1; i <= 10; i++)
for (int j = i+1; j <= 10; j++)
ans += freq[i]*freq[j];
printf("%d\n", ans);
return 0;
}
In problem C (div 2) you were given a sequence of numbers as input and you were supposed to find the shortest length subsequence whose sum is zero. My solution (ocaml code below) was to compute an array sum[i] such that sum[i] = a0+a1+...+ai. Now we need to find all a pair of places i and j where sum[i] = sum[j]. Then we know that a[i+1] + a[i+2] + ... a[j] = 0. Actually sum is an array of pairs, (v,i) where v is the value of the sum up to i and i is the index. We then sort these. This means that the places where sum has the same value are grouped together in the sorted list. So we just scan the list looking for successive places where the value is the same, and checking the length.
Alternatively, you can do this by keeping a hash table with the sum values along with the indices in it. This is the second solution below.
(* Solution to C in Ocaml, by Darooha *)
open Printf
open Scanf
let ( ** ) a b = Int64.mul a b
let ( ++ ) a b = Int64.add a b
let ( -- ) a b = Int64.sub a b
let ( // ) a b = Int64.div a b
let ( %% ) a b = Int64.rem a b
let long x = Int64.of_int x
let read_int () = bscanf Scanning.stdib " %d " (fun x -> x)
let () =
let n = read_int () in
let a = Array.init n (fun _ -> long (read_int())) in
let sum = Array.make (n+1) (0L,0) in
for i=1 to n do
sum.(i) <- (a.(i-1) ++ (fst sum.(i-1)), i)
done;
Array.sort compare sum;
let rec scan j best = if j=n+1 then best else
let (bestlen,_) = best in
let (v', i') = sum.(j) in
let (v, i) = sum.(j-1) in
let best = if v=v' && i'-i < bestlen then (i'-i, i) else best in
scan (j+1) best
in
let (bestlen,besti) = scan 1 ((n+2),-1) in
if besti= -1 then printf "-1\n" else printf "%d %d\n" (besti+1) bestlen
/* Solution to C by mallocanswer */
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int length = in.nextInt();
int[] arr = new int[length];
for (int i = 0; i < length; ++i) {
arr[i] = in.nextInt();
}
int minLen = Integer.MAX_VALUE, left = -1;
long sum = 0L;
HashMap<Long, Integer> map = new HashMap<>();
map.put(0L, 0);
for (int i = 0; i < length; ++i) {
sum += arr[i];
if (map.containsKey(sum)) {
int len = i - map.get(sum) + 1;
if (len < minLen) {
minLen = len;
left = map.get(sum) + 1;
}
}
map.put(sum, i+1);
}
if (left == -1) System.out.println(-1);
else System.out.println(left + " " + minLen);
}
}
Problem D (div 2) Problem A (div 1)
In this problem there are a set of "bandits". Each one is going to decide to fight or not. The criterion for bandit i is that at least a[i] other bandits are willing to fight. (You are given all the a[i]'s.) You are to find the largest "stable" subset of bandits, where the subset is stable if each bandit in the stable set has his criterion met. That is if bandit i is in the set then the set has to be of size at least a[i]-1.
The algorithm is to start with all the bandits in the set. Now if it is stable, you're done. If not, then delete the bandit whose criterion is not met. Repeat this until either there's nothing to delete.
This works because, by unduction, any stable set is a subset of the current set. (Initially you have all of them, so it holds trivially.) It is correct to delete a bandit unsatisfied with the current set, because he would be dissatisfied with ANY solution that is a subset of it. (And we already know that any stable solution is a subset of the current one.)
The final set that you reach will be the unique solution. This system has what is called the Church Rosser property.
The two solutions below implement this in a very slick way, which I will leave to you to figure out why it works.
import java.util.Arrays;
import java.util.Scanner;
/**
* Created by joe on 1/27/16.
*/
public class Contest29534 {
public static void main(String[] args){
dragon();
}
public static void dragon(){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0;i < n;i++ ){
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
for(int i = arr.length-1;i > -1;i--){
if(arr[i]<= i){
System.out.println(i+1);
return;
}
}
System.out.println(0);
}
}
/* solution by williamx */
#include <bits/stdc++.h>
using namespace std;
int n, *a, *c;
long long *b;
bool cmp (int x, int y) {
return x < y;
}
int main () {
scanf("%d", &n);
a = (int *)malloc(n*sizeof(int));
for (int i = 0; i < n; i++) scanf("%d", a+i);
sort(a, a+n, cmp);
int ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] < i+1) ans = i+1;
}
printf("%d\n", ans);
return 0;
}
Problem E (div 2) Problem B (div 1)
This problem is solved by dynamic programming.
/* Solution by Raymond Kang */
#include <bits/stdc++.h>
using namespace std;
int cnt[100005];
string G[100005];
long long ans[100005];
int main() {
int N, M;
scanf("%d%d", &N, &M);
for (int i = 0; i < N; ++i) {
cin >> G[i];
int len = 0;
for (int j = 0; j <= M; ++j)
if (j == M || G[i][j] == '+') {
if (len) ++cnt[len];
len = 0;
} else {
++ans[1];
++len;
}
}
for (int i = 0; i < M; ++i) {
int len = 0;
for (int j = 0; j <= N; ++j)
if (j == N || G[j][i] == '+') {
if (len) ++cnt[len];
len = 0;
} else {
++len;
}
}
long long tot = 0, totlen = 0;
for (int i = max(N, M); i > 1; --i) {
tot += cnt[i];
totlen += cnt[i] * i;
ans[i] = totlen + tot - i * tot;
}
for (int i = 1; i <= max(N, M); ++i)
printf("%I64d ", ans[i]);
printf("\n");
}
Problem C (div 1)
It can be set up as a standard 1D DP problem. For each point in time t(i) you compute cost(i), which is the cost of making all the orders 1, 2, ... i, and ending with a delivery at time i. Now to compute cost(j), we consider all possible last deliveries. The last delivery would go from some order i+1 through order j. In this case cost(i) would be spent on the first i orders, and the some cost would be incurred for the orders i+1...j to be placed at time t(j). This can be computed in O(1) time by the use of an array called "sum", which is precomputed. To compute cost(j) we would try all i < j. Thus the algorithm is O(n^2)
(* solution in ocaml by Danny Sleator *)
open Printf
open Scanf
let ( ** ) a b = Int64.mul a b
let ( ++ ) a b = Int64.add a b
let ( -- ) a b = Int64.sub a b
let ( // ) a b = Int64.div a b
let ( %% ) a b = Int64.rem a b
let long x = Int64.of_int x
let short x = Int64.to_int x
let rec fold i j f init = if i>j then init else fold (i+1) j f (f i init)
let minf i j f = fold (i+1) j (fun k a -> min (f k) a) (f i)
let read_int () = bscanf Scanning.stdib " %d " (fun x -> x)
let () =
let n = read_int () in
let d = long (read_int ()) in
let c = long (read_int ()) in
let t = Array.init n (fun _ -> long(read_int())) in
let sum = Array.make (n+1) 0L in
for i=1 to n do
sum.(i) <- t.(i-1) ++ sum.(i-1)
done;
(* t.(a)+...+t.(b) = sum.(b+1) - sum.(a) *)
let cost = Array.make n 0L in
for j=0 to n-1 do
cost.(j) <- minf 0 j (fun i ->
let k = long (j-i+1) in
let s = sum.(j+1) -- sum.(i) in
let prev = if i=0 then 0L else cost.(i-1) in
d ++ c ** (k ** t.(j) -- s) ++ prev
);
done;
printf "%Ld\n" cost.(n-1)
Problem D (div 1)
/* Solution by Raymond Kang */
#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> euclid(long long a, long long b) {
if (!b) return make_pair(1, 0);
auto f = euclid(b, a % b);
long long x = f.first, y = f.second;
return make_pair(y, x - y * (a / b));
}
int main() {
long long n, m;
scanf("%I64d%I64d", &n, &m);
long long g = __gcd(n, m);
long long best = n * m / g;
if (g == 1) {
if (n == 1 && m == 1) best = 1;
else if (n == 1 || m == 1) best = 2;
else {
auto x = euclid(n, m);
best = max(abs(x.first * n), abs(x.second * m));
}
}
printf("%I64d\n", best);
}
Problem E (div 1)
The problem here is to generate a long string of the letters "a", "b", and "c" such that in that string the pattern "WW" does not occur. That is, a string W followed by the same string W.
Jason solved this elegantly below by building up a string by appending random letters, and then checking that the addition of that letter did not created a suffix of the form WW, where the length of W is up to 50. This algorithm will fail with some very small probability, which is exponential in the constant 50. So failure is pretty unlikely.
To avoid getting stuck, the algorithm backtracks with a probability of .1. on each step. This works really well.
/* Solution by Jason Li */
#include <bits/stdc++.h>
using namespace std;
vector<char> V;
bool sub_check(int a, int b, int n)
{
for(int i = 0; i < n; i++)
if(V[a + i] != V[b + i]) return false;
return true;
}
bool check()
{
for(int n = 1; n <= 50 && 2 * n <= V.size(); n++)
if(sub_check(V.size() - n, V.size() - 2 * n, n))
return false;
return true;
}
int main()
{
int N;
cin >> N;
while(true)
{
if(!V.empty() && rand() % 10 == 0) V.pop_back();
V.push_back('a' + rand() % 3);
if(!check()) V.pop_back();
if(V.size() == N)
{
for(int i = 0; i < N; i++) cout << V[i];
return 0;
}
}
}
Problem F (div 1)
You're given an undirected graph. Your goal is to find a list of vertex visits v[1], v[2], ... such that every edge of the graph occurs at (v[i],v[i+1]) for some i. The sequence needs to be as short as possible.
This is a generalization of the concept of an Euler tour of a graph. If you're given a connected undirected graph, with the property that each vertex has even degree, then there is an "Euler Tour" that starts from a vertex v, walks over each edge exactly once, and ends at vertex v.
So to solve the given problem, we add edges until it is (1) connected and (2) all vertices have even degree. We then find an Euler tour of this graph. (This is the solution with one small tweek.)
You have to add as few edges as possible. If there are c connected components we know start by adding c edges. We try to use up as many vertices of odd degree as possible while doing this. If there are still odd vertices left over we arbitrarily add edges connecting them.
I won't include code here. See me if you want more info on the problem.