Almost everybody solved div 2 problem A "Tennis Tournament" and div 2 problem B "New Skateboard", so I won't discuss these here.
In Div 2 problem c "Board with lights and switches", you just need to observe that given that you can push n buttons the way to do that which maximizes the number of lights that go in is to use ceil(n/2) rows and floor(n/2) columns (or vice versa). So let f(n) = ceil(n/2) * floor(n/2). Starting from some number n, how many times do you have to apply f() so that the value is over 10^9?
Starting with 4 or fewer, you never get there. Starting with 5, you go to 6 then to 9 then to 20, ... The growth rate is doubly exponential. So you just keep iterating f() until the value is >= 10^9.
The only possibly stumbling block is that if you use 32 bit ints, it might overflow and cause you to get a wrong answer. Using 64 bit arithmetic avoids this.
I discovered somethign really odd about this problem. Some people (well at least one) interpreted it differently. LaserSH was answering a different question: how many iterations does it take for the TOTAL number of bulbs lit EVER is at least a billion. His code is below. It gives exactly the same answers as my interpretation.
/* solution by LaserSH */
#include <iostream>
using namespace std;
#define GOAL 1000000000
int main() {
uint64_t N, bulbs = 0, res = 0;
cin >> N;
if (N <= 4) {
cout << -1 << "\n";
return 0;
}
while (bulbs < GOAL) {
uint64_t temp = (N - N / 2) * (N / 2);
bulbs += temp;
N = temp;
res++;
// cout << N << " ";
}
cout << res << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main () {
long long n;
scanf("%lld", &n);
int ans = 0;
long long count = 0;
if (n <= 4) ans = -1;
//else if (n == 4) ans = 250000000;
else {
while (count < 1000000000) {
n = (n/2)*((n+1)/2);
count = n;
ans++;
}
}
printf("%d\n", ans);
return 0;
}
Div 2 problem D "New GPU"
After peeling away all the verbage the problem is this: Consider the function:
f(x) = a * sqrt(x) + b * cube_root(x)
Given p, find the minimum value of x such that f(x) >= p.
This is easily done using binary search. Here's a solution in Python 2 by MattSun:
# input
a, b, p = map(int, raw_input().strip().split())
# algorithm
def calc(a, b, n):
return a * (n ** (1.0 / 3)) + b * (n ** (1.0 / 2))
right = (p // (a + b) + 1) ** 3
left = (p // (a + b)) ** 2
while left + 1< right:
mid = (left + right) / 2
mid_val = calc(a, b, mid)
if mid_val > p:
right = mid
else:
left = mid
# output
if calc(a, b, left) >= p:
print left
else:
print right
Div 2 Problem E "Degree Sequence Tree"
You're given a list of n numbers. These numbers may or may not be the degree sequence for the nodes of a tree. If they are you have to output a tree that achieves this degree sequence. Otherwise you output -1.
There are many ways to do this. My approach was to eliminate the degree one vertices (the leaves) one at a time. I simply pair a leaf with a non-leaf, then decrement the degree of the non-leaf and continue. If successful at the end there will be two degree one nodes to connect.
My ocaml solution is below.
open Printf
open Scanf
let rec fold i j f init = if i>j then init else fold (i+1) j f (f i init)
let read_int () = bscanf Scanning.stdib " %d " (fun x -> x)
let () =
let n = read_int () in
let d = Array.init n (fun _ -> read_int()) in
let ones = fold 0 (n-1) (fun i ac -> if d.(i) = 1 then i::ac else ac) [] in
let nonones = fold 0 (n-1) (fun i ac -> if d.(i) <> 1 then i::ac else ac) [] in
let rec loop ones nonones ac =
match (ones,nonones) with
| ([],[]) -> Some ac
| (x::(y::[]),[]) -> Some ((x,y) :: ac)
| (_,[]) -> None
| ([],_) -> None
| (a::ox, b::nx) ->
let ac = (a,b)::ac in
d.(b) <- d.(b) - 1;
if d.(b) = 1 then loop (b::ox) nx ac
else loop ox nonones ac
in
match loop ones nonones [] with
| None -> printf "-1\n"
| Some tree ->
List.iter (fun (a,b) ->
printf "%d %d\n" (a+1) (b+1)
) tree
Here's Matt Dee's solution in Python 2.
from sys import stdin
def main():
n = int(stdin.readline().strip())
degs = [int(x) for x in stdin.readline().strip().split(' ')]
l = list((degs[i], i+1) for i in xrange(n))
l.sort(reverse=True)
v = [l[0]]
l = l[1:]
e = []
for (deg, i) in l:
#print i, deg, v
if not v:
print -1
return
(pdeg, pi) = v.pop()
e.append((i, pi))
if pdeg > 1:
v.append((pdeg-1, pi))
if deg > 1:
v.append((deg - 1, i))
if v:
print -1
return
for (v, w) in e:
print v, w
if __name__ == "__main__":
main()
Div 1 Problem D "Sequence of Words".
This problem involves both computing a suffix array and and then using a segment tree. Here's a very high-level description of how to do this.
You build a suffix array. For the first sample "mlcpet" The suffixes in order are:
0 cpe.. 2
1 et$ 4
2 lcp.. 1
3 mlc.. 0
4 pet.. 3
5 t$ 5
The index (0-based) where they came from is on the right.
So the suffix array is [2, 4, 1, 0, 3, 5].
We associate this list of numbers with the leaves of a segment tree, in that order. The data in each node is the weight of the leaves in the subtree rooted there. Each leaf of the suffix tree originally has a weight of one, and the internal nodes have weight equal to the total weight of all the leaves in the subtree rooted there.
Now to do a query (L,K) we need to have the weights of the high numbered leaves set to 0. That is, all leaves with number greater than n-K need to be zeroed. If that is the case, then we can do one search down the segment tree to find the Lth non-zero weight leaf from the left in the tree.
So we process the queries in decreasing order of L. We proceed to delete elements, highest index first. In the running example, we delete the 5 (last in the suffix array) then the 4 (2nd in the suffix array), etc. We process a query (L,K) at the time when only strings of length K longer are still there.
Using the "surrogate method" (or Karp-Rabin fingerprinting method) to build the suffix array takes O(n (log n)^2). The time to build the segment tree and process the deletions is O(n log n). The time to handle each query is O(log n). So it's O(n (log n)^2 + q log n), where there are q queries.
Here's Wakaka's solution:
#include <bits/stdc++.h>
using namespace std;
char S[100005];
const int MAXP = 17;
const int MAXS = 1 << 18;
int N, suf[100005];
pair<pair<int, int>, int> T[100005];
int R[MAXP + 1][100005];
pair<int, pair<int, int> > QQ[100005];
int seg[MAXS], ans[100005];
void getSuffixArray() {
for (int i = 0; i < N; ++i) R[0][i] = S[i];
for (int l = 1; l <= MAXP; ++l) {
int len = 1 << (l - 1);
for (int i = 0; i < N; ++i) {
int nex = i + len < N ? R[l - 1][i + len] : -1;
T[i] = make_pair(make_pair(R[l - 1][i], nex), i);
}
sort(T, T + N);
for (int i = 0; i < N; ++i) {
if (i && T[i].first == T[i - 1].first)
R[l][T[i].second] = R[l][T[i - 1].second];
else R[l][T[i].second] = i;
}
}
}
void update(int sn, int s, int e, int q, int v) {
if (s == e) {
seg[sn] += v;
return;
}
int m = (s + e) / 2, lsn = sn * 2, rsn = sn * 2 + 1;
if (q <= m) update(lsn, s, m, q, v);
else update(rsn, m + 1, e, q, v);
seg[sn] = seg[lsn] + seg[rsn];
}
int query(int sn, int s, int e, int q) {
if (s == e) return s;
int m = (s + e) / 2, lsn = sn * 2, rsn = sn * 2 + 1;
if (q <= seg[lsn]) return query(lsn, s, m, q);
return query(rsn, m + 1, e, q - seg[lsn]);
}
int main() {
int Q;
scanf("%s%d", S, &Q);
N = strlen(S);
getSuffixArray();
for (int i = 0; i < N; ++i) {
suf[R[MAXP][i]] = i;
}
for (int i = 0; i < Q; ++i) {
scanf("%d%d", &QQ[i].first, &QQ[i].second.first);
QQ[i].second.second = i;
}
sort(QQ, QQ + Q);
for (int i = 0; i < N; ++i) update(1, 0, N - 1, i, 1);
int cur = 1;
for (int i = 0; i < Q; ++i) {
int l = QQ[i].first;
while (cur < l) {
update(1, 0, N - 1, R[MAXP][N - cur], -1);
++cur;
}
ans[QQ[i].second.second] = suf[query(1, 0, N - 1, QQ[i].second.first)];
}
for (int i = 0; i < Q; ++i) printf("%d\n", ans[i] + 1);
}
Div 1 Problem E "K-Palindrome"
In this problem you were given a bunch of different number bases b1, b2, ... bk. (k is at most 13). Each base is at most 10^5. Then given a bunch of range queries of the form [L,U] you had to count the number of integers in that range such that the integer is a palindrome if written in one of the given bases. L and U can be up to 10^8.
The key observation is that there are not that many palindromes. So the solution is simply to construct all the numbers which are palindromes in any of the given bases. Put these in sorted order in an array. Now do binary search (once for L and once for U) to find out how many palindromes are in the given range.
Here's Wakaka's very nice code for this.
#include <bits/stdc++.h>
using namespace std;
const int MAXU = 100000000;
vector<int> L;
void go(int b, long long x, long long pb, int lst) {
if (x > MAXU) return;
if (lst) L.push_back(x);
if (pb > MAXU || (pb + x) * b + 1 > MAXU) return;
for (int j = 0; j < b; ++j)
go(b, (j * pb + x) * b + j, pb * b * b, j);
}
int main() {
int K;
scanf("%d", &K);
for (int i = 0; i < K; ++i) {
int b;
scanf("%d", &b);
for (int j = 0; j < b; ++j) go(b, j, b, j);
go(b, 0, 1, -1);
}
sort(L.begin(), L.end());
auto it = unique(L.begin(), L.end());
L.resize(distance(L.begin(), it));
int Q;
scanf("%d", &Q);
while (Q--) {
int l, u;
scanf("%d%d", &l, &u);
int ans = upper_bound(L.begin(), L.end(), u) - upper_bound(L.begin(), L.end(), l - 1);
printf("%d\n", ans);
}
}