How to solve problem 2?

After the GCJ Round 1A, Square869120Contest #5 will be held at Atcoder.
Let's participate and enjoy!!!!!
Contest Page

How to test a code after the contest?

It feels strange to fail hidden tests of problems 1 and 2 but to pass the third's one.

How to solve problem 1 ? I think I have understood the logic, but I just couldn't solve the problem. Can anyone please look into my code ?

https://ideone.com/Kz1GgQ

What's wrong with my B??? Isn't B just binary search + greedy? I get shocked seeing this fail the large test.

My solution

So apparently Google Code Jam won't even show the reason for Runtime error, which is quite unfortunate.

Oh well, in my case the issue was me using a different g++ version and not specifying explicitly -std=c++11 flag.

What is a solution for C (Edgy Baking)?

How to see friend standings?

Problem A with a very little difference:

My solution received TLE. There are 100 test cases and time limit is 15 seconds so it should not happen, right?

I wonder if somebody had similar feeling that B easy was harder than B hard. I already encountered this situation 2 years ago in 1C problem.

I was trying to check every mask of R cashiers out of C and then what? How to optimally assign B bits to given set of R cashiers?

I think that if the problem was given with smaller constraints it would be much harder/trickier to solve, as it would be much more difficult to get BS idea.

Its really bad that we can't upsolve problems after the contest. Its really important for us as you already know. We can't even download sources of people who got full score and create our own testcases and after test our source with these testcases (not the best solution but from nothing its better). So please if anyone who got full score in any problem and wants to help, could share his/her sources ? Thank you !

I have an interesting solution for problem C that works in O(n^3) which was inspired by IOI 2016 Molecules.

WLOG, all widths<=heights and the optimal solution requires cutting at least 3 cookies. Let's iterate over all unordered triples of cookies (A, B, C) and let A, B, and C have the greatest widths among the cookies that will be cut.

WLOG, let C have the smallest width among the triple. The length of the range of possible perimeters when A, B, and C are cut is at least 3*2*(sqrt2-1)*C.width (the smallest cut is C.width and the largest is sqrt2*C.width).

If an additional cookie is cut (remember that the widths of additional cookies <= C.width), the lower bound of the range will increase by at most 2*C.width. Because 3*2*(sqrt2-1)*C.width > 2*C.width, the new lower bound must be smaller than the previous upper bound, and no values will be skipped if we cut an additional cookie. Thus, we can just cut all cookies with widths <= C.width and the answer for a triple is min(upper bound, maximum perimeter).

public class Solution {
	public static void main(String[] args) {
		int tt=in.nextInt();
		for(int ti=1; ti<=tt; ++ti) {
			out.print("Case #"+ti+": ");
			int n=in.nextInt(), p=in.nextInt(), bp=0;
			Pair[] ps = new Pair[n];
			for(int i=0; i<n; ++i) {
				ps[i] = new Pair(in.nextInt(), in.nextInt());
				bp+=2*(ps[i].a+ps[i].b);
			}
			double ans=bp;
			Arrays.sort(ps);
			double[] ps2 = new double[n+1];
			for(int i=0; i<n; ++i)
				ps2[i+1]=ps2[i]+hypot(ps[i].a, ps[i].b)*2;
			for(int i=0; i<n; ++i) {
				if(bp+ps[i].a*2<=p)
					ans=max(min(bp+hypot(ps[i].a, ps[i].b)*2, p), ans);
				else
					break;
				for(int j=i+1; j<n; ++j) {
					if(bp+(ps[i].a+ps[j].a)*2<=p)
						ans=max(min(bp+(hypot(ps[i].a, ps[i].b)+hypot(ps[j].a, ps[j].b))*2, p), ans);
					else
						break;
					for(int k=j+1; k<n; ++k) {
						if(bp+(ps[i].a+ps[j].a+ps[k].a)*2<=p)
							ans=max(min(bp+(hypot(ps[i].a, ps[i].b)+hypot(ps[j].a, ps[j].b)+hypot(ps[k].a, ps[k].b))*2+ps2[i], p), ans);
						else
							break;
					}
				}
			}
			out.println(ans);
		}
	}
	static class Pair implements Comparable<Pair> {
		int a, b;
		Pair(int a, int b) {
			this.a=min(a, b);
			this.b=max(a, b);
		}
		public int compareTo(Pair o) {
			return a-o.a;
		}
	}
}

Unfortunately I could not wake up for the round and now I can't find the problemset. Anybody knows where can I see the problems?

Can someone help me with problem 2? I thought O(60 * R * C) was good enough to pass but turned out TLE.

My solution

How to submit after contest?