Medo.'s blog

Topcoder SRM 724
By Medo., history, 7 years ago, In English

Starts in few hours.

Date and Time : https://www.timeanddate.com/worldclock/fixedtime.html?msg=Topcoder%20SRM%20724&iso=20171128T1600&ah=2&am=0

Redoing this blog as it appears people liked it last time. (If there is someone from TC that prefers to post these kind of blogs, I will happily delete this).

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

Comments Comments (31)
| Write comment?
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Reminder: Registration closes in 45 minutes.

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

Why possibility to select reward has disappeared while registration still going?

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

    Forget, it is present on registration page on arena.

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

I really like today's problems, is TC back?

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

    Problems were good but not many participants even though SRMs at this time slot used to be most popular

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

How to solve Div2 1000 — point problem?

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

The contest was really tough. Div.1 250 pts solution?

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

    a + b = (a|b) + (a&b)

    Now that you have pairOr and pairAnd, note that you can check solution for each bit individually as they are independent. Now, do a dp[n][2] for each bit where dp[i][j] is whether there exists a prefix of length i ending at j. Check if dp[n][0] or dp[n][1] is true for each bit.

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

      Another one solution: we can simply say a = (a|b) and find b = (a + b) - (a|b). Then if our a|b = a|b from data then ok else no

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

        Wut? It works for n=1, but how does it work for bigger n's?

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

          If a + b = (a|b)+(a&b) then b = (a + b)-(a|b) = (a&b) and a = (a|b). If (a&b)|(a|b) = (a|b) so we could use these a and b.

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

            Can you explain your solution for these cases?

            • pairOr = {3, 3} and pairSum = {4, 6}
            • pairOr = {3, 3} and pairSum = {6, 4}
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              What means pairOr = {3, 3} ? Is it a|b = 3|3 or what?

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

                pairOr and pairSum are bitwise OR and sum of adjacent numbers in the required sequence. (The arguments of function in original problem)

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

        Can you please elaborate on it ?

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

When browsing codes to easy I wonder if people realize that (a&b) + (a|b) = a + b ;p

Btw, does anyone have a promising idea to hard? I got it passed using random but I am not satisfied with such approach. I thought about some kind of standard idea of determining lowest and biggest possible variance and if our goal is within allowed interval then making changes from solution with lowest variance to one with biggest and arguing that somewhere along this road we will encounter good answer, but I was not able to think of solution based on that.

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

    But why (a&b) + (a|b) = a + b ?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it 
      To understand something just try to write some examples on paper

 1011101 a
 1010110 b

 1010100 &
 1011111 |
 
 ^ sum of these will give a + b
 consider the i-th bit
 if a and b have 0 0 then & has 0 and | has 0
 if a and b have 0 1 then & has 0 and | has 1
 if a and b have 1 0 then & has 0 and | has 1
 if a and b have 1 1 then & has 1 and | has 1
 thus, same result
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And what about the carry value of (A+B)? For example, A == 10, B == 11, the result is longer that 2 digits, because of carry. How can you prove that (A&B) + (A|B) == A+B in that case, when some carry exists in the sum process?

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

      a + b = Σ (ai + bi)2i
      a|b = Σ max(ai, bi)2i
      a&b = Σ min(ai, bi)2i

      Here ai and bi are the ith bits.

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

        And what about the carry value of (A+B)? For example, A == 10, B == 11, the result is longer that 2 digits, because of carry. How can you prove that (A&B) + (A|B) == A+B in that case, when some carry exists in the sum process?

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

          10 + 11 = 0 + 1 + 10 + 10 = min(0, 1) + max(0, 1) + min(1, 1) * 10 + max(1, 1) * 10 = 0 + 1 + 10 + 10 = 101

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

          There'll be a carry in the addition of corresponding max and min as well. The point is I have written the binary number in decimal form, so equality in base 10 implies equality in base 2.

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

How to solve Div1 500?

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

    First, one observation is that it is enough to do at most one of the moves {"left", "right"}, and at most one of the moves {"up", "down"}. There is no point to do both of the moves in one of the sets, so any reachable board would be reachable in at most two steps.

    Let's say "left" is true if there exists a block that has a free cell on its left and false otherwise. (similarly, define "right', "up", and "down"). Intuitively, these are the moves which we shouldn't use, since we can't use these and get to our final configuration.

    Then, we have the following cases:

    1) If all of left, right, down, and up are true, then the answer is 1 (i.e. no moves are possible).

    2) Let's say that both left/right are true (similarly for up/down). Then, we can't ever do left/right moves, so we can treat each column independently. Since one of up/down must be false (otherwise, we would be in case 1), then, we can just place the blocks anywhere in the column, as long as the number of such blocks matches. The number of ways to do this is just the binomial coefficient (n choose number of blocks in column). We take the product over all columns.

    3) Now, without loss of generality, let's say left is false and up is false. Then, that means all blocks are in the upleft corner. For example, it may look like a shape like this:

    ####.
###..
###..
##...
.....

    There are two options: We either can do the moves "left" then "up" to get the blocks in the correct place, or we can do the moves "up" then "left".

    For, "left", then "up", we can arrange the rows in an arbitrary order, then arrange the blocks within each row independently. The number of ways to arrange the rows is the multinomial coefficent (n choose a_0, a_1, ..., a_m), where a_i is the number of rows with exactly i blocks. The number of ways to arrange blocks within each row can be computed similarly to case (2).

    Similary, we can do the same thing for "up" then "left" (using columns instead of rows).

    However, we double counted the boards that can be solved with both types of moves. Luckily, that is just the number of ways to rearrange rows multiplied by the ways to rearrange columns. We can also use multinomial coefficients here in this case.

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

Is it me, or Web Arena has some issues with 64-bit integers in input in 250? For me, the 5th (1-based) sample is ["261208776456074180", ...], ["333333333333333300", ...] when I run it in the batch test panel, and produces other answer than expected. It was extremely confusing, but I decided to submit the solution anyway, and it passed.

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

Btw, don't know how it was for others, but for me it was pretty confusing that when coding hard my compiler was replacing every occurence of "??-" by "~" and I was getting this "~" on input :|. oldG=(-??, ?-?, ~, )

UnfinishedTournament.cpp:253:3: warning: trigraph ??- converted to ~ [-Wtrigraphs] "??-"};

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

The problems were really good.

Although I got 0 point, the round was interesting.

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

I wonder if there is a solution using deterministic algorithm to solve div 1 Hard?

→ Reply