You can divide the problem into one problem for rows/columns (x, o) and one for diagonals (+, o), the first can be solved greedily, and for the second one you do a maximum matching between the diagonals that haven't been used (as long as the edge represents a valid position on the grid).

25 points

let us say at i-th position we have a '-' symbol and this is the left-most '-' symbol. Now, since you have to change all the '-' symbols to '+' symbols, you have to use at least one operation starting from i-th position.
I hope it gives you an idea about the proof.

Just take the max element (say X) , if its frequency is >= K then this is the answer else add its frequency to X / 2 and (X-1) / 2.

#include "bits/stdc++.h"
using namespace std;
int t;
long long n , k;
map < long long , long long > mp;
int main(){
	scanf("%d" , &t);
	for(int tc = 1 ; tc <= t ; ++tc){
		printf("Case #%d: " , tc);
		scanf("%lld %lld" , &n , &k);
		mp.clear();
		mp[n] = 1;
		long long ans;
		while(1){
			auto it = *prev(mp.end());
			mp.erase(prev(mp.end()));
			if(it.second >= k){
				ans = it.first;
				break;
			}
			else{
				k -= it.second;
				mp[it.first >> 1] += it.second;
				mp[it.first - 1 >> 1] += it.second;
			}
		}
		printf("%lld %lld\n" , ans >> 1 , ans - 1 >> 1);
	}
}

write a binary tree with the generated possibilities from N like so: root is N. left (let's call it L(n)) is the biggest subsequence generated and right (R(n)) is the smallest ( on both children for odd N or on the left and on the right for even N). Now start placing the people: you'll notice that, for a given node, the first person will stay on the node, the second will go to the left subtree, the third will go to the right, fourth will go left again, fifth will go right, and so on. Now it's easy to write an algorithm: call the answer f(n, k). if k = 1, you're on the answer node already, so just print L(n) and R(n). If k - 1 is odd, then the last guy will go to the left subtree, so the answer will be f(L(n), (k - 1) / 2 + 1). if it's odd, the last person will go to the right subtree, so the answer will be f(R(n), (k - 1) / 2).

it would look like this:

long long R(long long n) {return (n - 1) / 2;}
long long L(long long n) {return (n - 1) / 2 + !!(n % 2 == 0);}

void f(long long n, long long k) {
  if(k == 1) cout << L(n) << ' ' << R(n) << '\n';
  else {
    if((k - 1) % 2 == 0) f(L(n), (k - 1) / 2 + 1);
    else f(R(n), (k - 1) / 2);
  }
}

You just need to pass any of the three.

Another simple greedy solution is to notice, that a tidy number can be represented as a sum of at most 9 numbers consisting only of 1s. For example, 133347 = 111111 + 11111 + 11111 + 11 + 1 + 1 + 1. The solution is then to add maximum such number so that the sum doesn't exceed N and the count doesn't exceed 9.

long long answer = 0;
int count = 0;
for (long long ones = 111111111111111111LL; ones > 0; ones /= 10) {
    while (count < 9 && answer + ones <= N) {
        ++count;
        answer += ones;
    }
}

I guess it was a DIV 2E, but then again i'm a noob.

I'd say it is at least div2 E or a bit higher if you consider that div2 E is getting easier and easier (maybe that's just me).

Yes, it's still the same (top 1000 in each round 1 subrounds, 3000 total).

I tried to do maximum bipartite matching for B small but incorrect. Probably missed some corner case. I think the large is DP.

I got AC B-large with greedy. Just sort each row in Q and take earliest match possible.

C-small I could get AC with BFS, obv. doesn't work for large :D

Are there any corner cases in B? I also used maxflow but WA.

No letter appears in more than one cell in the input grid.

Made the same mistake and discovered it right now thanks to your query . Feel terrible !

https://code.google.com/codejam/contest/5304486/dashboard#s=a&a=2

I think many people missed the thing you have said about A :(

Same here :P Though C helped me get into top 1000 :D :D

Anyone here have a nice(short) solution to problem B? :)

GCJ people are so good at super-tricky problems. I can't believe very high success rate (more than 30%!).

For me it looked completely hopeless without stress-testing.

Did you cover a case that the last horse cant be the same as the first one?

For subtask with O = G = V = 0:

Assume a >= b >= c the number of occurrences. (Assuming c >= 1, other case is trivial)

Place a's first. You need (b+c >= a) to seperate all a's. If it is not so then its impossible.

Place b's after every a and then c until finished.

Incase you have some extra c's remaining: Let extra = (b+c) — a. Place each of this after every ab: aba -> abca...

So it goes like abc-abc-abc-ab-ab-ab-ac

Code

Can I see your code? I did the same thing but it kept saying i had WA.

If you don't mind, can you please tell what you did when all of them are equal? (As in the first sample test case)

If you know how to solve B-small, that should extend to B-large.

Notice for the color orange, it can only be adjacent to blues. Suppose there are x blues and y oranges. Of course if we have y > x, then it's impossible, otherwise if we have y=x, it's only possible if y+x = n. After handling this, we can reduce it to a problem where there are x-y blues and 0 oranges. Then, you solve the same case as small, and then replace any single arbitrary occurrence of "B" with "B" + y * "OB"

Here is an opposite take on the problem, which first solves hard and easy case follows naturally:

Consider a graph where each of 6 colors is a node. You know the number of edges between orange and blue, and two other pairs, because one should surround the other. You know that in-degree and out-degree of each node should be equal to the total number of unicorns of that color. Loop through a number of edges between, say, R and G, and then the in-degree and out-degree of every other node follows naturally from that. Now you just check if that graph has an Eyler cycle, that is your answer.

MAXN error? I had issue with A large because in the beginning it said MAXN = 100 but it was really 1000. (or maybe I just read it wrong the first time)

It makes us feel bad about ourself. :(

Always this hate, I can't understand it..

It's a nice variation to shorter statements. I see that statements like these in weekly contests might get annoying, but GCJ is once a year.

dislike my comment if u quit competitive programming after this code jam (Y)

Probably! You should only do it if it's fun!

Your rank in a contest depends completely on the type of problems you've practiced before. eg: if you've practiced lots of graph and not much else, but the contest is full of geometry, probability, etc. then you are bound to fail in that contest because that problemset is not your strong suite. If however there were some tricky graph problems, you might be able to solve it even though the total number of accepted solutions is low ( tricky problem ).

Today's problemset had my weaknesses. Naturally I failed today. But does that mean I don't have "talent" or anything like that? Mmmm.... I don't know and I don't care.

All year, I trained to solve problems almost everyday. I kept journal of how many hours I spent on training per day, per week, per month. According to my journal since May 2016, I spent about 500 hours (and those are only hours when I worked at home in total silence).

Let's make a deal here and now. Do exactly this again for the year 2017 and let's look at what will happen.

PS: I've also got far shittier place this year =)

Same for me, took 67th (!) place at 2016 Round 1B. And now 1094th.

Last year in round 1B I screwed up with task B — I spent too much time on it, and at the end I submitted a solution in which my value of infinity was smaller than the correct answers for some test cases (which I didn't catch in the small test set for obvious reasons). I also had no clue that the task C was a standard problem. I ended up 1180th and didn't advance. A week or two later in 1C I lucked out with 31st place and eventually went on to advance to Round 3.

See how much variance is in such contest? You have good days and bad days. You can still easily qualify in Round 1C while in the first hundred, you'll forget this round and be extremely grateful for all the hard work you've put in to it!

Hint: O need to be in between Bs, V needs to be in between Ys, and G needs to be in between Rs.

V can only be surrounded by two Ys, so the best way to arrange Vs is 'YVYVY...VY' The whole string can be seen as a single V.

So we can reduce this problem into the same as the small dataset.

The only special case is there are only Vs and Ys with the same amount, which is a valid case.

I'm a grey and solved A small and large in 40 minutes.

you can practise there on the gcj page itself ! download test files and submit output files !

I tried all sorts of heuristics and even simulated annealing, without success. My idea was that the reason it's a small input is that with heuristics you need a bit of luck to get it correct, so it's only reasonable to allow multiple tries.

Can't tell what the correct solutions are doing at a quick glance, so we'll just have to be lazy and wait for the editorial. :(

I only know, how to calculate probability that at least k of n works fine.

dbl ans = 0;
for (int i = k; i <= n; i++)
    ans += work[i];
return ans;

Stupid question but how did you solve small C? It looked deceptively simple (judging from the number of successful submissions) but somehow I couldn't crack it after almost an hour. :(

As I saw from some solutions, you need to choose some j >= k, and maximize product of the j highest probabilities (with the method from small C). Choose the best from all such j. Also check the case when you increase the highest probabilities to 1.0 as many as possible.

I don't know how to prove it.

B large is DP. We want the answer for each of 24*60 seconds such that ith second is cam/jam's responsibility to look after the child such that jam has already looked after the child for t seconds. So the dp table looks like dp[i][cam/jam][t]. Quite simple, but I still couldn't solve it.

Define f(c,j,i,s) as the smallest number of exchanges so that Cameron has watched the baby for c minutes, Jamie has watched the baby for j minutes and the baby is currently (at the end of c+jth minute) being watched by Cameron (i=0) or Jamie (i=1) and the first one to watch the baby was Cameron (s=0) or Jamie (s=1). Store the activity status of each minute in an array so you can check in constant time who is doing activities at minute c+j-1. Each recursion step is a simple constant time check and there are only 720*720*2*2 states to store in the DP.

The final answer is min(f(720,720,0,0), f(720,720,0,1)+1, f(720,720,1,0)+1, f(720,720,1,1)).

In A-large, first sort the pancakes in decreasing order of their radii, so that i+1 can always be placed on i. Let dp[i][j] be max value of exposed surface area of a stack of j pancakes considering only first i in our list.

Then, dp[i][j] = max( dp[i-1][j], dp[i-1][j-1] - pi*r[i]*r[i] + surface_area(i)) i.e. when we do not place ith pancake or when we place ith pancake on stack of length j-1.