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

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

Let's discuss the solutions of all the problems. I would like to know other peoples approaches for the problems. This time I am only able to solve Problem A. What are your views about the problems ?

Here are the problem statements.

Final Round on Sunday, November 6, 2016 13:00 CST

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

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

how did u solve A ?

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

    I didnt solve it through the contest because I had some troubles, but I submited now and got AC to both, small and large. Large run in 6sec, so I think is a good solution. Complexity is O((N+M)*N) I keep a dp[i][j] with size [4000][2000] where i is the position and j is how much 'A' voters I have until that position. Dp itself keeps the ways we can achieve that with the rules that statements says. So dp[i][j] = dp[i-1][j] * max(0, M — (k-1)), for the case that we want to add in ith position an 'B', and dp[i][j] += dp_solve[i-1][j-1] in case we want to add an 'A'. Finally you will print dp_solve[N+M][N] / factorial(N+M). In large that will overflow, so we can keep a clever division in each for loop, something like that-> dp[i][j] /= i, because we want dp[i][N] to be divided by i!, so dp[i-1][N] will be divided by (i-1)! so new dp[i][N] can be equal to (i-1)!*i, so you see that you can just divide by i in each loop.

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

    sanket407 Read the problem statement carefully and Just see the sample inputs. The ans will be (n-m)/(n+m). You can get this by writing all the permutations as explained in problem. Check this for more details : Bertrand's ballot theorem

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

A: Simple DP with state as (N, M) denoting number of people of first kind and second kind left. Transitions are easy, just check if second kind person votes now, then first person should be still winning.

B: I'm not sure, but I think I got AC on large by fluke, just submitted some random greedy solution. Any ideas on proof or your solution? Solution for small: DP with state (current Index, mask of row[currentIndex-1], mask of row[currentIndex-2]). Transitions are easy, check all possible masks for the current row which satisfy all conditions.

C: Again DP in O(N2 logN) per test case. State is (Current Index). From the current index, start iterating forward keeping an array of frequencies. At each position, check if we have the same frequency of characters as in any one of the strings using a map(which is computed previously).

D: Small: Brute force, try out all 210 combinations. No idea how to solve large. Anyone?

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

    D: DP[x][i] stores the minimum cost required for formation of length exactly x using some rubber bands upto i. Transitions are pretty straight forward. One can use segment tree or sparse table to speed up the same.

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

    please state the recurrences for A

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
      find(noOfPeopleVoted, noOfVotesforA) = P(A)*find(noOfPeopleVoted+1, noOfVotesforA+1) + P(B)*find(noOfPeopleVoted+1, noOfVotesforA)
      

      P(A) = Probability to select a person that votes for A from remaining voters

      Similarly for P(B). These could be find out from initial, n, m, noOfPeopleVoted, noOfVotesforA

      Answer is in find(0, 0)

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

    How did u bitmask on large dataset ? R,c<100

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

      Only for the small dataset. For large I used a greedy approach that I don't have a proof of.

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

        can you explain how to use greedy approach to solve the problem? I think the method is like this:

        xox xox xox ...
        xxo xxo xxo ...
        oxx oxx oxx ...
        xox xox xox ...
        xxo xxo xxo ...
        

        so I get the answer:

        1 2 2 3 4 4 5 6 6 7 8 8 9 10 10
        2 4 4 6 8 8 10 12 12 14 16 16 18 20 20
        2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
        3 6 8 11 14 16 19 22 24 27 30 32 35 38 40
        4 8 10 14 17 20 23 27 30 33 37 40 43 47 50
        4 8 12 16 20 24 28 32 36 40 44 48 52 56 60
        5 10 14 19 23 28 33 38 42 47 52 56 61 66 70
        6 12 16 22 27 32 38 43 48 53 59 64 69 75 80
        6 12 18 24 30 36 42 48 54 60 66 72 78 84 90
        7 14 20 27 33 40 47 53 60 67 74 80 87 94 100
        8 16 22 30 37 44 52 59 66 74 81 88 95 103 110
        8 16 24 32 40 48 56 64 72 80 88 96 104 112 120
        9 18 26 35 43 52 61 69 78 87 95 104 113 122 130
        10 20 28 38 47 56 66 75 84 94 103 112 122 131 140
        10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
        

        N = 15,M = 15

        the code like this :
        int getAns(int N,int M)
        {
            int ans;
            if(N < M) swap(N,M);
            if(M == 2 || N == 2)
            {
                swap(N,M);
                if(M % 3 == 1)
                    ans = ((M / 3) * 2 + 1) * N;
                else
                    ans = ((M + 1) / 3) * 2 * N;
            }
            else
            {
                ans = (N / 3) * 2  * M ;
                if(N % 3 != 0) ans += (N % 3) * ((M + 2) / 3) + (N % 3 &mdash; 1) * ((M + 1) / 3) +   (M / 3);
            }
        
            return ans;
        }
        
        

        but it's wrong!!! I don't know how to solve it. thanks a lot

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

          I had a shitty greedy, this is what I did:

          Every time if the previous column in the same row is blank, and the same column in above 2 rows both are not filled, I fill this current cell.

          If the previous column is filled:

          1) If the above top 2 rows of current column is filled, do nothing.

          2) Else if the above row is not filled, fill this cell.

          3) Now if the above cell is filled, we check the previous column. If the row above in previous column is also filled, we don't fill the current cell(if it is the last row, we fill it), else we fill it.

          When I did this, it didn't pass the small dataset.

          Then I did the same thing for both, the given matrix, and transpose of the matrix because answer won't change since we have started filling in another way.

          Now I took max of both, and it passed the large data set too.

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

            thank you for you reply, but I have some doubts. I default the cells above the first row are all blank.

            Every time if the previous column in the same row is blank, and the same column in above 2 rows both are not filled, I fill this current cell.

            and

            2) Else if the above row is not filled, fill this cell.

            so the first row will be filled like this:

            xxxxxxxxxx
            

            Maybe I have some misunderstanding, very thanks

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

              I'm sorry for the confusion, you also have to check at each time that there isn't any consecutive 3 cells. So first row is filled like this -xxoxxoxxoxxo...

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

    How did you create a map of character frequencies for the dictionary words in C?

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

A: well-known problem, answer is (n-m)/(n+m).

B: I don't know the right way but I made a few observations and with a little help from oeis, I guessed the answer. Answer for (r,c) is same as (c,r). Assume r<=c. If r=1 or r=2, answer is r*(c-floor(c/3)). If r is a multiple of 3, answer is (2*r/3)*c, else the answer is r*c-floor((r*c)/3).

C: DP. Dp[i] is the number of ways to form the string till i. To find this, select some j<i and consider the string between these two indices. Check for how many words in the vocabulary, this string is an anagram of. Call that number X, then dp[i]=dp[i]+x*dp[j-1].

D: Did the small dataset only by checking all the subsets.

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

    How to prove answer for A is (n-m)/(n+m) ?

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

    Could u please tell me how did u get this formula about r and c in problem B. Thanks a lot!

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

      When r = 1:

      xxo xxo xxo ...

      When r = 2:

      xxo xxo xxo ...

      xxo xxo xxo ...

      When r > 3 and r % 3 == 0 or 1:

      Consider the following method:

      xxo xxo xxo ...

      oxx oxx oxx ...

      xox xox xox ...

      xxo xxo xxo ...

      When r > 3 and r % 3 == 2:

      xox xox xox ...

      xxo xxo xxo ...

      oxx oxx oxx ...

      xox xox xox ...

      xxo xxo xxo ...

      Here we permute the lines to assure that the leading columns filled with 'x' as many as possible.

      Then you can get the above formula.To prove the correctness,

      For every continous 3 grids we need to fill at least 1 'o',

      while the method we suggested can do exactly 1 'o' every 3 grids.

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

        Thank u very much! I have got your idea,but one question here is.

        If i keep every 3 seats must have one 'o' in a line,and permute the 'o's position in different lines, why when r > 3 and r % 3 == 2 is:

        xox xox xox ...

        xxo xxo xxo ...

        oxx oxx oxx ...

        xox xox xox ...

        xxo xxo xxo ...

        Is it the same with?:

        xxo xxo xxo ...

        oxx oxx oxx ...

        xox xox xox ...

        xxo xxo xxo ...

        oxx oxx oxx ...

        which means does the first line can be xxo xxo ... form? they all have 15 'o'

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

          Take your same examples and take C = 10 (instead of 9 above) Then couunt the no. of X in both cases U will get the difference

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

          "Here we permute the lines to ensure that the leading columns filled with as many 'x' as possible."

          When r % 3 == 2, we only consider the last 2 lines. When the column number increase, we want to keep as many 'x's as possible.

          (i)

          xxo

          oxx

          when c = 1, number of 'x' is 1. when c = 2, 'x' is 3, c = 3, 'x' is 4.

          (ii)

          xox

          xxo

          when c = 1, number of 'x' is 2. when c = 2, 'x' is 3, c = 3, 'x' is 4.

          You can see when c = 1, the second one is better.

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

Can somebody tell me of how much order pass in Apac or Codejam. In Codeforces solution of 10^8 pass. However, I am not sure about how much complexity Apac allows. Please guide me in this as I thought my A would not pass large test cases but however it did.

So please tell me is it 10^8 computations in Apac too.

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

    There's nothing like that in code jam or apac as you have to post the output file rather than code. Your code will not be run by server like in CF. So basically it comes down to generating the output file on your pc using your code within the time limit ( 4 minutes from time of downloading input file to time of submitting i guess )

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

      No, they take the source code so obviously they check the code on their cases too. Else 4 minutes is too much I guess. It may happen that many TLE solution may pass.

      Plz someone help over here.

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

        They check any similar codes to avoid copying. TL is dependent on your computer and 4min is very lenient but still enough to kill most suboptimal solutions.

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

          Thanks a lot. And so Facebook Hacker Cup follows same procedure( of just checking output files ) or do they have limit on computation. Can you please tell this too?

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

        source code is just for plaigarism check i or some other reason They dont run it themselves https://code.google.com/codejam/apactest/terms.html check rules 3-4-5-6 under 4.PROBLEMS section

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

Is there any other way to solve B-large , apart from formula ?

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

Problem D. large test case in detail anybody please

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

    Let's dp[n][L] = the least money to create a rope of exactly size L

    then dp[n][L] = min(dp[n — 1][L — b[n]] -> dp[n — 1][L — a[n]] you can find the answer by using dequeue,

    Code