caioaao's blog

By caioaao, 9 years ago, In English

Hello, yesterday we participated in ACM ICPC 2014 South America Finals in Brazil. We'd like to know if there are websites that we can check the final results from other regions. Also, if you have info on how to solve some problem, please post it here :D

Thanks!

Link to the online contest:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=339

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I think you meant Latin America Regional, right? ;) Here is the unofficial final scoreboard: http://score.bombonera.org/latam2014/ About the problems, do you have any in particular that you would like to hear about the solution? :)

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

    Thanks for the scoreboard! And I've corrected the title, thanks for pointing it out...

    I'd like to know about D, F, J and K. The only one I had a clue about how I'd start was F, but couldn't come up with a working solution in the last 30 minutes

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

      K: the problem in a line would be pretty easy, the issue is circularity. However, it's possible to find a point between two seats such that no soldiers will cross that point in any valid order. Then you can cut the circle in that point and solve the much easier linear version.

      I have an idea about D, but I won't explain it until I try it. I'm pretty curious about J, though. :)

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

        did you manage to code the k ? I've found a lot of properties but im still unable to code it .

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hi, I know it's been 3 years, but I'm trying to solve problem K and I can't help but ask for additional tips because I still don't get it. Even if I follow your tip and think of a line version of the problem, I'm still unable to see why it is "pretty easy". My best insight so far is that you can split the K — D remaining knights into two groups: (1) those who have their seat available and (2) those who have their seat occupied by somebody of the first D knights. The knights of group (1) will always go straight to their seat unless one or more knights of group (2) enter first, move clockwise and seat to the right of an "island" of occupied seats and thus end up occupying a seat of a knight of group (1). But besides this I haven't figured out yet the combinatorial pattern in this. Any help will be deeply appreciated.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      D: construct trie of all strings, then do dynamic programming on this tree with state (node, number of children that will become street names). Complexity is O(n3L), with L being the maximum number of letters (18).

      Edit: details are pretty standard, but here they are: Each abbreviation is used on exactly n intersections, so we want to compute the quantity n * (sum of lengths of all abbreviations).

      DP(node, number of children that will become street names) computes the optimal sum of the lengths of all abbreviations of all children of this node of the trie. Note that the second parameter also determines how many nodes will become avenue names, and so the answer we want is n * DP(root, n).

      Explaining transitions is a bit boring, but it shouldn't be too difficult to figure out. If you only have one street name in the whole subtree, then you can already use the node you're at as an abbreviation, same thing for avenues. Then try all possible ways to split the streets between the children of this node.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      F: Perimeter is easy: it's just the perimeter of a rectangle that encloses all points. Real problem is the area. Line sweep all points from left to right, keeping the current top and bottom coordinates of the fence, stretching and shrinking as necessary. That is, whenever you find a new point, stretch the fence until it covers it; and whenever there are no more points with more/less than a certain y coordinate, shrink the fence.

      Implementing this might be a little complicated. A handy implementation tip to make it simpler is to consider a single point (x,y) as 4 points (x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1), which lets you avoid the "not able to touch points" condition. The "not able to touch fence" condition is a bit nastier, and it requires creating line sweep events at x+1 for every point. You can see my code for a use of this idea.

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

        I solved this problem during contest and my approach was similar, but I never shrank the fence, since I did two line sweeps: from left to right and then from right to left. In the first line sweep I stored the points of the left side of the fence while stretching it. Then I used all points (those from the input and the ones I stored during the first line sweep) to do the second line sweep, this time stretching the right side of the fence. This trick let me deal with the "not able to touch points" condition.

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

      Finally got J (yay for monologues), even though admittedly I had to ask StefanoT for a hint.

      OK, so the problem is asking for the smallest path between two locations. We could probably use Dijkstra here to solve it, but the complexity is O(ElogV) and the amount of edges is too big. We want a way to cut those to a reasonable amount.

      The trick: all edges leaving a certain location have the same cost, so visiting that location already means you will have to pay that cost anyway. For this reason, we can consider that the cost of the edges that reach a node is the amount you will have to pay to leave it.

      Why does this help? Because we now have a very useful property: we can guarantee that the first time Dijkstra's algorithm visits a certain node, the distance to this node is already the optimal one. To prove this is the case, just notice all edges reaching a certain node have the same cost. So essentially you only need to consider the first time Dijkstra's is able to reach any given vertex.

      The boring part: you'll need to use a data structure such as a range tree to query for all available (not yet visited) points in a rectangle.

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

        Did you solve the k problem ? i know its DP but idk how to handle the positions in a circle :(

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

        can you showme your code? I have that idea, but I got TLE, I use a quadtree. The complexity is N^2 * log^2(N), is fast for N=500, I think that my solution have a high constant value, I dont know.

        Sorry for my english.

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

          I linked to all of my codes for this regional in an earlier post, but as you missed it here is J. Make sure to code your own version! :)

          I have my doubts as to whether a quadtree can achieve log^2 n for all queries (I haven't really thought about it much, though). The log^4(n) BIT strategy I used has a pretty small constant, so it works pretty fast in practice, and it worked faster than the traditional range tree I had coded earlier.

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

            ffao Do you still have the solution to problem D somewhere? the links are broken :(

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn't understand sample cases for problem E, can someone explain?

How problem F can be solved?

Thanks.

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

    For each trip plan you choose, you'll always take the maximum amount OF kids, which is the GCD of the islands in the plan. Also remember that the problem doesn't ask for the maximum K, but for the amount of different K's

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me how the exercise C is solved?

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

    Lets focus on a numeric string and 1 base indexed.

    It's a dp problem, define f(N, S) how many positions up to N sums S, work with S mod 3.

    Lets define A as the sum of the digits up to N in mod 3.

    For each digit d in the string (d mod 3) 0 <  = d < 3 do.

    • Add d to A, keeping A mod 3.
    • If A is zero, this is already a substhreeng Add 1 to answer.
    • Add to the answer f(N-1,A)

    As an example, consider the following String "20144"

    1. d = 2, add d to A, now A is 2, add f(0, 2) = 0
    2. d = 0, add d to A, now A is 2, add f(1, 2) = 1
    3. d = 1, add d to A, now A is 0, add 1 + f(2, 0) = 1
    4. d = 4, add d to A, now A is 1, add f(3, 1) = 0
    5. d = 4, add d to A, now A is 2, add f(4, 2) = 2

    So the number of substhreengs is 4, {0, 201, 0144, 144}

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

      Thanks... And the problem G do you know?

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

        You had to go through points dwith at most 5 units away from each point. As the statement said it was always possible to divide the points in two, there'd be at most 4 points in a square with side of 10 units and centered in the point. Put an edge between point with distance smaller than 5. Now you have a bipartite graph and you just need to color it and pick the set with the least amount OF points at each connected component

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

          I have the same idea about the bipartite graph, but I didn't have idea about de four points... thanks caioaao

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

            That's because if you have more than 4 points in this square (not couting the center point), you wont be able to divide the stars into two groups according to the constraints

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

              given a point, how to find those points that are near on a efficient way?

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

                Keep them on a map, with the coordinates as the key. To check just loop through all 25 points inside the square

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

                  Sorry maybe I am missunderstanding your idea, why 25 points? I think that there are 80 in a 10 units side square centered at x,y. my code can you help me?

                  If you see anything wrong, please let me know :)

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

                  @pachon_1992

                  Your idea is correct, you just have a small implementation problem.

                  The way a map behaves in c++, if you do m[index] and the item with index doesn't exist, it will create it. Also, the map is stored in a (balanced) tree, so each insertion and lookup takes O(log n) (and mind you that the balancing constants can take quite a bit of time too).

                  So, where you are doing:

                  int mapped = m[point(xx,yy)];
                  if(mapped){
                      adj[i].push_back(mapped);
                      adj[mapped].push_back(i);
                  }
                  

                  You are inserting a new item every time you do m[point(xx, yy)] which is filling the map with a huge lot of points that don't need to be there.

                  You can use .count to do the lookup without inserting a new element:

                  if (m.count(point(xx,yy))) {
                      int mapped = m[point(xx,yy)];
                      adj[i].push_back(mapped);
                      adj[mapped].push_back(i);
                  }
                  

                  This will get rid of the TLE and give you AC (just remember to comment the "cout << endl;" on line 30 too, gave me a lot of WAs when testing your code until I noticed it haha :P).

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

                  Thank you very much bro, I didn't know it.

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

                There is a trick: You can divide all the points x,y by 5. So, you only have to check the points at distance 1 in the plane 2D. Good luck :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain problem E. Thanks in advance

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

    You can solve this problem using Dynamic Programming on the input graph with state(node, actual_gcd). For each new state you reach, just add the corresponding gcd at some set recording all the possible answers. The key idea for this implementation is to realize that the number of divisors of any number between 1 and 10^5 won't be big, and because of that, the number of possible actual_gcd's too.

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    To solve this problem you have to realize that the answer is: for every non-empty connected sub-graph of the input graph, take the GCD of the values of all nodes in the sub-graph and store it. That GCD is a possible k, the number of different k's is the answer of the problem. To make a working implementation of this idea, let's iterate over all different GCD's (not that many) and try to find a connected sub-graph such that the GCD of the values of their nodes is exactly the one we are considering. How to do that? Well, if we are considering GCD g, then all nodes whose values are not divisible by g can be discarded, the resulting sub-graph has only nodes whose values are divisible by g. Now, let's make a DFS on any node of this sub-graph keeping the current GCD of the values of the visited nodes: every time we visit a new node, the current GCD cannot increase and will always be greater or equal than g, so here a greedy approach works. Find the GCD of all connected components of the sub-graph (as explained before) and check if any of them is equal to g, if so then g is a possible k.

    The algorithm look like this:

    For every node v:
      For every divisor d of value_of(v):
         Add v to sub-graph_d
    
    def check(g):
      For every connected component c of sub-graph_g:
        x = GCD(c) // gcd of the values of the nodes of c
        if x == g:
          return True
      return False
    
    sol = 0
    For every possible GCD g:
      if check(g):
        sol++
    
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, as nobody has talked about problem B, i would like to know how i could solve it. I have been getting w.a after w.a, i am trying a O(B^2), the first cycle iterates the number of big swaps ill do (and therefore the number of little swaps ill do), and the second iterates over all the positions where a B should be, swapping the W against the furthest position of a B.

Seems to have logic, but i believe i am failing at logically simulating the swaps, can anyone help me ? This is my code: http://ideone.com/8ZTg3U

Now Problem G , i am curious on how to solve that one. Thanks!

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

    Sorry I don't like to read other's code :(, B can be solved in O(N).

    First of all let's define X as the number of black stones and Y the number of white stones in the first X positions.

    You have to put all black stones in the first X positions of the string.

    Start with the worst cost, which is Y * A, that comes from swap all Y white stones in the first X positions with the black stones that are not in the first X positions.

    Now take white stones, starting with the one that is near to the position X, and try to improve the cost by doing continuous swaps until the first black stone to the right, you don't have to simulate it, it's just (BlackPosition - WhitePosition) * (A - B), if the cost gets lower update the cost otherwise terminate the algorithm.

    To solve it in O(N) you can store the positions of the blacks or the whites stones or both, whatever works for you. :)

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

      i am following this approach , cause it seems right, but yet i still got w.a

      I am counting all the B's, then i am doing min_moves+=A for ever W on the range [0,Bnumber-1]

      Then i do a for (int i=Bnumber-1;i>=0;--i)

      if (there is a W) i will do int a= min_moves, a-=A, a+=(A-B) * (i-closestBidx)

      if (a>min_moves) break;

      else min_moves=a

      still does not work, i have tested a bunch of test cases and all of them work, am i missing something?

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

        I would need to check your code, but it's closestBidx - i, and if you do your maths you need to use long long

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

          ty, i was missing the long long, :) all my solutions got w.a cause of this hahaha thanks!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone put problem g code,get lot of wa and can not find which is wrong in my solution,i use an scc and color

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

    If you need a solution this is this is my solution.

    You don't need scc, as caioaao suggests here, you just need to generate a graph, each point is adjacent only to points with distance less than or equal to 5.

    Now for each connected component (not scc) color it (let's say 1 and 2) with a bfs, and pick the set with minimum size out of this two colors sets and add this size to your solution.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the H problem, since N is only 1000, I used the following approach:
1) I stored the distance for every pair of possible elements along with the corresponding elements. Distance between elements a and b means min(abs(a,b),24-abs(a,b)). I also stored the frequency(count) of every element.
2) Now sort these distances in non-decreasing order.
3) Now, since you have N/2 pairs, you need exactly N/2 elements from this array.
4) So, we will iterate over this distance array and keep taking the smallest distances until we add N/2 distance elements into the answer. We will only add distance to answer if the frequency of the constituent elements are greater than 0. After adding the distance to answer, we will decrease the frequency of the corresponding constituent elements.

But this approach is giving me Wrong Answer. Can someone please explain what is wrong in this approach?
Here is the implementation of this approach which gave me WA !! http://pastebin.com/S67kg97b

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

    I think the approach is incorrect, there might be some cases where use the minimum distance for a pair will increase the distance for others, I can't find an example right now.

    You have to use the property of circularity, sort all elements, to get the minimum cost, you have to pair each element with one of his neighbors in the sorted sequence, left or right.

    There are only two options,

    • Start from the first element and pair it with his right neighbor, advance two, do the same for the rest.
    • Start from the second element and pair it with his right neighbor, advance two, do the same for the rest, pair last and first too.

    Take the minimum of this two options.

    As an example let's take the following input

    1, 3, 4, 6

    If I am not wrong your algorithm will form the following pairs (1, 3)(1, 4)(1, 6)(3, 4)(3, 6)(4, 6)

    And greedily will take (3, 4) first, then as the only remaining option will be (1, 6) giving you 6 as answer, while the correct answer is 4, taking (1, 3) and (4, 6).

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

      Thanks for the explanation and specially the test case.

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

        You're welcome, I wouldn't believe myself without the test case :).

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

huehuehue