fcspartakm's blog

By fcspartakm, history, 3 weeks ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +49
  • Vote: I do not like it  

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

What's the complexity of F?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n^2lgn,I think

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O(n^2logn + qlogn)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Won't it be TLE?

      I'm afraid if it'll be TLE and I optimized it to O(nm+q).

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Wow, How could you answer each question in O(1) ?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          DFS on the tree and maintain the DFS stack. It's off-line.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My O(n^2logn + qlogn) solution passes in 700ms.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it won't throw TLE in java if u are conscious abt what u r doing

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem E, why is it necessary to sort items, or I will get the wrong answer?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    If we implement only a simple knapsack for the problem then we wont get the optimum answer.Check this case

    2

    2 4 100

    1 2 100

    answer is 200 we can save object 2 and then save object 1.But we lose the number of the object after sorting.How can we get back the order??We can store the indices in a structure format or map them before sorting.I used structures because it was comfortable for me.My structure had t,d,p and then num(where t is time needed to save,d is time after which the object cant be saved,p is the value and num is the initial position of the object before sorting).

    Hope this helps.Let me know if you have any difficulty.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Thanks. I just wonder why I must sort these items. And now I see it's because selecting these items in different items will get diffrent answers, but normal 01 knapsack won't.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I've just got an insight about problem E: Fire.

    I believe that its plot is perfectly described in the scene youtube: "Quicksilver saving mutants from explosion in Xavier's school basement" // "X-Men: Apocalypse".

    So my editorial is: imagine that d[i] + 1 is the time moment when explosion hits the i-th creature and try to be as good as Quicksilver even though his ways of always getting Σ p[i] did a fresh change to the problem overall perspective)))

    Here is the screenshots for Chinese users (0.5 MB)

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My solution is literally O(nm + q) but it is distincly slower than other solutions

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E why does sorting elements based on parameter d gives us the correct solution? I cannot understand the logic behind it from the tutorial.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    basically its about the order of choosing items . its better to choose the items first that will be burned sooner right ? because if you dont choose them fast (if its better to choose them) you probably cant choose them ever

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

30745421 whats wrong with my code of D...I followed this editorial did I missed something..

»
3 weeks ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my program not work in task B. In my computer its working good! http://codeforces.com/contest/864/submission/30750759

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Console.ReadLine(); string a=Console.ReadLine();

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And what??

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        // read n
        Console.ReadLine();
        // read string s
        string a=Console.ReadLine();
        
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for E is not printing right items. Can anyone help me? My submission is LINK

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have the same error in my code. The issue with the order can be fixed through sorting. I assume you are sorting just based on the 'd' values. If so, then when 'd' is equal, the item with lower 't' value should come first. This solved the order disparity for me...however there is also a problem that while printing one item is skipped (I have the same problem too)...I have so far no idea why this happens.

    Edit: The order might not be the real issue here...the answer is probably still valid. The main issue is the fact that one item is skipped while printing.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why it is printing one item less when it is giving correct value ? I am not able to understand.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I rewrote my solution to print the value of the answer from the constructed solution and it turns out it gives the same answer. This shouldn't be the case...if our constructed solution were wrong we should get a smaller value...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Cana anyone please explain the solution idea of problem 864F — Cities Excursions. I have read the editorial but I can't catch the idea :( .

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I couldn't catch the last two paras of the editorial, but here's what I understood-

    Suppose we are at sj node currently. Now, consider all nodes connected to it with an edge, and let u be the lexicographically minimum among them, from which we can reach tj via dfs/bfs. Obviously it will be optimal to pick u. Because, from u we can still reach tj node from u-maybe at an infinite time(ie, never actually reach it). That is, we greedily select the next node. This gives us an n*q solution, what the last two paras did is to optimize this part.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

"The lexicographically minimal path from the vertex sj to the vertex tj is equal to the inverted path from tj to sj in this tree." Please elaborate. Problem F.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem E, the editorial wants dp[i+1][j+t] to be found as the maximum of itself and some other number. Is this a typo? It doesn't make sense to find a value with itself.

And it does this in the second line, as well

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I was also confused at first, but it makes sense if you think of all the values of dp as initially 0. So after initialization, it is just about upgrading the values of dp through those seemingly recursive relations.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give a more detailed explanation regarding F. I am unable to understand it from the tutorial. It would be really nice, if you could explain the implementation details as well.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

And what is binary climb?

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem A 4 1 2 3 4 what answer should come with this input .My answer is

YES

1 2 3 4 but its wrong

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Somebody help me with Problem F,Test 13? I use Tarjan to check if there is a cycle,while always get WA on Test 13 I see many people get the same problem with me , how to correct it?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try out these cases, they were useful to debug my idea:

    4 5 1 1 2 1 3 2 4 4 2 3 4 1 3 1 Ans = 1

    4 5 1 1 2 1 3 2 4 3 4 4 2 1 3 1 Ans = 1

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem 864E-Fire, Consider this case :

3
20 21 20
3 6 1
4 8 2

Now if we sort the d parameter, then we select the 2nd element first because its d value is the least(6) and then the 3rd element, whose d value is 8. But using this method, we ignore the 1st case, where if we only save the 1st item, then we will get the maximum value of saved items, which will be 20. So can anyone please explain how we can solve this just by sorting the d parameter?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you may got the answer 20 in dp[3][20], because dp[3][20] = dp[2][0]+20 = dp[1][0]+20 = 20, and why we can simply solve this by sorting d was explained at before