Блог пользователя starboy_jb

Автор starboy_jb, история, 6 лет назад, По-английски

Discussion thread.

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

is the solution binary search?

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +9 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, скрыть # ^ |
    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.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +1 Проголосовать: не нравится

        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.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
        Rev. 2  
        Проголосовать: нравится +1 Проголосовать: не нравится

        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.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    Link : https://ideone.com/zKxKGi

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +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.

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +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])

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
Rev. 5  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by starboy_jb (previous revision, new revision, compare).

»
6 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

This blog was made private before .Please check few comments here to get new ideas or to help someone link

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Anyone willing to help with this. Problem C

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

»
6 лет назад, скрыть # |
Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

For Problem C,

Can anyone please explain what we do after establishing that Ei + Ri >= Sum. Ei.

How did we proceed forward ?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
My Solution for Problem C

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!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

If anyone need Explanation for B Here