Google Code Jam — 2017

8 years ago, # |

← Rev. 2 →

How to solve D of qualification round with maximum bipartite matching? The best I could think was to place maximum bishops and rooks on nxn chess board.

edit-solved.

→ Reply

MarioYC

8 years ago, # ^ |

← Rev. 2 →

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).

→ Reply

8 years ago, # ^ |

← Rev. 2 →

Can you prove why any placing is optimal? And how can we decide which ones to upgrade?

I was able to reduce the problem to what you said, and I think it's just about placing maximum bishops(+,o) and rooks(x,o) but why is it correct?

→ Reply

MarioYC

8 years ago, # ^ |

Since you're using the maximum matching it has to be optimal. Upgrading happens when you modify one occupied cell in one of the two subproblems.

→ Reply

8 years ago, # ^ |

← Rev. 3 →

I am still unsure why greedy + MBM gives optimal answer.

I started to think that both have to placed with bipartite matching simultaneously. As, depending on how you place your 'x' you may not be able to place maximum number of '+'. eg : when n = 4, if we place 'x' in (1,2), (2,1), (3,4) and (4,3) we won't be able to place the maximum number of '+' with such an arrangement. The maximum is 6(+) + 3(x) = 9 models, but if the above configuration is followed, we only get 4(x) + 4(+) = 8 models.

→ Reply

animeshf

8 years ago, # ^ |

They've uploaded a very detailed Contest Analysis. You can check it here

→ Reply

8 years ago, # ^ |

Thanks! I didn't know there was an editorial :|

→ Reply

MarioYC

8 years ago, # ^ |

The particular thing in the problem is that the value of o is 2, this gives you the equivalence between solving the main problem and the two subproblems

→ Reply

8 years ago, # ^ |

Oh! I see now. That's clever :)

→ Reply

_DN_

8 years ago, # |

how many points needed to go to next round "Online Round 1: Sub-Round A" ?

→ Reply

zscoder

8 years ago, # ^ |

+14

25 points

→ Reply

Mr.Awesome

8 years ago, # |

I solved A but can any one give a proof of that solution ( iterate the string and if the current character == '-' flip the next k pancakes )?

→ Reply

pakhandi

8 years ago, # ^ |

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.

→ Reply

Mr.Awesome

8 years ago, # ^ |

I'm sorry but I didn't get it, also I'm interested with proof of optimality ( minimum number of operations ).

→ Reply

pakhandi

8 years ago, # ^ |

If i-th position is the left-most position with '-' symbol, then the claim is that it would be optimal to perform an operation at i-th position because there is no other way to convert the i-th symbol.
In case you perform an operation at a position j before i such that j + k <= i then, by our assumption, we would be creating new '-' symbols before i-th position, hence increasing the number of operations.

→ Reply

caioaao

8 years ago, # ^ |

to understand this, first you have to notice that the flips are commutative. by noticing it, you also understand that two flips on the same range are the same as not doing any flip. so, starting from left, there's only one way to turn the first '-' into '+'. this is true for the rest of the pancakes: if there's a '-' on the pancake with index i, there'd be two ways of turning it into a '+': by doing a flip starting at i or by doing a flip starting before i. you know that by flipping something before i you'd be either canceling a flip you already did (thus turning a '+' into '-') or adding a flip you didn't do (also turning some '+' into '-'). so the only possible way of turning the current pancake is to make a flip starting at it.

→ Reply

8 years ago, # |

How to solve C-large anyone ??

→ Reply

rajat1603

8 years ago, # ^ |

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.

Code

#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);
	}
}

→ Reply

caioaao

8 years ago, # ^ |

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 ( $\text{[math]}$ on both children for odd N or $\text{[math]}$ on the left and $\text{[math]}$ 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);
  }
}

→ Reply

E869120

8 years ago, # |

+20

After qualification round, Square869120Contest #4 will be held at Atcoder.
Let's participate and enjoy!!!!!
https://s8pc-4.contest.atcoder.jp/

→ Reply

8 years ago, # |

Can anyone explain me what does it mean that Round 1 is divided into 3 Sub-Rounds? Does it mean that we have to advance in any of these like in TCO or we have to pass through all of them?

→ Reply

microtony

8 years ago, # ^ |

You just need to pass any of the three.

→ Reply

8 years ago, # |

Problem D was very nice! Although I didn't solve it in contest, I thought the author's solution was very elegant.

→ Reply

code_astra

8 years ago, # |

Can anyone Explain the greedy method used in the editorial in a more simpler way ?And if anyone solved it bipartite matching feel free to explain your method also.Thanks in advance .

→ Reply

misof

8 years ago, # |

+46

The analysis for B is unnecessarily complicated. We can just greedily construct the optimal number by going from the left to the right. (Additionally, to avoid all special cases just prefix both the input and your number with a 0.)

Example:

   input number: 01568435466
we already have: 0156

What is the largest next digit we can use? If we use digit d, the smallest possible final number will have d on all remaining places. If this number is small enough, there are some valid tidy numbers with the next digit d, and if this number is too large, there are no valid tidy numbers in which the next digit is d. And that's all.

   input number: 01568435466
we already have: 0156
   we can use 7: 01567777777 is <= input
we cannot use 8: 01568888888 is > input
thus, next step: 01567

My submitted code:

T = int(input())
for t in range(1,T+1):
    V, A = [0]+[int(_) for _ in input()], [0]
    while len(A) < len(V): A.append(max(d for d in range(A[-1],10) if A+[d]*(len(V)-len(A)) <= V))
    print('Case #{}: {}'.format(t,int(''.join(str(_) for _ in A[1:]))))

→ Reply

Al.Cash

8 years ago, # ^ |

+140

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;
    }
}

→ Reply

Azret

8 years ago, # ^ |

← Rev. 4 →

+28

OMG. In compare, I have a mega overkill: I wrote dp[lengthOfNumber][startingDigit] to find maximum number X, such that X ≤ N and f(X) = f(N), where f(num) = number of tidy numbers less than or equal to num.

Code: https://pastebin.com/Pw1c4rXM

→ Reply

msci

8 years ago, # ^ |

I think I have an even simpler solution:

Reading the number n as a string s, for an index i, 0 ≤ i < s.size() - 1, if s[i] > s[i + 1] then we decrement s[i] and for all j, i + 1 ≤ j < s.size(), s[j] = 9. We then increment i. Since there may be cases like 554 we run the algorithm log(n) times (i.e. cases in which we have a violation of the tidy number constraint that was generated by the algorithm before index i).

Total running time is log(n)².

string s;
cin >> s;
for (int t = 0; t < 18; t++) {
    int ix = 0;
    while (ix < (int) s.size() - 1) {
        if (s[ix] > s[ix + 1]) {
            s[ix]--;
            for (int i = ix + 1; i < (int) s.size(); i++) {
                s[i] = '9';
            }
        }
        ix++;
    }
}

Afterwards just print s without the leading zeroes.

→ Reply

P___

8 years ago, # ^ |

← Rev. 2 →

Without dealing with any leading 0's. Printf res:

I thought that this is the same approach as above, but I was wrong. It is O(lg N). Remember the smallest digit you constructed so far. If you have something bigger, then decrement it by 1, set all 9's at the end and set that new smallest value to new decremented digit.

        LL N;
        scanf( "%lld", &N );
        
        LL mn = 1;
        LL prev = 9;
        LL res = N;

        while (N)
        {
            if (N % 10 > prev)
            {
                // obniz o 1 pozycje i z tylu same 9 daj
                N--;
                res = N*mn + mn - 1;
                prev = N % 10;
            }
            else
                prev = N % 10;

            mn *= 10;
            N /= 10;
        }

→ Reply

8 years ago, # |

Just out of curiosity

Would you say problem D was comparable to a div2 D level problem, or div2 E in terms of difficulty?

→ Reply

I_Love_Equinox

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

+13

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).

→ Reply

8 years ago, # ^ |

It was a very beautiful problem, especially because it reminded me of a sport I love :)

I didn't think it would be considered that difficult as close to 1000 people solved it in 27 hrs, but the logic was indeed very good behind the problem.

→ Reply

P___

8 years ago, # ^ |

Which was especially noticeable in the last 408 div2 round.

→ Reply

8 years ago, # ^ |

I hope you're being sarcastic... XD

→ Reply

8 years ago, # ^ |

I'd see it as not sarcastic but last round simply showed that the other div 2 rounds were way easier than what they could be. Also, looks like tons of people misunderstood C's statement, I did that too when looking at the contest later hahaha.

→ Reply

8 years ago, # ^ |

Oh, I kind of misunderstood you comment. I thought you were saying last round's problem E was easy, which is definitely isn't. BTW, I also misunderstood C's statement XD

→ Reply

kojak_

8 years ago, # |

Test cases for B-small were weak. I had an AC solution which actually failed in cases such as 331.

→ Reply

ProximaCentauri

8 years ago, # |

+15

For problem — C (large), I got the solution like — write the binary representation of k, then we will compute n for every bit (from right), except the left most bit. If the bit is '0', we get n = n/2, if the bit is '1', we get n = (n-1)/2. After computing for every bit, the answer will be — max(a, b) , min(a, b) where a & b is computed in this way : if(n%2 == 0) a = n/2, b = n/2 — 1; else a = (n-1)/2, b = (n-1)/2

The time complexity of this approach is log(k). But I can't prove why it is correct!!

→ Reply

8 years ago, # |

How many people from online round 1 would qualify to round 2, I can't seems to find info from their site? From what I remembered, it is top 1000 of each round, but is it still the same?

→ Reply

Kombu

8 years ago, # ^ |

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

→ Reply

https://code.google.com/codejam/terms

8 years ago, # ^ |

thanks! any source for that info?

→ Reply

Kombu

8 years ago, # ^ |

"1. You will advance to Code Jam Round 2 if you are one of the highest-ranked 1000 contestants from one of the sub-rounds in Code Jam Round 1. You will be notified by email after the end of each sub-round if you are one of the 3000 contestants advancing to Code Jam Round 2."

→ Reply

8 years ago, # ^ |

thanks

→ Reply

Vicennial

8 years ago, # |

Logic for B & C in round 1A please?

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

← Rev. 3 →

-10

I solved B small/large with maximum bipartite matching. If I had to guess it was probably something to do with the range that you can get from each package.

Edit: forget that, the problem is harder than I thought.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

nvm

→ Reply

yassin_

8 years ago, # ^ |

← Rev. 2 →

+21

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

→ Reply

8 years ago, # ^ |

I think everyone thought this solution at one point. Wish I hadn't overthought it :|

→ Reply

8 years ago, # |

I submitted a max flow solution to B, during contest it passed the small so i submitted the large. The large failed after the contest so I was curious to know what the problem was, I tried submitting the large again in the practice with the same exact code and got a correct verdict! Is it just the test cases are weak for the practice or what

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

← Rev. 2 →

well I don't know, actually by comparing with other solutions, my code failed in only a single case out of the 100 and it's this one http://ideone.com/WNzI0X

My code outputs 4 while the answer should be 3. It's too hard to debug though lol

→ Reply

majk

8 years ago, # ^ |

+10

Keep in mind that a package may be suitable for kits of different sizes. What do you return for this? 4 1 1 1 1 1 100 110 120 130

I used a simple greedy approach — first try to match the packages with minimum size for each. If that does work, take all and increase answer by one. Otherwise, discard the package with the smallest Q_ij / R_i and try again, until there are no more packages left. Works in O(N² * P).

→ Reply

8 years ago, # ^ |

Yes I know, actually I build a flow network of N+2 layers, first layer is source and last is sink. Each layer represents an ingredient and it has P nodes, I add an edge between a node from a layer and the layer next to it if there is at least one common kit size they both can fit in. Basically for each package, the valid kit sizes is a range so you can find if there is a common one or not by a simple range intersection

→ Reply

8 years ago, # ^ |

and my code returns 1 for your input

→ Reply

majk

8 years ago, # ^ |

← Rev. 2 →

Yet the correct answer is 0. If the kit is of size >111, you cannot use the first package. If it is of size <119, you can't use the last. Hence, the is no valid kit size, even though the ranges of consecutive ingredients overlap.

→ Reply

8 years ago, # ^ |

loool I feel so dumb now. Thanks a lot for the help

→ Reply

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

8 years ago, # ^ |

It should return 0. The problem is that you need overlapping ranges to choose the packages. For example, (1 — 2), (2 — 3), (3 — 4) these are the ranges of 3 packages and you can't choose them but there will be flow if you simply connect them from one layer to the other.

→ Reply

dalex

8 years ago, # ^ |

+10

Sometimes it's better not to know maxflow algorithm at all. You could have thought a bit more and come up with very simple greedy algorithm.

→ Reply

P___

8 years ago, # ^ |

I tried max flow first. Because I couldn't find appropriate network, I wrote the simplest greedy instead.

→ Reply

Frank_15

8 years ago, # ^ |

Can you, please, explain why this greedy strategy will not work when we have arbitrary ranges (according to the official editorial)?

Especially, I don't see for now why the condition: "for 2 intersecting ranges having at least 1 common point" helps to prove that greedy approach works?

→ Reply

Fcdkbear

8 years ago, # ^ |

I have exactly the same question. Can anyone explain?

→ Reply

kittylover

8 years ago, # |

← Rev. 2 →

-30

Looks like tests for A are weak. For test:

1
3 3
J??
JH?
??H

some accepted solutions (firstly I tried tourist's one) give this result:

JJJ
JHH
HHH

Or I misunderstood statement and this is valid construction?

→ Reply

paulwang

8 years ago, # ^ |

+22

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

→ Reply

kittylover

8 years ago, # ^ |

Thank you, I missed that restriction :(

Need to sleep a little bit more — it's bad idea to participate at 4am.

→ Reply

Mithrandir_14

8 years ago, # ^ |

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

→ Reply

ordan

8 years ago, # |

← Rev. 3 →

+23

Very weak test cases for B, I got AC large using a wrong max flow solution that allows to use a package multiple times.

My code gives 2 instead of 1 for this testcase:

→ Reply

Deemo

8 years ago, # |

How to solve C-large?

→ Reply

ordan

8 years ago, # ^ |

+18

→ Reply

8 years ago, # |

+39

Anyone else thinks that the problem statement is too long?

For A, I missed no initial appears more than once on the cake. and couldn't solve the problem.

And for B, I missed (Of course, each package can be used in at most one kit.) and only found out after an hour...

→ Reply

wittyskull

8 years ago, # ^ |

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

→ Reply

Omar_Morsi

8 years ago, # |

← Rev. 2 →

+31

I hate problem B xD

→ Reply

8 years ago, # ^ |

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

→ Reply

Omar_Morsi

8 years ago, # ^ |

← Rev. 2 →

Didn't even read Problem C :S

→ Reply

8 years ago, # ^ |

Even i never open harder problems before even trying easier ones. ! But this time the submited problems count at begining compelled me to try C first !

→ Reply

peterpans01

8 years ago, # ^ |

Can you tell us how to solve C? I can recongise it as DP shortest path but can't handle how to solve the problem with choosing the horse.

→ Reply

8 years ago, # ^ |

for small : just linear dp for each horse i = 1..N for each city j = i+1 to N if j is within limit of horse i through path i..i+1 i+2..j time[j] = min(time[j],time[i]+dist(i..i+1..i+2...j) /spd[i].

ans = time[n-1];

for large: for each horse do dijikstras to find min time in which it can reach each city reachable time[i][j] = time for horse [i] to reach city[j] in other words one path from i to j of cost time[i][j]

then do floyd warshall shortest path for each pair i,j to get final cost array[n][n]

ans will be in this array

check my solution in GCJ page : username — sanket407

→ Reply

8 years ago, # ^ |

Just don't choose the horse, always use the horse at the current DP, when you update from a town just update all towns within range, not just the ones connected by edges.

→ Reply

8 years ago, # ^ |

+11

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

→ Reply

rng_58

8 years ago, # ^ |

+83

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.

→ Reply

8 years ago, # ^ |

+23

What is tricky about it? You just have to find a bunch of test cases. Frankly I don't see the purpose of such problems. It's not "good at super-tricky problems" it's "annoying problems".

→ Reply

8 years ago, # |

+11

How is round 1B problem B meant to be solved? I checked my code over and over even with triangle inequality and I still couldn't solve the small case. I have no clue what's wrong!

→ Reply

8 years ago, # ^ |

-10

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

→ Reply

8 years ago, # ^ |

← Rev. 2 →

yeah. I swap the last two if they are the same, then check if it works.

→ Reply

vsp4

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

decoder123

8 years ago, # ^ |

How did you get the idea? There are logical reasoning..can you post it? The approach ?

→ Reply

8 years ago, # |

How to small B-large ?? B-small could be done by assigning alternately colors in foll, order largest count — then mid count — smallest count

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

check my code in google code jam submissions itself! Same username there as handle here : sanket407

→ Reply

nikhil_c

8 years ago, # ^ |

← Rev. 2 →

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)

→ Reply

Lewin

8 years ago, # ^ |

+56

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"

→ Reply

8 years ago, # ^ |

Honestly, if this was described as part of the problem, I still wouldn't be able to solve it.

→ Reply

hellman_

8 years ago, # ^ |

During the contest I thought it can make a difference if you join all BOs inti one BOBOBOBOBOB or split into BOB,BOB,BOB, ... Had to bruteforce the numbers of BOBs, RGRs, YVYs. Got AC with that (the numbers sum to N/3 so the max number of combinations could be 111^3).

Now I see that the amount does not matter, thanks

PS: and failed C-large, which I thought is simple >_<

→ Reply

maksay

8 years ago, # ^ |

+34

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.

→ Reply

8 years ago, # ^ |

So the selection is n^2 and euler cycle takes O(E) and here E ~ N, so O(T * n^3). Isn't it TLE?

→ Reply

maksay

8 years ago, # ^ |

No, selection is actually O(N) — you backtrack through the out-degree of one node and the remaining in- and out-degrees follow. Then you need to check whether the obtained graph has an Eyler cycle, which can be done in O(1). Then you output that cycle in O(E) = O(N).

Actually, I computed the cycle every time and then checked that it had length N, and if so, printed the answer, so the total complexity was O(TN²), that passed.

Here is the solution: https://pastebin.com/hfxVkTyZ

→ Reply

AlwaysMerlin

8 years ago, # ^ |

I had something similar.

Can't you just check the in/out degree of each vertex in O(1) to check if an Euler cycle exists? This leads to an O(N) algorithm, I think.

→ Reply

maksay

8 years ago, # ^ |

That is what I said in the first paragraph exactly.

The only subtle moment is that you need to also check that the graph is connected — ex. for test 12 2 2 2 2 2 2 you get in your graph 3 connected components, in each of which in- and out-degrees are equal.

→ Reply

AlwaysMerlin

8 years ago, # ^ |

← Rev. 2 →

Good point. I was just checking that it was possible, not claiming you didn't already say that. I figured you could simply do this in O(1) by doing a DFS through a graph with collapsed edges.

→ Reply

8 years ago, # ^ |

This is so far the best solution for this deadly problem.

→ Reply

yinanzhu

8 years ago, # |

+25

Either take round1-C in 4am, or say bye-bye to GCJ :(

→ Reply

WasylF

8 years ago, # |

← Rev. 2 →

Any ideas why A-large could fail?)

UPD:
I made wrong assumption:
If we sort horses by start position we can ignore all horses starting from first horse that ride faster than previous one.

It passed small input, it's very sad((

→ Reply

8 years ago, # ^ |

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)

→ Reply

Omar_Morsi

8 years ago, # |

1113 Solved C Large. 730 Solved B Large.

This is bad for people who didn't even read C xD xD

→ Reply

ko_osaga

8 years ago, # |

+65

Kudos for HYPERHYPERHYPERCUBELOVER alex9801 who drunk lot of beers but still passed R1B safely

→ Reply

peterpans01

8 years ago, # ^ |

+16

It makes us feel bad about ourself. :(

→ Reply

8 years ago, # |

+51

By the way these statements are horrible...

→ Reply

yassin_

8 years ago, # ^ |

+13

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.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

You are right that we should appreciate long statements with a nice story behind it but in this exact situation somehow it was really difficult to have fun. (At least for me)

→ Reply

omgcoin

8 years ago, # |

+30

In the last Google Code Jam 2016, I finished 1557 in round 1B. Since then, I set the goal to advance to round 2 in Code Jam 2017 (i.e. be in top 1000).

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).

So I thought that those efforts are enough to move from 1557 place (2016) to top 1000 (this year).

And here are results of all my efforts during whole year:

Round 1B 2017 — 6617 place!!!

I.e. I became much, much, much worse at competitive programming as a result of ~500 hours of training. It's fu....g unbelievable!!!!!!

Apparently, I have no talent whatsoever and probably I should quit...

→ Reply

nologic

8 years ago, # ^ |

-8

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

→ Reply

AlexandruValeanu

8 years ago, # ^ |

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

→ Reply

omgcoin

8 years ago, # ^ |

Will you enjoy losing chess all the time to everybody including those who trained 10 times less than you?

I won't believe you will enjoy losing game all the time.

I personally enjoy very much to have an insight and find a clever solution, see my submissions in green light with magic word Accepted. It's awesome feeling. Every time, I solve hard problem (which is rare), I'm so glad and I continue starring at my code for minutes thinking how beautiful my solution.

But if you spent hours, hours, hours, hours and hours in training to only see:

WRONG! WRONG! WRONG! TIME OUT! WRONG! YOU WRONG! WRONG! TIME OUT! YOU WRONG AGAIN!

Then you can't enjoy. You can't enjoy this disaster!

→ Reply

AlexandruValeanu

8 years ago, # ^ |

I wouldn't play chess in competitions if I felt I wasn't good enough and hate to lose. But I would still practice playing chess because it's a fun way to spend some time and maybe some day I will be able to enter a chess tournament.

→ Reply

8 years ago, # ^ |

+31

You are right! Life is unfair. But if I can share one lesson from contests, it's that you can't expect to "deserve" results just because you've worked hard. That's not how this works.

→ Reply

danilka.pro

8 years ago, # ^ |

+113

Try not to take the competitive part very much serious. Competitive programming is just a thing where competitors of all levels may occasionally compete together. Just imagine if you are placed to compete with world top chess players. With dozens of them. No much point in that, right? The difference is that the CP allows this situation to happen.

Honestly, I never liked the competitive part itself. I like to solve problems, especially when I learn something by solving them. From this point, competitions don't provide me any motivation reasons, but they do provide modern problems.

So try just to forget about the competition part. No matter what rating do you have, no matter how are you placed in a contest. The best way may be not to take part in contests for a while, so you will be just facing the problems themselves. And there is no need to take it very formal, like "I've spent X hours today", you should enjoy the process, and I think it's easier to achieve when the process is more free.

There is no reason in working hard for some placing in some round — it does not show anything at your level. There is no point to take those useless numbers in mind. Enjoy, learn, solve — and only after all that — compete.

→ Reply

ko_osaga

8 years ago, # ^ |

+13

Good point. Honestly I don't like the word CP. If someone do web development in a very competitive company he is also doing "competitive programming". Fact is, we do "Algorithmic problem solving", while some fraction of them use "competitive training" to improve their skills, or just for fun.

→ Reply

http://codeforces.me/contest/779/problem/D

8 years ago, # ^ |

+17

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.

→ Reply

omgcoin

8 years ago, # ^ |

← Rev. 2 →

Here is a problem:

I didn't solve it.

But when I looked at editorial, solution turned out to be dead simple. There was nothing I didn't know to solve this problem. Yet, I didn't find that solution.

I honestly can't understand why I didn't find that solution.

I understand when I failed to solve some problem which uses trick or algorithm I didn't know. But often, it turned out that everything I need to know I already know.

It's total mystery to me.

So it turned out that solving problems are not entirely about knowledge.

→ Reply

8 years ago, # ^ |

+13

You expect a lot from yourself, and beat yourself over not being able to fulfill your own expectations. Not just that, you probably spend more time thinking "WHY CAN'T I SOLVE THIS" or "I HAVE TO SOLVE THIS BECAUSE I'VE TRAINED SO MUCH I HAVE TO" than on the problem itself.

So it turned out that solving problems are not entirely about knowledge.

This is nothing short of an epiphany! You are right. It's not just about knowledge. You have to know what to let go. Shake off bad days, and keep going.

→ Reply

8 years ago, # ^ |

You can say the same about last round's problem D. Dead simple solution, but only a few people could think it up. So many randomized algos from div1 guys also passed, which means even div1 guys had troube finding the actual solution. It didn't have any DP, tree, graph, mo's algo, centroid decomposition, etc. nothing. Just a dead simple greedy solution that everyone understood when they read the editorial.

→ Reply

8 years ago, # ^ |

+15

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 =)

→ Reply

hellman_

8 years ago, # ^ |

+19

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

→ Reply

majk

8 years ago, # ^ |

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!

→ Reply

thedark

8 years ago, # |

Can someone explain how to solve B large in detail.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+18

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

→ Reply

poao899

8 years ago, # ^ |

+18

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.

→ Reply

thedark

8 years ago, # ^ |

got it, thanks

→ Reply

Osama_Alkhodairy

8 years ago, # |

Where's round 1B analysis ?!!!

→ Reply

8 years ago, # |

Is anyone going to add the recent GCJ rounds to gym?

→ Reply

FieryPhoenix

8 years ago, # |

+10

Around what rating(estimated) would you have to be above to solve the first problem? Just curious about how far behind I am :) Thanks!

→ Reply

Kombu

8 years ago, # ^ |

+11

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

→ Reply

fruwajacybyk

8 years ago, # |

← Rev. 2 →

+18

I'd rather have small constraints (say n=1000 instead of n=10^6) than easier problems in small versions.

Now you have to test your large solution carefully, because there arent any pretests.

Fortunately I passed, despite of my c-large failed.

→ Reply

WasylF

8 years ago, # |

Is there any upsolving?

→ Reply

8 years ago, # ^ |

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

→ Reply

TooDumbToWin

8 years ago, # |

+41

How to solve large C?

→ Reply

yuizy

8 years ago, # ^ |

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. :(

→ Reply

WasylF

8 years ago, # ^ |

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

code

dbl getProb(vector prob, int n, int k) { vector work(n + 1, 0); // work[i] — probability that exactly i cores works fine sort(prob.begin(), prob.end()); work[1] = prob[0]; work[0] = 1 — prob[0]; for (int i = 1; i < n; i++) { work[i + 1] = work[i] * prob[i]; for (int j = i; j > 0; j--) work[j] = work[j] * (1 — prob[i]) + work[j — 1] * prob[i]; work[0] *= 1 — prob[i]; }

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

}

→ Reply

8 years ago, # ^ |

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. :(

→ Reply

P_Nyagolov

8 years ago, # ^ |

It's a well-known fact that if you know the sum of some numbers and you want to maximize their product, then you need the numbers to be as close to each other as possible.

In this particular problem, the only thing you can do to make the numbers close is to increase some small numbers so that they become closer to the big numbers we have (or increase all numbers so that they become closer to some greater value). In other words, our goal is to maximize the minimum among all numbers.

So let's do a binary search over this minimum. Once we fix some minimum V (which is to be maximized), we can take the sum of V - P[i] for all P[i] ≤ V. Then compare this sum to U and proceed with the binary search. Code goes here.

→ Reply

8 years ago, # ^ |

This is precisely what I did but still got an incorrect answer. Can you spot the error in my code?

→ Reply

hellman_

8 years ago, # ^ |

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.

→ Reply

Deep13

8 years ago, # |

can anyone tell me the approach for A-large B-large?

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

How do you account for a possible exchange at midnight with these DP states?

→ Reply

8 years ago, # ^ |

I take the answr for 24*60 + 1th second. Something is wrong with my code as it is currently failing the 1st test case itself, but I think if we take 24*60+1th second, we will get that exchange. This is assuming that there is always an exchange at midnight, unless the read the statement wrong.

→ Reply

8 years ago, # ^ |

+11

Not necessarily. If the same person starts and ends the day, then there would not be a midnight exchange.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

So that's what I'm doing wrong. Thanks!

Well in this case you need one more state to keep track of starting person.

→ Reply

yuizy

8 years ago, # ^ |

+17

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)).

→ Reply

8 years ago, # ^ |

This looks so much easier to code than what I did :|

→ Reply

pranshul

8 years ago, # ^ |

← Rev. 2 →

1.) Why do we need s i.e. "the first one to watch the baby"?. 2.) I kept the same state except "s" f(c,j,i) and struggled to take into account a possible exchange at midnight. My 1st and 3rd sample input return 1 instead of 2.

Link to my code:http://ideone.com/JiT8bW

[Edit] Got it. If the final person is same as the starting person, there is not need of an exchange at night.

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

Greedy is sufficient for A large. We can reverse sort based on radius. Then we choose each pancake as the base pancake, and choose k-1 other pancakes with at most this chosen pancake's radius with largest sum of surface area. Once the base pancake is chosen, we know the area of the disk is fixed, we just need maximum area on the sides.

→ Reply

8 years ago, # ^ |

Nice approach!

→ Reply

binary_eagle

8 years ago, # ^ |

Can it still be

dp[i][j] = max( dp[i-1][j] , dp[i-1][j-1]+ pi*r[i]*r[i]-pi*r[x]*r[x] + surfacearea(i).

Where x is the pancakes chosen at for the state (i-1,j-1).

→ Reply

8 years ago, # ^ |

This is not correct as it would subtract upper surface area of pancake x which is exposed to air.

→ Reply

binary_eagle

8 years ago, # ^ |

When the pancake x, was added at state (i-1,j-1), I added the upper surface area of x.

at (i,j), That pancake x, is glued to the ith pancake so it does not have a lower surface area. We need to subtract both circles of i and x.

then add the surface area of i. (assuming we choose i at this step.)

Hos is this incorrect please ?

→ Reply

8 years ago, # ^ |

Let x be the uppermost pancake of j-1 length stack having surface area dp[i][j-1]. We are adding pancake i to this stack. So, the area of x which is now covered by i should be subtracted from dp[i][j] and surface area* of i should be added.

*Note: We are not considering surface area of it bottom side

→ Reply

cegprakash

8 years ago, # ^ |

← Rev. 2 →

I solved it using DP.

1) Choose all possible top pancake. Let this index = prev.

2) DP[prev][k] = maximum surface area of choosing k pancakes when prev is the previously chosen pancake.

The complexity is much larger than it appears as there is an inner loop in the DP. Better approach would be to go with the greedy one by BlackVsKnight.

→ Reply

TooDumbToWin

8 years ago, # ^ |

+17

I used a greedy approach.

First of all, sort all intervals by start time (along with marking which one belongs to C/J). Now two consecutive intervals might belong to either same person or different person. The answer will atleast be the number of consecutive pairs with different person.

Answer will increase by 2 only when C looks after the child between two Js or if J looks after the child between two Cs. So I'll try to avoid these situations.

Code: here

→ Reply

MiteshAgrawal

8 years ago, # |

← Rev. 2 →

For problem A in round 1C, I wasted about 1.5 hour but couldn't find a mistake (many WA attempts) in the approach. I am solving it with dp(index, required) which is index position am currently on and required pancakes, this outputs two values, firstly best answer and secondly last disc index included in this answer, second part is used to add new disc area to existing stack. Finally required answer is DP(n-1,k).first.

I changed my approach at last to make it AC. But it will be really helpful if someone could guide me to the mistake in previous approach.

here is the code

→ Reply

8 years ago, # ^ |

firstly best answer and secondly last disc index included in this answer, second part is used to add new disc area to existing stack.

We cannot use best result calculated for i + 1 disks and attach it to i'th disk. It may be so that we need to take a disk with a smaller surface area on the i + 1'th place.

→ Reply

MiteshAgrawal

8 years ago, # ^ |

Please check the code, the fault is not in the algorithm, I am taking care of it in dp state traversal.

→ Reply