Almost everybody solved div 2 problem A "Many Questions" and div 2 problem B "It's Complicated", so there's no need to discuss those here.
Almost everybody solved C "Energy Saving". I'll just note that this solution by williamx uses binary search.
/* Solution to problem C "Energy Saving" by williamx */
#include <bits/stdc++.h>
using namespace std;
int *k;
int mysearch (int x, int lo, int hi) {
if (lo+1 == hi) return lo;
int mid = lo+(hi-lo)/2;
if (x >= k[mid]) return mysearch(x, mid, hi);
else return mysearch(x, lo, mid);
}
int main () {
int n, m;
scanf("%d %d", &n, &m);
k = (int *)malloc((n+1)*sizeof(int));
k[0] = 0;
int tmp;
for (int i = 1; i <= n; i++) {
scanf("%d", &tmp);
k[i] = k[i-1]+tmp;
}
int q;
scanf("%d", &q);
int left = m*((k[n]-1)/m+1)-k[n];
for (int j = 0; j < q; j++) {
int d;
scanf("%d", &d);
int dm = d*m;
int idx = mysearch(dm, 0, n+1);
int ans2 = dm-k[idx];
if (idx == n && ans2 >= left) ans2 = left;
printf("%d %d\n", idx, ans2);
}
return 0;
}
People in the class tried various kinds of greedy algorithms, but they did not work. The intended solution is dynamic programming. Since n,k <= 1000, an O(n*k) algorithm is fine.
You're given a sequence of numbers c.(0)....c.(n-1), along with a bound k. n and k are bounded by 1000. Starting from 0 you add or subtract c.(0) from it. Then you add or subtract c.(1), etc. In every case the resulting value must be in the range [0,k]. How long can you go on until you get stuck?
This is solved by a simple DP. Keep mv.(i).(j), which is a non-empty list if after i steps you can reach a value of j. m.(i+1) can be computed from m.(i) in O(k) time. And the list is set up so that the solution is just that list (reversed).
(* Solution in Ocaml by Danny Sleator *)
let rec forall i j f = (i>j) || ((f i) && forall (i+1) j f)
open Printf
open Scanf
let read_int () = bscanf Scanning.stdib " %d " (fun x -> x)
let () =
let n = read_int () in
let k = read_int () in
let c = Array.init n (fun _ -> read_int()) in
let mv = Array.make_matrix (n+1) (k+1) [] in
let rec loop i =
(* fill in level i+1 *)
for j=0 to k do
if mv.(i).(j) <> [] then
if j+c.(i) <= k then mv.(i+1).(j+c.(i)) <- '+'::mv.(i).(j);
if j-c.(i) >= 0 then mv.(i+1).(j-c.(i)) <- '-'::mv.(i).(j)
done;
let rec findit i j = if mv.(i).(j) <> [] then mv.(i).(j) else findit i (j+1) in
if forall 0 k (fun j -> mv.(i+1).(j) = []) then findit i 0
else if i=n-1 then findit (i+1) 0 else loop (i+1)
in
mv.(0).(0) <- ['*'];
let dlist = List.tl (List.rev (loop 0)) in
printf "%d\n" (List.length dlist);
List.iter (printf "%c") dlist;
print_newline()
# Solution in Python by MattSun
# load the data
n, k = map(int, raw_input().strip().split(" "))
sequence = map(int, raw_input().strip().split(" "))
# the algorithm
val_path_pairs = {0: ""}
num_actions = 0
for num in sequence:
temp_pairs = {}
for cur_val in val_path_pairs:
next_val = cur_val + num
if next_val >= 0 and next_val <= k and next_val not in temp_pairs:
temp_pairs[next_val] = val_path_pairs[cur_val] + "+"
next_val = cur_val - num
if next_val >= 0 and next_val <= k and next_val not in temp_pairs:
temp_pairs[next_val] = val_path_pairs[cur_val] + "-"
if len(temp_pairs) > 0:
num_actions += 1
val_path_pairs = temp_pairs
else:
break
print num_actions
_, path = val_path_pairs.popitem()
print path
---------------------------------------------------
/* Solution in C++ by LaserSH */
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
int n ,k, temp, cnt = 0;
cin >> n >> k;
vector<int> dp (k + 1, 0);
dp[0] = 1;
vector<string> tracker (k + 1, "");
string res;
for(int i = 0; i < n; i++) {
vector<int> dp_new (k + 1, 0);
vector<string> tracker_new = tracker;
cin >> temp;
bool alive = false;
for(int j = 0; j <= k; j++) {
if(!dp[j]) continue;
int A = j + temp;
int B = j - temp;
if (0 <= A && A <= k) {
dp_new[A] = 1;
alive = true;
tracker_new[A] = tracker[j] + "+";
res = tracker_new[A];
}
if (0 <= B && B <= k) {
dp_new[B] = 1;
alive = true;
tracker_new[B] = tracker[j] + "-";
res = tracker_new[B];
}
}
tracker = tracker_new;
dp = dp_new;
if (!alive) {
cout << i << "\n";
cout << res << "\n";
return 0;
}
}
cout << n << "\n";
cout << res << "\n";
return 0;
}
It should have been called "Tree-Drinking" because it's just a minimum spanning tree problem.
You're given n strings of length m. The distance between a pair of strings is the maximum over all positions i of the absolute difference between the characters in those positions. You have to compute the most expensive edge needed to connect the set of strings together. I.e. it's the cost of the last edge added when forming a MST. (God, this problem is hard to read.)
The code below uses the union-find with data structure with path compression. And instead of running the standard Kruskal algorithm, it does binary search on the maximum allowed edge cost.
/* twj1993's solution */
#include <bits/stdc++.h>
using namespace std;
char s[1005][35];
int n, m;
int a[1005][1005];
int pre[1005];
int find(int x) {if(pre[x] != x) return pre[x] = find(pre[x]); else return pre[x];}
void Union(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return ;
pre[x] = y;
}
bool ok(int k) {
for(int i = 1; i <= n; i ++) pre[i] = i;
for(int i = 1; i <= n; i ++) {
for(int j = i + 1; j <= n; j ++) {
if(a[i][j] <= k) Union(i, j);
}
}
int cnt = 1;
for(int i = 2; i <= n; i ++) if(find(i) != find(1)) cnt ++;
return cnt == 1;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) {
scanf("%s", s[i]);
}
for(int i = 0; i < n; i ++) {
for(int j = i + 1; j < n; j ++) {
int v = 0;
for(int k = 0; k < m; k ++) {
int t = s[i][k] - s[j][k];
if(t < 0) t = -t;
if(v < t) v = t;
}
a[i+1][j+1] = v;
}
}
int l = 0, r = 25;
int ans = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(ok(mid)) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
There are n fields. And for the ith field there are m[i] courses you can take. The jth course in the ith field gives you a skill level s[i,j]. You have to pick one course in each field in such a way that the range of skill levels achieved among all fields is as small as possible.
My solution was to create an array of triples (s[i,j], i, j). Then sort this. Now use a two-finger scan of this array. Call the two fingers i and j (sorry for the overloading). A given pair (i,j) indentifies a set of the triples of indices between i and j, that is i, i+1, ... j-1. We're intersted in pairs (i,j) which are complete in the sense that within that range all of the fields are represented. And we want to find a complete range of minimal diameter (as determined by the smallest and largest s[] in that range).
So if the range (i,j) does not contain all the fields, we advance j until it does contain them all. And we evaluate that possible solution. Then we advance i. This guarantees that we hit the optimum solution, because for each i we find the minimum j that allows it to work. Which is also the j that causes the minimum diameter, given that the interval starts at i.
The way we tell if the interval contains all fields or not is by keeping a histogram for the current interval. That is we keep a count of the number of courses in the interval in each field. This in turn allows to keep the cardinality of the set of fields represented by the interval. That is, when we decrement a count to zero we decrement the cardinality, and correspondingly when we increment it up from zero we increment the cardinality.
(* Solution by D. Sleator *)
open Printf
open Scanf
let rec sum i j f ac = if i>j then ac else sum (i+1) j f (ac + (f i))
let read_int () = bscanf Scanning.stdib " %d " (fun x -> x)
let read_pair () = bscanf Scanning.stdib " %d %d " (fun x y -> (x,y))
let () =
let n = read_int () in
let m = Array.init n (fun _ -> read_int()) in
let mm = sum 0 (n-1) (fun i -> m.(i)) 0 in
let ar = Array.make mm (0,0,0) in
let pos = ref 0 in
for i=0 to n-1 do
for j=1 to m.(i) do
ar.(!pos) <- (read_int(), i, j);
pos := 1 + !pos
done
done;
Array.fast_sort compare ar;
let v j = let (x,_,_) = ar.(j) in x in
let f j = let (_,i,_) = ar.(j) in i in
let hist = Array.make n 0 in
let card = ref 0 in
let histinc j =
let x = f j in
if hist.(x) = 0 then card := !card + 1;
hist.(x) <- hist.(x) + 1
in
let histdec j =
let x = f j in
hist.(x) <- hist.(x) - 1;
if hist.(x) = 0 then card := !card - 1;
in
let rec advance hfun j = hfun j; j+1 in
let rec scan i j bestopt =
if !card < n then (
if j = mm then bestopt else
let j = advance histinc j in
scan i j bestopt
) else (
let newopt = ((v (j-1)) - (v i), i, j) in
scan (advance histdec i) j (min newopt bestopt)
)
in
let (bestval, besti, bestj) = scan 0 0 (max_int, 0, 0) in
let soln = Array.make n 0 in
for i=besti to bestj-1 do
let (_, field, course) = ar.(i) in
soln.(field) <- course;
done;
printf "%d\n" bestval;
for field = 0 to n-1 do
printf "%d " soln.(field)
done;
print_newline()
(If anybody wants to write up a description of algorithms for B, C, D, and F, please let me know.)
This problem is practically impossible to read. But I did it, and here's what it means.
You've given a connected undirected graph G=(V,E). An articulation point of an undirected graph is one whose removal separates the graph into two or more disconnected components. For each articulation point, its score is the size of the largest component that results from removing it. Your goal is to find the articulation point whose removal has a score that is as small as possible.
This is solved by using the standard DFS algorithm for bi-connected components. When the algorithm discovers an articulation point, you have enough information to compute the size of the biggest component among those below it. You can also figure out the size of the component above the articulation point in the DFS tree. Namely, it contains everything else. I've included Raymond's solution as well as mine.
/* Solution by wakaka */
#include <bits/stdc++.h>
using namespace std;
vector<int> E[100005];
int low[100005], H[100005], siz[100005], N;
int best, ans = INT_MAX;
void go(int x) {
low[x] = H[x];
int totch = 0;
int maxch = 0;
siz[x] = 1;
for (auto y : E[x]) {
if (H[y] == -1) {
H[y] = H[x] + 1;
go(y);
low[x] = min(low[x], low[y]);
if (low[y] >= H[x]) {
// This sub becomes disconnected
maxch = max(maxch, siz[y]);
} else {
totch += siz[y];
}
siz[x] += siz[y];
} else if (H[y] < H[x] - 1) {
// This is a backedge
low[x] = min(low[x], H[y]);
}
}
int v = max(N - siz[x] + totch, maxch);
if (v < ans) {
ans = v;
best = x;
}
}
int main() {
memset(H, -1, sizeof(H));
H[1] = 0;
int M;
scanf("%d%d", &N, &M);
while (M--) {
int a, b;
scanf("%d%d", &a, &b);
E[a].push_back(b);
E[b].push_back(a);
}
go(1);
printf("%d\n", best);
}
(* Solution in ocaml by Danny Sleator *)
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 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 read_pair () = bscanf Scanning.stdib " %d %d " (fun x y -> (x,y))
let () =
let (n,m) = read_pair () in
let numa = Array.make n (-1) in (* the dfs numbers *)
let msize = Array.make n 0 in (* max size of down component sizes for articulation vertices *)
let ssize = Array.make n 0 in (* sum of the down component sizes for articulation vertices *)
let adj = Array.make n [] in
let add_edge (i,j) =
adj.(i) <- j::adj.(i);
adj.(j) <- i::adj.(j);
in
for i=0 to m-1 do
let (u,v) = read_pair() in
add_edge (u-1, v-1)
done;
let rec dfs v num =
let rec loop remaining_edges num low =
match remaining_edges with
| [] -> (num,low)
| w::t ->
if numa.(w) < 0 then (* tree edge *)
let (num', loww) = dfs w num in
if loww = numa.(v) then ( (* v is an articulation point *)
msize.(v) <- max msize.(v) (num' - num);
ssize.(v) <- ssize.(v) + (num' - num);
loop t num' low
) else
loop t num' (min low loww)
else if numa.(w) > numa.(v) then (* descendant edge *)
loop t num low
else (* ancestor edge *)
loop t num (min numa.(w) low)
in
numa.(v) <- num;
loop adj.(v) (num+1) numa.(v)
in
let (_,_) = dfs 0 0 in
let (_, v) = minf 0 (n-1) (
fun v -> (max msize.(v) (n - ssize.(v) - 1), v)
) in
printf "%d\n" (v+1)