Discussion thread.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
Discussion thread.
Name |
---|
How to solve C?
is the solution binary search?
It seemed binary search, but couldn't pass with it.
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.
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.
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).
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.
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
Your output:
2 15
Correct output:
0 13
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?
https://ideone.com/OoRXdW
[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
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.Thanks :)
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 prints0 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$$$).Changing these lines to something like
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
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.
Could you explain why are we removing the toy with the highest Ri+Ei value first?
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.
Got it! Thanks for the nice explanation
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
Can somebody tell me a test-case where my brute force solution for C fails ?
Link : https://ideone.com/zKxKGi
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.
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.
https://codingcompetitions.withgoogle.com/kickstart/submissions/000000000019ff47/TmVrZG8 here is my submission.
My approach is wrong since I only use recipes at one node while it can be optimal to use them at differnet nodes.
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.
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])
Your recursion is cyclic if the recipes are cyclic. So the dp values you compute are not correct.
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....
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.
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.
By non-decreasing do you mean that there are no negative edges (that no move decreases the cost)?
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.
Lots of participant couldn't solve B. Is
if(a+b-c > n || c > a || c > b || c==0)
enough for the answer to beIMPOSSIBLE
or am I missing something?Well, 1 <= c <= min(a, b) from constrains already. But if $$$n > 1, a = b = 1$$$ there is no answer too.
it was given 1 <= c<= n , a >= c, b >=c
too much casework for B?
I had to stress test to discover those cases.
Can you share some corner cases?
1 2 1 1 1
i think you can reduce the casework i you write a complete brute force for n=2 n=2 costs me almost 6 penalties
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
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.
It is incorrect actually.
How are you getting the AC in subtask 1 then?
upd : i found the error. I tried to solve C using multisets .I removed a toy if "sum of enjoyment of other toys" < "remembrance of current toy". Can some one tell test case where it fails. code
Auto comment: topic has been updated by starboy_jb (previous revision, new revision, compare).
This blog was made private before .Please check few comments here to get new ideas or to help someone link
Anyone willing to help with this. Problem C
code Link: https://ideone.com/60YHAb
For Problem C,
Can anyone please explain what we do after establishing that Ei + Ri >= Sum. Ei.
How did we proceed forward ?
My solution is rendering a WA. Can someone please give me a test case where it fails ? I checked it with all the samples mentioned before in this thread and it passed all of them. Please do help!
1
3
4 15
12 20
13 2
The answer should be:
0 33
Thanks a lot for the test case! It helped me understand my error.
If anyone need Explanation for B Here