Google Kick start Round E 2020

4 years ago, # ^ |

It seemed binary search, but couldn't pass with it.

→ Reply

4 years ago, # ^ |

Keep the current sum of all nodes in the current circle. Keep a priority queue / heap of indexes and values e[i] + r[i]. If there are no indexes with e[i] + r[i] > circle sum, then he can go on to infinity. If there are, then take all those indexes to another priority queue and take the first index and remove it. Then check if there are any new indexes with e[i] + r[i] and add them to the priority queue for lowest index, etc.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

+13

You can solve it using binary search on time, but you don't need to. First let us notice that a toy $$$i$$$ is fine to play with if $$$E_{i} + R{i}$$$ >= sum of $$$E_{i}$$$ of toys taken. The first cycle will always complete, so lets just assume thats happened. Now in the second cycle of iteration, note that if the $$$i$$$-th toy makes the child sad we don't care about the $$$j$$$-th toy for any $$$j \gt i$$$. So basically we iterate through the toys in order keeping track of the current sum of $$$E_{i}$$$ of those that remain. For the $$$first$$$ bad one we find, we remove it, till then we keep tossing them in a set / pq which is in descending order. We use this set / pq to store the current $$$E_{i} + R{i}$$$ of the good ones. If after some removal (and the resulting reduction of the sum) the largest of this set becomes bad, remove it as well, repeat while set is non empty. Take max of the time in each step of the iteration. If after a full iteration across the n elements any element is remaining, it will always be good, the answer is inf in that case.

→ Reply

4 years ago, # ^ |

I did the same, but I made sure to always take the leftmost "bad" element (I'm not sure if you specified to do that, though you wrote that the toys after the last one don't matter so idk).

→ Reply

4 years ago, # ^ |

Yeah that is what I meant, if at any point, I found a bad position, I removed it, updated the sum and then kept on removing the top of the set of good values if they had become bad after the last removal ($$$E_{i}$$$ + $$$R_{i}$$$ >= sum of $$$E_{i}$$$. But you're right, I didn't state that clearly enough, edited to add that.

→ Reply

Invaders

4 years ago, # ^ |

Can somebody tell me a test-case where my brute force solution for C fails ? (I simply generated all the subsets) Link : https://ideone.com/zKxKGi

→ Reply

https://ideone.com/OoRXdW

4 years ago, # ^ |

Your output: 2 15
Correct output: 0 13

→ Reply

harshpathak17

4 years ago, # ^ |

Hey, thanks for your solution. I wrote my own code based on your idea but I am still getting a wrong answer for N <= 12. Can you please provide me a simple testcase where this should fail?

→ Reply

tocolor

4 years ago, # ^ |

[user:BumbleBee][user:karkl_10][user:ExplodingFreeze]

I have tried a similar approach, but getting WA, anyone willing to help

code Link: https://ideone.com/60YHAb

→ Reply

4 years ago, # ^ |

Case:

We have to remove the 2nd and 3rd to get it to run indefinitely, but your code prints 1 INDEFINITELY which is impossible. I'm unable to figure out where exactly you're making a mistake, but I think it might be similar to the issue with [user:karkl_10]'s code, so check my response to his comment.

→ Reply

tocolor

4 years ago, # ^ |

Thanks :)

→ Reply

4 years ago, # ^ |

Case:

Clearly we can remove the first one and we will visit 2 -> 3 -> 2 -> BAD for a total sum of 23 with 1 deletion, so 1 23. However your code prints 0 23. I'm pretty sure the mistake occurs from the below line, you minimize $$$min$$$_$$$deletions$$$ even when the new time is better (you are using the number of deletions for $$$t = 14$$$ while taking the new best time of $$$t = 23$$$).

bestans = max(bestans, running_sum + firstround);
if(bestans == running_sum + firstround){
    min_deletions = min(min_deletions, cur_deletions);

Changing these lines to something like

if(bestans == running_sum + firstround)
    min_deletions = min(min_deletions, cur_deletions);
else if(bestans < running_sum + firstround)
    min_deletions = cur_deletions;
bestans = max(bestans, running_sum + firstround);

fixes this issue and should allow your code to get AC (unless there is some other mistake as well). I actually made the exact same mistake while coding subtask 1, thankfully found it after looking through the code for 4-5 mins.

Your original code which fails this case — https://ideone.com/fM5SUU

Fixed code which passes this case — https://ideone.com/qoqaPn

→ Reply

harshpathak17

4 years ago, # ^ |

Hey, thanks for analysis of my code. I am still getting a wrong answer for some reason, but atleast this code is better than my last one. I am probably making another subtle mistake somewhere.

→ Reply

yp7398

4 years ago, # ^ |

Could you explain why are we removing the toy with the highest Ri+Ei value first?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I think you misunderstood, we aren't removing the toy with the highest $$$R_{i}$$$ + $$$E_{i}$$$ value first. The toy which we encounter first while iterating it order which fails the condition is the one we are removing, since obviously we cannot proceed any further as long as this one remains and thereby the time can't improve.

However the set / pq contains all the ones we've encountered till now which are good. We want to keep them as long as it remains good so as to minimize the number removed. Any toy becomes bad if its $$$R_{i}$$$ + $$$E_{i}$$$ value exceeds the sum. So of the good ones we have remaining, if after some step the sum reduces, they may now become bad and have to be removed. Obviously any value with a larger $$$R_{i}$$$ + $$$E_{i}$$$ value cannot remain good longer than one with a smaller value, so we can store these in descending order, so we can check the first value to see if any of the previously good ones have become bad and need to be removed.

→ Reply

yp7398

4 years ago, # ^ |

Got it! Thanks for the nice explanation

→ Reply

kati-patang

4 years ago, # ^ |

← Rev. 2 →

If instead of (Ei + Ri) we insert only Ri(as a decision variable) into priority queue, then i got WA. I couldn't figure out the difference between the two. Here is the incorrect code(based upon Ri): https://rextester.com/RWWMVJ61195 Here is the corect code(based upon Ei + Ri): https://rextester.com/JWRVG10647

→ Reply

Invaders

4 years ago, # ^ |

Can somebody tell me a test-case where my brute force solution for C fails ?

Link : https://ideone.com/zKxKGi

→ Reply

4 years ago, # |

+11

How to solve D?

I was thinking about doing something like floyd-warshall for distances between nodes, using that store the closest of each stone of each type (and somehow possible recipes) for each node and then dijkstra on the least energy with some state like {node, stone} but couldn't come up with anything concrete.

→ Reply

4 years ago, # ^ |

I tried to solve problem golden stone by going through every junction and choosing it as the center. I then did bfs from it to get the shortest path to every stone available in a junction. Then I went through the recipes by using an approach similar to djikstra (recipe with smallest sum of stone costs first). I got WA though, though I'm not sure if the approach is the problem or my code.

→ Reply

4 years ago, # ^ |

https://codingcompetitions.withgoogle.com/kickstart/submissions/000000000019ff47/TmVrZG8 here is my submission.

→ Reply

4 years ago, # ^ |

My approach is wrong since I only use recipes at one node while it can be optimal to use them at differnet nodes.

→ Reply

ijxjdjd

4 years ago, # ^ |

+14

It's a weird dijkstra. Transform the graph to {node, stone} to be the minimal cost to get "stone" at "node". The answer is clearly min{node, 1} over all nodes. Transitions are {node, stone} + 1 -> {e, stone} for each edge at node. Recipes can be calculated in a similar way. Whenever {node, stone} is processed in the dijkstra, iterate over all recipes with "stone" in the creation process then use this to transition to {node, result} where result is the result of the recipe and the value will be {node, s} over all "s" in the recipe. For each node, there will be at most $$$3RN+MS$$$ transitions over all $$$NS$$$ nodes. Dijkstra works here because each transition is non-decreasing.

→ Reply

4 years ago, # ^ |

+16

Can you tell if this Dynamic programming is equivalent ?

DP[i][j] = Cost to product stone j at city i

I check 3 ways :

If stone j is located at city i , cost = 0
Create jth stone at another city and bring it to i, cost = DP[k][j] + dis[i][k]
For a recipee R that generates stone j, cost = Sum over all ingredients v of R (DP[i][v])

→ Reply

so_close_yet_so_far

4 years ago, # ^ |

← Rev. 3 →

+13

Your recursion is cyclic if the recipes are cyclic. So the dp values you compute are not correct.

→ Reply

4 years ago, # ^ |

+13

I set DP[i][j] = -1 Initially

In the recursive function, If DP[i][j] != -1 return DP[i][j] else DP[i][j] = 10^12

Calculate here....

→ Reply

so_close_yet_so_far

4 years ago, # ^ |

← Rev. 3 →

+13

I believe you are talking about this code. The reason you are getting WA instead of TLE/RE is because you are setting res = INF and the next time you visit here you are just returning INF or some intermediate value thinking that you have already computed the answer for this state. This slightly modified code gives RE because of infinite recursion. I tried to find a counter case to fail your code but I was not successful. But I think the problem is precisely this.

→ Reply

4 years ago, # ^ |

Thanks, I seem to get it.

I thought it will follow Acyclic order of evaluation, but it is not the case.

Technically I should get WA on subtask 1 too.

→ Reply

4 years ago, # ^ |

By non-decreasing do you mean that there are no negative edges (that no move decreases the cost)?

→ Reply

AlexFetisov

4 years ago, # ^ |

I solved a little bit differently, but kind of similar idea.

So basically easy can pass with something like Ford Bellman. Initially we don't use spells. And then we iterate for every spell until we can improve. That TLEs for big one.

But if we improve with some spell the only thing we can update is the cost of the result stone of that spell. Then we only need to check spells, where that stone is an ingredient. That actually works pretty fast on the test set.

→ Reply

ajayNegi

4 years ago, # |

Lots of participant couldn't solve B. Is if(a+b-c > n || c > a || c > b || c==0) enough for the answer to be IMPOSSIBLE or am I missing something?

→ Reply

BohdanPastuschak

4 years ago, # ^ |

+11

Well, 1 <= c <= min(a, b) from constrains already. But if $$$n > 1, a = b = 1$$$ there is no answer too.

→ Reply

nilesh8757

4 years ago, # ^ |

it was given 1 <= c<= n , a >= c, b >=c

→ Reply

4 years ago, # ^ |

if(x+y-z>n) puts(" IMPOSSIBLE");
else{
    if(x==y && y==z){
        if(z<2 && n>1){
            puts(" IMPOSSIBLE");
        }
    }
}

→ Reply

cis_pie

4 years ago, # ^ |

← Rev. 2 →

too much casework for B?

→ Reply

4 years ago, # ^ |

I had to stress test to discover those cases.

→ Reply

cis_pie

4 years ago, # ^ |

Can you share some corner cases?

→ Reply

_whysonew_

4 years ago, # ^ |

try this

i think you can reduce the casework i you write a complete brute force for n=2 n=2 costs me almost 6 penalties

→ Reply

Tru3R00T

4 years ago, # ^ |

← Rev. 7 →

I have used buildings of three types n, n-1, 1 then the following cases.
let left = n-a-b-c
Then if c > 1 : (n-1)*(a-c) + (n) + 1*left + (n)*(c-1) + (n-1) * (b-c)
else : 
if (a-c) > 0 : (n-1)*(a-c) + (1) * (left) + n + (n-1) * (b-c)
else if (b-c) > 0 : n + (1) * (left) + (n-1) * (b-c)
* denotes No of times used 
+ denotes concatenation
This construction worked for me. but i also included checks such that size of buildings included == n && no. of buildings seen are equal to that given in problem.
This passed

→ Reply

4 years ago, # |

How am I getting AC in subtask 1 and WA in subtask 2 for Problem D, (I guessed TLE would be okay)

Code : https://pastebin.com/z9j9bSQ8

→ Reply

4 years ago, # ^ |

+13

Very possible that it's an overflow if your solution is correct. In my case I just set every path length if it was larger than 10 to the 12 back to the 10 to the 12 (since it doesnt matter how much bigget it is). I did this and it solved both subtasks.

→ Reply

4 years ago, # ^ |

It is incorrect actually.

→ Reply