azizkhan's blog

TCO 2014 Round 2A
By azizkhan, 11 years ago, In English

TCO 2014 Algorithm Round 2A will be held today at 20:00 Moscow time . Those who previously advanced in Round 1 may compete in this round. First 50 places advance to Round 3. Good luck!

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

»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Arena doesn't work with Ubuntu again?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    It doesn't work for me too >_< Does anyone know how to fix it? It would be so disappointing to miss this round because of this.

    Edit: the Topcoder forum's URL is also broken. No idea how can we contact admin to ask..

    Edit2: The applet works now :)

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

      Here is the solution for Mac OS, maybe it also works for Ubuntu.

      → Reply
»
11 years ago, # |
  Vote: I like it +45 Vote: I do not like it

How to solve 250, 500, 1000?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    You should ask such questions only after the end of the Challenge Phase.

    250: let's sort our bricks in nonincreasing order and let's put them in such a pattern (number is an index of the sorter array):

     1  11   2   9
12   7  15   3
 6  16   8  13
10   5  14   4

    Any permutation of bricks 1-8, 9-10, 11-14, 15-16 will be fine.

    500: already explained in Russian in this post.

    UPD. I've changed the comment after eatmore has pointed to my error, but didn't mention it. Now everything is fine :).

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

      Actually only wrong solution is explained in russian post.

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

      Can't find correct solution of 500. Would you mind giving a link?

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Not exactly right, two smallest bricks must be near the center.

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

      Would you explain please, how have you found out such pattern for 250 problem ???

      I tried with,

      1 16 2 15
14 3 13 4
5 12 6 11
10 7 9 8

      I thought it would give me max result... :(

      But it hasn't worked... :(

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

        Well, you've guessed that 8 highest bricks must be put in a checkerboard pattern. I don't really understand, what can be unclear after you've made this assumption: you put a brick into an empty position and you can easily write a formula of how it affects the answer (each brick now affects the answer independently).

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          I put 8 highest bricks in checkerboard pattern, but I have not followed any order. I've just put them in descending order. But you haven't done it.

          In the first row, I've put 16 & 15

In the second row, I've put 14 & 13

In the third row, I've put 12 & 11

In the fourth row, I've put 10 & 9

          And when putting rest 8 bricks, I've put them in ascending order...

          But it didn't work... :(

          So it comes in my mind that, there should be specific ordering for putting them. So I asked you if you followed the order... :(

          *** Sorry for my bad english

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it -48 Vote: I do not like it

            You had a lot of time to read my comment again and again, again and again to finally notice that I've written: "Any permutation of bricks 1-8, 9-10, 11-14, 15-16 will be fine.".

            What does it mean? It means exactly the following: you must(!!!) put the bricks exactly as I've done this, but the groups that I've mentioned can be permuted in any way. You can transform this to an answer to your question.

            Competitive programming is an activity where participants must think heavily to achieve some result and I really hate people who don't do this and fill Codeforces with such garbage questions. As I've read my hint again, it's obvious for me that you didn't understand it not because of I've written it unclearly, but because of your blindness and lazyness.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it +27 Vote: I do not like it

              Why are you so angry? Not everyone is as smart as you. Mukit09 is asking about solution and trying to understand why it works — it does not looks like laziness. That green guy just can't get it.

              Mukit09, looking at your pattern, answer is S_total-4*(l[10]+l[15])-6*(l[9]+l[11]+l[14]+l[16])-8*(l[12]+l[13]). It should be clear that if you want to maximize answer, you should rearrange those bricks in such a way that you'll have S_total-4*(large_bricks)-6*(medium_bricks)-8*(small_bricks).

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                ← Rev. 3   Vote: I like it -7 Vote: I do not like it

                Thanks a lot I_love_Tanya_Romanova ... :)

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it +20 Vote: I do not like it

                Since I do participate in such discussions, I'm not smart, I'm an idiot. Really.

                But why do you repeat Xellos's explanation? Mukit09 is green, but it shouldn't prevent him from scrolling the page down and reading another comment.

                As I've told before, I'm not smart, but even for me it seems obvious that spoonfeeding won't help anybody to become smart either. IMHO, it will be much better if people such as Mukit09 will be angry with me, but this anger will make them grow hard and beat me and you and somebody much stronger than us sometimes.

                But seems that I don't have enough authority to make people change their oppinions...

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it +13 Vote: I do not like it

                  But seems that I don't have enough authority to make people change their oppinions...

                  It is quite usual in normal society. Normally nobody has "authority" to force people think on one way or another.

                  → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    250: The area is the sum of absolute values of height differences between all neighboring blocks. We can guess that it's best to use a chessboard coloring and put the larger 8 blocks on black squares and smaller ones on white squares. Then, we figure out that it's best to put the 2 smallest blocks in the 2 central white squares and blocks 7 and 8 to the corner white squares (to maximize the number of times larger h are added in abs(h-0)).

    500: Bruteforce, sort the wolves by a and first try splitting the sequence into the prefix that goes left, suffix that goes right and center. If the wolves are in correct order now, it's easy to compute the cost; otherwise, center must be empty and you can choose the prefix (in sorted order by b) that will be left on the left (lol), count the number of wolves which need to pass through the passage (lol again) once more, and then count the distances. Time's probably something around O(N4).

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

      Nice Observation of 250. I envy you to have such insight to solve problems as 250. Because after trying to use Dp to solve 250 the whole contest, I finally became green on TopCoder. TAT

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    250: "fair" solution would be submask dynamic: you just put elements one-by-one from the largest to the smallest and keep the mask of the occupied cells. If you put an element somewhere, you have to subtract its value * number of neighbouring cells in the mask (since it is smaller then values in these cells). However, everyone submitted the following greedy: put 8 smallest and 8 greatest values in chess-order, preferring central cells for the larger (smaller) numbers. Should be pretty straight-forward to prove, but I didn't do it during the contest (seemed pretty painful to strictly prove it).

    500: There are 2 cases: either there is an element which was not both at the left end and at the right end (this case is trivial), or was there is not. If it was not, each element either came to some end and stayed there, or came to some end, then to the other, and stayed there. You can sort items by their final position, and then iterate through possible left-right splits, and then determine who has to also go to the other end for the split.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    1000: DFS on states (tree edge, number of tokens in subtrees separated by that edge)

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    1000: Suppose we want to move the red tile from node a to node b. Let's freeze its movement in the middle of the edge (a, b). Note that at this moment both a and b are empty. Also, we know that there are k black tiles in the subtree of the node b and total - k in the subtree of a. Here the subtree of the node a is the connected component of a after removing the edge (a, b). Let's call three numbers (a, b, k) the state.

    There are O(N2) states in total, because we have O(N) edges and O(N) possible values of K. Now we need to define transitions between these states. Before we start our movement from a to b we need to rearrange black tiles in the subtree of b in some way. Let's iterate over the node c that will be our next destination (after we reach b). We can iterate over all possible values of k', which is the number of black tiles in the subtree of c with respect to the edge (b, c). Note, that we can easily find the bounds of k'. In this way we can find all the states (b, c, k') that are reachable from (a, b, k).

    Now we just need to do a bfs/dfs in this new graph, where the vertices correspond to our states. The complexity is O(N3).

    → Reply