Remember to register.

--- EDIT, the contest is over ---

BearBall, 250 points

There is a special case when all points are in one line. Otherwise, for any pair of bears the number of throws is 1 or 2.

So, for each points you should count how many points are directly reachable from this one. You achieve it by sorting other points. The complexity should be $\text{[math]}$ .

Proof that 2 throws are enough

code for BearBall

import java.util.Arrays;

public class BearBall {
	public int countThrows(int[] x, int[] y) {
		int n = x.length;
		int answer = 0;
		for(int i = 0; i < n; ++i) {
			// sort other points by angle
			Point[] p = new Point[n-1];
			int tmp = 0;
			for(int j = 0; j < n; ++j) if(i != j)
				p[tmp++] = new Point(x[j] - x[i], y[j] - y[i]);
			Arrays.sort(p);
			// check if all are collinear
			if(p[0].compareTo(p[n-2]) == 0) {
				answer = 0; // forget what was calculated so far
				for(int a = 0; a < n; ++a)
					for(int b = a + 1; b < n; ++b)
						answer += 2 * (b - a);
				return answer;
			}
			for(int j = 0; j < n - 1; ++j) {
				++answer; // the first point in this direction
				while(j + 1 < n - 1 && p[j].compareTo(p[j+1]) == 0) {
					answer += 2; // not the first point in this direction
					++j;
				}
			}
		}
		return answer;
	}
}

class Point implements Comparable<Point> {
	int x, y;
	Point(int _x, int _y) { x = _x; y = _y; }
	public int compareTo(Point other) {
		if(isRight() != other.isRight())
			return isRight() ? 1 : -1;
		return x * other.y - y * other.x;
	}
	void write() {
		System.out.println(x + " " + y);
	}
	boolean isRight() {
		return x > 0 || (x == 0 && y > 0);
	}
}

BearGridRect, 600 points

Hint: use flows, maybe mincost.

what graph?

code for BearGridRect

import java.util.*;

public class BearGridRect {
	int n, m;
	int row(int i) { return i; }
	int column(int i) { return n + i; }
	int query1(int i) { return 2 * n + i; }
	int query2(int i) { return 2 * n + m + i; }
	public int[] findPermutation(int tmp_n, int[] r1, int[] r2, int[] c1, int[] c2, int[] cnt) {
		n = tmp_n;
		m = r1.length;
		int s = 2 * n + 2 * m;
		int t = 2 * n + 2 * m + 1;
		int total = 2 * n + 2 * m + 2;
		MinCostMaxFlow f = new MinCostMaxFlow();
		f.init(total);
		
		boolean visited[][] = new boolean[n][n];
		int cnt_sum = 0;
		
		for(int i = 0; i < m; ++i) {
			cnt_sum += cnt[i];
			f.add(query1(i), query2(i), cnt[i], 0);
			for(int r = r1[i]; r <= r2[i]; ++r)
				for(int c = c1[i]; c <= c2[i]; ++c) {
					f.add(row(r), query1(i), 1, 0);
					f.add(query2(i), column(c), 1, 0);
					visited[r][c] = true;
				}
		}
		for(int r = 0; r < n; ++r)
			for(int c = 0; c < n; ++c)
				if(!visited[r][c])
					f.add(row(r), column(c), 1, 1);
		
		for(int r = 0; r < n; ++r)
			f.add(s, row(r), 1, 0);
		for(int c = 0; c < n; ++c)
			f.add(column(c), t, 1, 0);
		
		int[] ans = f.findFlow(s, t);
		int total_flow = ans[0];
		int total_cost = ans[1];
		if(total_flow != n || cnt_sum + total_cost != n) {
			int tmp[] = {-1};
			return tmp;
		}
		ans = new int[n];
		for(int r = 0; r < n; ++r) {
			for(int c = 0; c < n; ++c) {
				if(f.flow[row(r)][column(c)] > 0)
					ans[r] = c;
				for(int i = 0; i < m; ++i)
					if(f.flow[row(r)][query1(i)] > 0 && f.flow[query2(i)][column(c)] > 0) {
						ans[r] = c;
						f.flow[row(r)][query1(i)] = f.flow[query2(i)][column(c)] = 0;
					}
			}
		}
		return ans;
	}
}

class MinCostMaxFlow { // from http://web.mit.edu/~ecprice/acm/acm08/MinCostMaxFlow.java
	boolean found[];
	int N, cap[][], flow[][], cost[][], dad[], dist[], pi[];
	
	void init(int N) {
		this.N = N;
		cap = new int[N][N];
		cost = new int[N][N];
	}
	void add(int from, int to, int ca, int cos) {
		cap[from][to] = ca;
		cost[from][to] = cos;
	}
	
	static final int INF = Integer.MAX_VALUE / 2 - 1;
	
	boolean search(int source, int sink) {
		Arrays.fill(found, false);
		Arrays.fill(dist, INF);
		dist[source] = 0;

		while (source != N) {
			int best = N;
			found[source] = true;
			for (int k = 0; k < N; k++) {
				if (found[k]) continue;
				if (flow[k][source] != 0) {
					int val = dist[source] + pi[source] - pi[k] - cost[k][source];
					if (dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if (flow[source][k] < cap[source][k]) {
					int val = dist[source] + pi[source] - pi[k] + cost[source][k];
					if (dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if (dist[k] < dist[best]) best = k;
			}
			source = best;
		}
		for (int k = 0; k < N; k++)
			pi[k] = Math.min(pi[k] + dist[k], INF);
		return found[sink];
	}
	
	int[] findFlow(int source, int sink) {
		found = new boolean[N];
		flow = new int[N][N];
		dist = new int[N+1];
		dad = new int[N];
		pi = new int[N];
		
		int totflow = 0, totcost = 0;
		while (search(source, sink)) {
			int amt = INF;
			for (int x = sink; x != source; x = dad[x])
				amt = Math.min(amt, flow[x][dad[x]] != 0 ? flow[x][dad[x]] :
			cap[dad[x]][x] - flow[dad[x]][x]);
			for (int x = sink; x != source; x = dad[x]) {
				if (flow[x][dad[x]] != 0) {
					flow[x][dad[x]] -= amt;
					totcost -= amt * cost[x][dad[x]];
				} else {
					flow[dad[x]][x] += amt;
					totcost += amt * cost[dad[x]][x];
				}
			}
			totflow += amt;
		}
		return new int[]{ totflow, totcost };
	}
}

BearCircleGame, 800 points

Dynamic programming. Iterate over the number of remaining players, from n to 1. In each moment, you need an array of size with probabilities — for each number of bears what is the probability that Limak is this far from the starting bear. Then, for each bear we need probability that he loses and thus we will know the next array (for remaining - 1 remaining bears).

a loses with probability $\text{[math]}$ .

Try to first write O(n³) approach — find cycle in a sequence of indices a + 1 - k, a + 1 - 2k, a + 1 - 3k... and then over indices in the cycle sum up $\text{[math]}$ where c is the size of cycle and d says which place this index has in the cycle.

To make it faster, notice that the answer for a and for a + k will be similar. It's enough to multiply (or divide, whatever) by the sum by two, and then add one value.

code for BearCircleGame

public class BearCircleGame {
	int mod = 1000 * 1000 * 1000 + 7;
	int mul(int a, int b) {
		return (int) ((long) a * b % mod);
	}
	int my_pow(int a, int b) {
		int r = 1;
		while(b > 0) {
			if(b % 2 == 1) r = (int) ((long) r * a % mod);
			a = (int) ((long) a * a % mod);
			b /= 2;
		}
		return r;
	}
	int inv(int a) { return my_pow(a, mod - 2); }
	
	public int winProbability(int n, int k) {
		int dp[] = new int[n];
		dp[0] = 1; // probability that Limak starts
		for(int remaining = n; remaining >= 2; --remaining) {
			int old[] = dp;
			dp = new int[remaining - 1];
			boolean vis[] = new boolean[remaining];
			for(int starting = 0; starting < remaining; ++starting) if(!vis[starting]) {
				int p = 0;
				int x = starting;
				int div = 1;
				int cycle_size = 0;
				do {
					vis[x] = true;
					++cycle_size;
					div = mul(div, inv(2));
					p = (p + mul(old[x], div)) % mod;
					x = ((x - k) % remaining + remaining) % remaining;
				} while(x != starting);
				
				int power_two = 1;
				for(int i = 0; i < cycle_size; ++i)
					power_two = 2 * power_two % mod;
				if(power_two == 1) {
					System.out.println("assert inv(0)");
					return -1;
				}
				// multiply by 2^c/(2^c-1) (because it's geometric  series)
				int mul_by = mul(power_two, inv(power_two - 1));
				
				do {
					int dead = (x + k - 1) % remaining;
					if(dead != 0) {
						int nxt = (dead == remaining-1) ? 0 : dead;
						dp[nxt] = mul(p, mul_by);
					}
					p = (p - mul(old[x], inv(2)) + mod) % mod;
					p = 2 * p % mod;
					p = (p + mul(old[x], div)) % mod; // div == inv(2)^c
					x = ((x - k) % remaining + remaining) % remaining;
				} while(x != starting);
			}
		}
		return dp[0];
	}
}

WINNERS

liymsheep, who solved all three problems
ACRush
kriii

And congratulations to Petr for solving all problems and thus winning the parallel round.

greed.codeRoot = "./../.." greed.language.cpp { longIntTypeName = ll templateDef { source.templateFile = "template3500.cpp" source.afterFileGen { execute = "C:/Program Files (x86)/Dev-Cpp/devcpp.exe" arguments = ["DOLLAR{GeneratedFilePath}"] } problem-desc.afterFileGen { execute = "C:/Program Files (x86)/Mozilla Firefox/firefox.exe" arguments = ["DOLLAR{GeneratedFilePath}"] } } }

Комментарии (20)

Написать комментарий?

Zlobober

10 лет назад, скрыть # |

That was a bit of spoiler.

→ Ответить

+19

Btw, problem 600 can be solved without using mincost-flow, but using an LR-max-flow algorithm (for finding maximum flow when there are lower bounds of flows for each edge).

eatmore

10 лет назад, скрыть # ^ |

+29

Problem 600 can be solved with maximum matching (with $\text{[math]}$ vertices on each side).

Errichto

Nice, I didn't expect that. How to do it with matching?

Shapo

+18

As I see, the first part contains N rows and cnt[i] vertices for each rectangle -- placeholders for columns that are supposed to cover by marked cells in rectangle.
The same holds for the second part, but for columns and rows' placeholders.

Btw, thanks for such interesting problems!!!

StoneCold_

What's wrong with the solution using bfs for the 250 pointer ?

desert97

There could be O(N²) edges, so the complexity could be O(N³) right?

Gassa

+51

This can be overcome by breaking out of the BFS as soon as all vertices are visited.

ho-jo-bo-ro-lo

Did that in last minute but failed systest because of integer overflow -_-

NibNalin

Small clarification, this would only speed up BFS in practice right?

I mean, consider some graph with N / 2 nodes with all pairs of edges connected. the rest N / 2 nodes connected as a chain with this main component. Here BFS from any of those nodes in main component will be still O(N²) right?

Yeah, it does not help the asymptotic behavior in the general case. But in this problem, BFS becomes O(N) instead of O(N²), for the same reason the more clever solution works.

Reyna

+24

Lol there's nothing wrong when you do a bit of optimization such as returning when all of the vertices are in the queue = ))

fetetriste

Why did you set the time limit for the 800-pointer two times the usual 2s?

+31

I tried to write my Java solution to be as slow as reasonably possible. It requires ~2s for the current constraints so I chose 4s to be TL.

But you may ask why I chose high constraints. Well, to not be afraid about O(n³) approach. In hard problems it's a disaster when people get worse complexity accepted so it's very convenient for me to set high constraints. I think that everything would be fine today with lower constraint for n but I also don't see important pros.

dj3500

My screencast

← Rev. 3 →

Slightly unrelated, but what tool are you using for opening problem statement in browser and coding in Dev C++ instead of the arena?

It is really tough to use the arena(UX wise)

← Rev. 2 →

Actually, I just started to use Greed and I like it. Previously I used KawigiEdit. There are some nice posts about Greed on Vexorian's blog. For what it's worth, my config is the following:

(replace DOLLAR with dollar signs).

+38

qualify to TCO round 3 (from 39th place where top40 advance, so that's neat)
read up that this year, FOUR PEOPLE PER ROUND (3a/3b) advance to onsite
...profit?

anduturacila6

In your code for BearCircleGame, I believe that is a geometric series not an arithmetic series. Please correct me if I'm wrong.

Thanks, corrected now.

№	Пользователь	Рейтинг
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3408
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

№	Пользователь	Вклад
1	Qingyu	154
2	nik_exists	151
3	maspy	149
4	AmShZ	146
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	135
9	maroonrk	133
10	cry	130

Блог пользователя Errichto

BearBall, 250 points

BearGridRect, 600 points

BearCircleGame, 800 points

WINNERS