zoomswk's blog

By zoomswk, 4 months ago, In English,
Tutorial is loading...

Official Implementation: http://ideone.com/jsXSst

===

Tutorial is loading...

Official Implementation: http://ideone.com/YD7s4S

NOTE: If you get TLE, use faster input methods. For example, use scanf instead of cin.

===

Tutorial is loading...

Official Implementation: http://ideone.com/B9pjyi

NOTE: If you get TLE, use faster input methods. For example, use scanf instead of cin.

===

Tutorial is loading...

Official Implementation: http://ideone.com/nlPVW0

===

Tutorial is loading...

Official Implementation: http://ideone.com/cwP55b

===

Tutorial is loading...

Official Implementation: http://ideone.com/FfnJyp

===

Feel free to ask any questions below. It's hard to write an editorial that satisfies the need of everyone. I hope you'll enjoy solving the problems :)

 
 
 
 
  • Vote: I like it  
  • +79
  • Vote: I do not like it  

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for providing Editorial so quickly!!

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Suppose this is not optimal, and k’ + c (c ≤ 0) roads can be shut down. It should be c >= 0

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it's incorrect. I'll fix it soon. Thanks!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In problem C does this statement means it is a tree. "There are also n - 1 wires connecting the banks." Please why it is tree ?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        A graph with n nodes and n - 1 edges can be a tree, but it is not guaranteed to be. For example, there could be 1-2, 2-4, 1-4 edges (4 nodes). To be a tree, the graph (that has n - 1 edges) must also be connected (i.e. from every node we can travel to any other nodes using the edges).

        The condition "It is guaranteed that the wires connect the banks in such a way that Inzane can somehow hack all the banks using a computer with appropriate strength" given in the input section infers that the graph is connected, and thus a tree.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          "A graph with n nodes and n - 1 edges can be a tree, but it is not guaranteed to be." Yeah I had that doubt. Thanks for the clarification.

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

          This is the main part in solution. But I understand the remaining part of your ideone solution. would you mind explain this part why we are doing this ?

          if(x == 0)

          {
          
                  res = min(res, maxval+1);
          
                  if(y == 0) res = min(res, maxval);
          
              }
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            Consider x as the count of m + 2 and y as the count of m + 1 (after adding 2 to all banks' strengths).

            If there is no m + 2, then the answer is either m + 1 or m. If there is still no m + 1, then the answer is m.

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
              Rev. 5   Vote: I like it 0 Vote: I do not like it

              Sorry Again I can't get it.

              if(a[pos] == maxval) x--, y++; (in the minus section inside for loop j variable)

              if his neighbour's position is maxval so his nieghbour's value will increase by 1 we are doing x--, but why we are doing y++. (his neighbour's value will be maxval+1)

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it +4 Vote: I do not like it

                Because for neighboring nodes, if its original strength is ai, then it will be hacked with strength at least ai + 1 (that is, m + 1, in this case), so we will need to add 1 to y.

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

                  Thanks a lot. Now I understood. Your responses were quick.

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

      Hey !

      9
      7 6 7 6 7 6 7 6 5
      2 9
      4 9
      6 9
      8 9
      1 2
      3 4
      5 6
      7 8
      

      The answer for the above case should be 8 but your code is giving 9.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Are you talking about problem Bank Hacking?

        Why are there so many numbers in the second line? There are 11 numbers, but shouldn't there be 9?

»
4 months ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

In C, each bank’s strength can be increased at most twice

Isn't it, each bank's strength can be increased at most [ sum of adjacent node's degrees ] times. eg: consider the star graph. However the overall total updates will not exceed 2 * ( n — 1 ).

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hmm, why is it 2*degree times? Can you provide me a sample test case?

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

      a complete binary tree of depth 3 where the root is 1, and strength of each node is it's index number. The bottom nodes will be removed first, updating the root once. Now we severe the edges that connect the bottom most nodes to the tree. Now the bottommost nodes will be removed one by one and root will again be updated.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But you can't remove 2 bottommost nodes consecutively at first, because no bottommost node is neighboring to a hacked node (because hacked node is also at depth = 3). When you hack node at depth = 3, you'll have to continue hacking node at depth = 2.

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

          Missed that condition. My bad :| With this constraint, the problem is simpler than what I was solving :|

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If there are 4 nodes, 1,2,3,4 and edges are (1,2),(2,3),(2,4). If we hack in sequence 3,2,4,1, then 1st node's value will increase by 3. Please, clear my doubt.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            Node 1 and node 4 are not semi-neighboring when you hack node 4. Node 2 must be online in order for node 1 and node 4 to be semi-neighboring (refer to the definition).

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks !!! big mistake in reading problem statement. :(

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. Max update is 2

»
4 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

Problem E can be solved in as well using the dp which was used in IOI 2016's Task Aliens. 26284310

UPD as mentioned below 26298863.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Also you can instead of storing benefit of both geniuses assume that one of their benefit ended in that prefix, so original solution will be O(N * P) or with lambda optimization O(N * log(P) * K). It's awesome!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the lambda optimization or give a link where it is described? Is that one that is described in blog named "Incredibly beautiful dp optimization from N^3 to N^2logN"?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes , also check out editorial for ioi 2016's last problem , that has a pretty good explanation of this technique.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I have two questions about your code, thanks in advance if you can help clarify my doubts:

          1. Is the mult constant used just for the purpose of rounding the binary search?
          1. I am not exactly sure how does the penalty parameter in the check function helps to monitor the amount of peeking — is it used for setting a baseline for the score gained in each peek assuming that none of the peeking overlaps?

          Thanks again. :)

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it
            1. mult is used to avoid doubles.
            2. if you increase penalty , the number of items picked will be less and if you decrease it , the number of items will increase , so you can binary search on penalty so that exactly K items will be used.
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Would you mind elaborating what a and b in dp[i][j][a][b] in problem E are? I don't get what you mean by this benefit.

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Where are the official solutions ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    They have been posted. Sorry for the delay.

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

My solution in C that considers two starting vertices : any vertex with maximal value and vertex that has the most neighbors with maximal value passes the tests, can anyone prove correctness of such solution?

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone please elaborate more on C?

I didn't get the part after each node's strength is incremented by 2.

»
4 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Official Implementations are not available!

It says "You are not allowed."

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

    I've posted them on ideone. Please refresh the page.

»
4 months ago, # |
  Vote: I like it +28 Vote: I do not like it

C alternate solution:

  • if the MAX number appears only once, need to run a bfs (for case like: 8->7->7 (ans:9))
  • else if we can find a node where all MAX numbers are within its 1 level, ans is MAX+1
  • else ans is MAX+2

code

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    For "MAX appears only once" case it's enough to check whether there is MAX-1, which is not a neighbour of MAX.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explains: Suppose this is not optimal, and k’ + c (c ≤ 0) roads can be shut down. The tree will break into k’ + c + 1 components in problem D?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is a typo, that must be c ≥ 0. This is just to prove that shutting down k' - 1 roads we got from performing BFS is optimal. (That is, you can't shut down k' roads.) You can imagine a tree. Once you cut one edge, there are two components. If you cut two edges, there are three components. So if you cut k' + c edges, there will be k' + c + 1 components.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Add tag to problem E. Now its empty. Interesting hard problem.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i used problem D with dfs...And got wa on 6....I don't know why? here is my code :26286839 please help me....

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

    Last night,i also used dfs and got wrong answer. I found that my Dfs solution will give wrong answer on this test case.

    Image of the test case

    In my dfs visit order, i first vist the right police node and will not visit "visited-node" again. So when i start at the left police node, i can't visit the X-Blue node ==> wrong answer.

    That is my case. Hope it help :D

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

      I used dfs with cities containing police stations as starting vertexes while keeping track of distance of the current node from current police station during dfs. I removed a road if that road connects to the node whose distance is greater than d from the current police station. I also removed the road if that road connects with other police station because if from a city we can reach to more than one police stations in different cities with distance less or equal to d then there is no need for the extra road that leads to more police stations from that city.

      But still getting the wrong answer on test #6. Any help would be appreciated....

      My Submission

      Thnx...

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

        Ur method leaves some city isolated, and they don't connect any police station.So was mine.I have a simple example of such condition:With d equals 3, start from left, shut down 3 roads, finally leaves a city without police station isolated.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D

"With this method, you can see that exactly k’ - 1 roads will be shut down"

Can anyone explain this statement

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

    Imagine all cities being associated with their closest police station, and collapse this cluster of police station with it's associated cities into one node. This is always possible as the problem states that each city can go to at least one police station with distance <= d.

    Now, we have k nodes in the graph each representing one cluster. Remember that originally, we had a tree. So even after collapsing, these k nodes are still connected to each other and form a tree.

    Now we know that there exists exactly one path joining each of these k nodes, and we just have to delete these paths, as there is no need to join two clusters, since every city is already associated with one police station. And, for k nodes in a tree, we have exactly k-1 edges.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Problem C can be solved within O(N)? cannot understand the standard solution's algorithm.. Someone can help me?

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

"Why? It is because each bank’s strength can be increased at most twice, once by a neighboring bank, and once by a semi-neighboring bank".I don't understand why only once by a neighbor or semi neighbor since a node can have multiple neighbors .... can someone kindly explain what i am missing ? Thanks .

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

    Because the given graph is a tree and a tree can not contain any cycle. And you can only hack the neighbors of a already hacked bank.(except first one). Hope it helps

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is problem C solvable using DFS?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

One of my friends had a small problem while solving the C on the last contest. He used cin.sync_with_stdio(false); and cout.sync_with_stdio(false); and he got runtime error. We used this things and had no problem but this time got runtime error.. Is it a special rule for this ? Or where does this problem come from?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where did editorial for problem C disappear? :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV2-C: Got TLE in testcase 35. can anyone help me in analysing the time complexity of this submission Thank you in advance :)

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

Sorry! I don't understand why "y" is incremented here if(a[pos] == maxval) x--, y++;

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because they are neighboring, so its value is to be decreased by 1. From maxval, it would become maxval - 1. x should be decreased and y should be increased.

    On the other hand, if a[pos] = maxval - 1 you do not add anything, because it becomes maxval - 2 but we keep track of maxval and maxval - 1 only.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just to add to it,

    Notice that when a[pos] == maxval, it means that there exists a neighbor that is maxval.

    In this case, we don't want y == 0. Because if that happens, then

    if(x == 0){
        res = min(res, maxval+1);
        if(y == 0) res = min(res, maxval);
    }
    

    If you look at the code above if a[pos] = maxval, y > 0, so that min(res, maxval); does not happen.

    I think.

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

Here's my solution to C which doesn't need to iterate through all the banks to start with:

  1. Pick a bank with the maximum cost. Let this be the start bank and the max value be m.
  2. Initialise counters for the numbers of banks with cost m, m-1 and m-2.
  3. If there's a bank which is semi neighbouring our start bank and of the same cost, make the bank which is connecting them the start bank.
  4. If the start bank's cost is m, m-1 or m-2 decrement the respective counter.
  5. Go through the neighbouring banks of the start bank. If there's a bank with cost = m, we set temp ans to m+1. Also, decrement the counters if there is any bank in the neighbourhood with cost m, m-1 or m-2.
  6. At the end, if the counter of m > 0 (which means there are banks not in neighbourhood with the max cost, and hence they will be incremented twice), then ans is m+2. If the counter of m-1 > 0 or temp ans = m+1 then ans is m+1 else the ans is m.
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is a counterexample to the greedy solution of D? I don't understand why this doesn't work.

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    Consider this example

    6 2 2

    1 5

    1 2

    2 3

    3 4

    3 5

    3 6

    If you traverse greedily and delete parent of nodes greater than d distance or nodes with station on it,

    After starting from node 1, you will end up deleting edges (3,4) (3,5) (3,6). But nodes 4 and 6 are reachable from node 5.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In your example, d = 2 or d = 4?

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

      Yes I saw that this doesn't work, but assume that you always pass the minimum distance (-1 if none exists) to a police station in your subtrees to your parent when you moving up the dfs tree. Now you only cut edges if the distances has exceeded d. So in your case we would have cut (1,2) when coming back from 2 to 1. And we cut as well if we arrive at a police station moving back up and some police station is present in the subtree.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have something wrong with problem D. My two submission (1 in-contest, 1 practice, but both are the same) got TLE on different test cases, although it provided the output.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think all TLE solutions on Codeforces show output like this, but in fact it is the jury's answer.

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem C can be solved with the segment tree. It's really faster than multiset and data structures like it. Maybe it a bit harder in implementation, but we get so far from TLE instead of multiset. Maybe, someone can suggest more easier way? ( I know about O(N) solution, but interesting in O(NlogN) with data structures ). Solution with segment tree ( 700 ms ) — http://codeforces.com/contest/796/submission/26302092 Solution with multiset ( 1800 ms ) — http://codeforces.com/contest/796/submission/26299257

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

As for Div2-C, I cannot quite understand how the maximum strength can be m + 2.

Number of Vertices : 7

  1. 1 2
  2. 2 5
  3. 3 2
  4. 2 4
  5. 1 7
  6. 7 6

Please refer to the example above. If we were to hack the banks in order of 2, 6, and 7, wouldn't bank #1 have strength + 3 ? From my understanding, the process is as follows;

  • (s) stands for semi-neighbor.
  1. Hack 2 -> {1, 3, 4, 5, 7(s)} get + 1 strength
  2. Hack 6 -> {1(s), 7} get + 1 strength.
  3. Hack 7 -> {1} gets + 1 strength.

Please correct my thoughts.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am definitely an idiot to miss reading below problem statement;

    Bank x is neighboring to some offline bank.

    Thank you for the interesting problem zoomswk !

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used greedy approach for problem E. I got WA on #12, the input is big, so I can't check by hand, where my algorithm went wrong. Probably there is a mistake in my theorem about the algorithm's correctness. Can someone point out why is the approach wrong, or tell, I have only failed in implementation?

Algorithm: We store 3 boolean arrays, the answers first and second genius got right, and the answers we have already copied. We check the maximum copiable answer number (we can do this in O(n) by pushing a window of size k from 1-n), then we copy the answers which produces the maximum copiable answers. We do this p times, so every peek we get the maximum number of answers correct. Total runtime is O(np).

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    14 2 7
    6 1 6 7 8 9 14
    0
    
    

    It looks like this: 10000111100001.

    So, your algorithm will take the middle segment first, and will be unable to cover the two remaining questions. But the optimal answer takes 2 segments [1, 7] and [8, 14].

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is so special about testcase 13 in problem D? My code seems to do the same thing as you wrote :/ http://codeforces.com/contest/796/submission/26274912

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    notice that your code never goes into this segment: if (D[a] < d) because 0 < 0 is false.

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

Can someone explain state transitions for problem E in detail?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C:

What is the differance b/w map and hashmap?

Also, from editorial "However, each operation involves the map data structure, so the overall runtime is O(nlogn)" How map access adds log(n)? Isn't map access is a constant time operation O(1)?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C++ map and Java TreeMap are usually implemented with a balanced tree (like Red-Black) with each operation being O(log n) while C++ unordered_map and Java HashMap use a hash table with amortized O(1) operations.

    Thus n operations on a map/TreeMap take O(n log n) time but only O(n) amortized for unordered_map/HashMap.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think O(1) is just average, not amortized. Amortized complexity has to be guaranteed. In the worst case, unordered_map and HashMap work in O(n) per operation.

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

Waw problem E solution is pretty dense

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

Hello, for problem D your algo gives wrong output for following input(at least my implementation did :( )

5 2 2
1 4
1 2
2 3
3 4
3 5

the output should be 1 2. But mine give 1 3. (thus leaving node 5 3 miles away!)

The problem is, If we traverse those cities with police stations as given in input city 3 is marked visited by city 1. And when city 4 comes to city 3 it finds it already visited and cut the road(This will leave city 5). How can i fix it?

If someone is interested in source code it can be found 26301147

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to run BFS simultaneously from all cities with a police station. See the provided code and ask if you don't understand.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you. got AC :)

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

      You probably should have mentioned that in the editorial you know. :)

»
4 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Thanks for the useful editorial.

In the Official Implementation of Problem C,

the // plus part (lines 44-51) could have been replaced with two lines:

In line (28): int x1 = x, y1 = y;

In line (43): x = x1, y = y1;

The following verifies the correctness of the observation:

http://codeforces.com/contest/796/submission/26337076

And the following is a C++ class implementation:

http://codeforces.com/contest/796/submission/26321000

Best Regards

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sure, that works too. Thanks for pointing out. I just copied-pasted from the minus part and changed the signs, so I didn't notice this. XD

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So at first I didn't really understand why we need to clear out DP[next_layer][j][a][b] to a negative instead of just 0's at the end of each i iteration. Is this because DP[i][j][a][b] is not really "valid" for the case where i + a < k or i + b < k when j >= 1?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Mainly because it's already wrong for cases like dp[layer][0][k - 1][k - 1], so the next questions can use the invalid glance. So I just set it to a huge negative value to be sure.

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

In official implement of problem D.

can someone please explain why set v[pos] = 1 here

   if(v[pos]) continue;
        v[pos] = 1;

instead of set v[way[pos][i].first] = 1 when

   else q.push({way[pos][i].first, pos});

is met?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's a matter of style. I'm just used to implementing this version of BFS. :)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I get WA if I modify your code

       while(!q.empty()){
              int pos = q.front().first;
              int from = q.front().second;
              q.pop();
              // if(v[pos]) continue;
              // v[pos] = 1;
              for(int i=0; i<way[pos].size(); i++) if(way[pos][i].first != from){
                  if(v[way[pos][i].first]) res[way[pos][i].second] = 1;
                  else{
                  	q.push({way[pos][i].first, pos});
                  	v[way[pos][i].first] = true;
                  } 
              }
          }
      
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry for the late reply. It shutdowns all roads connected to cities with multiple police stations. You have to modify the algorithm to push to the queue only once per each city with police stations.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E In your code, you didn't calculate dp[i][j][k-1][k-1].

dp[i][j][k-1][k-1] = max(dp[i][j][k-1][k-1], dp[i - 1][j - 2][0][0] + (A[i] | B[i]));

Why is it right?

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

    It's never better to start looking at both answer sheets at the same time. In the optimal strategy, if there is the answer on both answer sheets, you can just start looking at one of them.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now I have deeper understanding of the state of DP. Thank you very much~

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you tell something about how to find the definition of the state in DP in problem E? I find it rather difficult.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can only recommend you to solve more DP problems. I found it hard to define states when I was new too, but things become better as I have more experience. :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain problem E clearly ??

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Which part don't you understand? DP formalization, time optimization, or memory optimization?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      index a and b :/

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

        As can be seen in my code, when you decide to start looking at some question, you'll have a (or b) set to k - 1. That's because once you start looking, the next k - 1 questions can be looked at at no cost (you pay only for the index i). Hence, a (or b) means the number of the next consecutive questions that can be looked at for free, as the benefit of the recent glances.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am having some trouble trying to upsolve D. I don't know if it is my approach that is flawed or the code. My idea is start at a station then DFS to of a distance of 2*d+1. If I find a station while doing this I immediately backtrack and make a cut halfway between the two stations if there are an even number of nodes between them or closer to the original station if there are an odd number of nodes between them. Then I store the cut and stop exploring the part of the branch below the cut. I repeat until I either make k-1 cuts or have started a DFS from each station. My code http://codeforces.com/contest/796/submission/26412721 works until case 7 which is so big I can't figure out exactly where it goes wrong. If anyone could point out an error in the approach, code or generate a smaller test case that breaks it that would be appreciated.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    10 3 3 1 6 7 1 2 2 3 3 4 4 5 4 10 10 9 9 8 8 7 10 6

    City 5's nearest police station will be 4 kilos away with your algorithm.

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

      Thanks that should help debugging.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Great example I now see why the approach can't work. The DFS can break a link between nodes that are far away before it breaks links between nodes that are closer.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problom D. example 5; There are 300000 plice stations,but the answer is not 300000-1. I don't know why.Could you help me?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Some police stations are in the same cities. In the editorial, k' is used to denote the number of cities that have at least one police station in them.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem c, If there are 5 nodes,with strength 10,1,1,1,10 and edges are (1,2),(2,3),(3,4), (4,5). If we hack in sequence 1,5,2,3,4 The answer for the above case should be 10 but your code is giving 12.Please why it is wrong

»
4 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Couple things with the solution for Problem C that I am confused about.

  1. What exactly do x = 0 and y = 0 signify? Figured Out: The ties between all the (maxValue)s and (maxValue-1)s are severed.
  2. What is the point of going back through and setting x and y to their original values before a particular iteration of the "i" loop? Wouldn't a dummy variable save time?
  3. Why are semi-neighbors not checked in the "j" loop? Figured Out: You already know the answer is one of three values, and you just need to check if all the (maxValue)s and (maxValue-1)s are in the same "flower" (one center node that is (maxValue) with "petals/leaves" stemming out of it to (maxValue-1)s).

Can someone now verify my arguments?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Yes.

    2. I didn't think of it. You can create dummy variables if you want.

    3. We assume that hacking each bank i needs strength ai + 2, but this is not true for the bank you start with and its neighboring banks, so we have to update the strengths required to hack those banks required accordingly. Hacking semi-neighbors cost ai + 2 anyway so we don't have to update them.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the solution for Problem E, is the switch between curr and prev a result of which 3-D table has the previous values? As in, do the previous values alternate between being stored in i = 0 and i = 1?

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

for problem D: the variable d is unuseful?

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

    I'm not sure but alternative (but more complex) solutions seem to exist, taking variable d into account. However, it is useless for the described solution :D

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

      Oh~Thanks (Useless..I am so weak in English.

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

"It is because each bank’s strength can be increased at most twice, once by a neighboring bank, and once by a semi-neighboring bank." I don't understand this. Each bank may have more than one neighboring bank, so the bank's strength could be increased multiple times, more than 2 times at least.