Блог пользователя Medo.

Автор Medo., история, 7 лет назад, По-английски

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).

  • Проголосовать: нравится
  • +93
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Reminder: Registration closes in 45 minutes.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2 1000 — point problem?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Can you explain your solution for these cases?

            • pairOr = {3, 3} and pairSum = {4, 6}
            • pairOr = {3, 3} and pairSum = {6, 4}
            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you please elaborate on it ?

»
7 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится
      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
      
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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.

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve Div1 500?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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] "??-"};

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

The problems were really good.

Although I got 0 point, the round was interesting.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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