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

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

Discussion thread.

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

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

How to solve C?

is the solution binary search?

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

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

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

  • »
    »
    4 года назад, # ^ |
    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.

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

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

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

          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

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

          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

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

            [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

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

              Case:

              1
              4
              12 9
              37 25
              8 69
              9 2
              

              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.

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

            Case:

            1
            3
            1 100
            10 1
            3 50
            

            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

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

              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.

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

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        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.

    • »
      »
      »
      4 года назад, # ^ |
      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

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

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

    Link : https://ideone.com/zKxKGi

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

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

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

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

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

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            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.

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

              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.

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

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

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

»
4 года назад, # |
  Проголосовать: нравится 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?

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

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

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

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    if(x+y-z>n) puts(" IMPOSSIBLE");
    else{
        if(x==y && y==z){
            if(z<2 && n>1){
                puts(" IMPOSSIBLE");
            }
        }
    }
    
  • »
    »
    4 года назад, # ^ |
    Rev. 7   Проголосовать: нравится +5 Проголосовать: не нравится
    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
    
»
4 года назад, # |
  Проголосовать: нравится +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

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

»
4 года назад, # |
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

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

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

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

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

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

Anyone willing to help with this. Problem C

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

»
4 года назад, # |
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 ?

»
4 года назад, # |
  Проголосовать: нравится 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!

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

If anyone need Explanation for B Here