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

Автор pakhandi, 5 месяцев назад, По-английски,

Registration for the Google Code Jam 2017 is now open

Past rounds can be found here

The complete schedule can be found here

Update —: Round 2 starts in 2hrs-7mins. Top 500 participants will advance to Round-3.

Gl & Hf !!

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

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

How to solve D of qualification round with maximum bipartite matching? The best I could think was to place maximum bishops and rooks on nxn chess board.

edit-solved.

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

    You can divide the problem into one problem for rows/columns (x, o) and one for diagonals (+, o), the first can be solved greedily, and for the second one you do a maximum matching between the diagonals that haven't been used (as long as the edge represents a valid position on the grid).

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

      Can you prove why any placing is optimal? And how can we decide which ones to upgrade?

      I was able to reduce the problem to what you said, and I think it's just about placing maximum bishops(+,o) and rooks(x,o) but why is it correct?

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

        Since you're using the maximum matching it has to be optimal. Upgrading happens when you modify one occupied cell in one of the two subproblems.

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

          I am still unsure why greedy + MBM gives optimal answer.

          I started to think that both have to placed with bipartite matching simultaneously. As, depending on how you place your 'x' you may not be able to place maximum number of '+'. eg : when n = 4, if we place 'x' in (1,2), (2,1), (3,4) and (4,3) we won't be able to place the maximum number of '+' with such an arrangement. The maximum is 6(+) + 3(x) = 9 models, but if the above configuration is followed, we only get 4(x) + 4(+) = 8 models.

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

how many points needed to go to next round "Online Round 1: Sub-Round A" ?

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

I solved A but can any one give a proof of that solution ( iterate the string and if the current character == '-' flip the next k pancakes )?

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

    let us say at i-th position we have a '-' symbol and this is the left-most '-' symbol. Now, since you have to change all the '-' symbols to '+' symbols, you have to use at least one operation starting from i-th position.
    I hope it gives you an idea about the proof.

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

      I'm sorry but I didn't get it, also I'm interested with proof of optimality ( minimum number of operations ).

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

        If i-th position is the left-most position with '-' symbol, then the claim is that it would be optimal to perform an operation at i-th position because there is no other way to convert the i-th symbol.
        In case you perform an operation at a position j before i such that j + k <= i then, by our assumption, we would be creating new '-' symbols before i-th position, hence increasing the number of operations.

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

        to understand this, first you have to notice that the flips are commutative. by noticing it, you also understand that two flips on the same range are the same as not doing any flip. so, starting from left, there's only one way to turn the first '-' into '+'. this is true for the rest of the pancakes: if there's a '-' on the pancake with index i, there'd be two ways of turning it into a '+': by doing a flip starting at i or by doing a flip starting before i. you know that by flipping something before i you'd be either canceling a flip you already did (thus turning a '+' into '-') or adding a flip you didn't do (also turning some '+' into '-'). so the only possible way of turning the current pancake is to make a flip starting at it.

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

How to solve C-large anyone ??

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

    Just take the max element (say X) , if its frequency is >= K then this is the answer else add its frequency to X / 2 and (X-1) / 2.

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

    write a binary tree with the generated possibilities from N like so: root is N. left (let's call it L(n)) is the biggest subsequence generated and right (R(n)) is the smallest ( on both children for odd N or on the left and on the right for even N). Now start placing the people: you'll notice that, for a given node, the first person will stay on the node, the second will go to the left subtree, the third will go to the right, fourth will go left again, fifth will go right, and so on. Now it's easy to write an algorithm: call the answer f(n, k). if k = 1, you're on the answer node already, so just print L(n) and R(n). If k - 1 is odd, then the last guy will go to the left subtree, so the answer will be f(L(n), (k - 1) / 2 + 1). if it's odd, the last person will go to the right subtree, so the answer will be f(R(n), (k - 1) / 2).

    it would look like this:

    long long R(long long n) {return (n - 1) / 2;}
    long long L(long long n) {return (n - 1) / 2 + !!(n % 2 == 0);}
    
    void f(long long n, long long k) {
      if(k == 1) cout << L(n) << ' ' << R(n) << '\n';
      else {
        if((k - 1) % 2 == 0) f(L(n), (k - 1) / 2 + 1);
        else f(R(n), (k - 1) / 2);
      }
    }
    
»
4 месяца назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

After qualification round, Square869120Contest #4 will be held at Atcoder.
Let's participate and enjoy!!!!!
https://s8pc-4.contest.atcoder.jp/

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

Can anyone explain me what does it mean that Round 1 is divided into 3 Sub-Rounds? Does it mean that we have to advance in any of these like in TCO or we have to pass through all of them?

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

Problem D was very nice! Although I didn't solve it in contest, I thought the author's solution was very elegant.

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

Can anyone Explain the greedy method used in the editorial in a more simpler way ?And if anyone solved it bipartite matching feel free to explain your method also.Thanks in advance .

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

The analysis for B is unnecessarily complicated. We can just greedily construct the optimal number by going from the left to the right. (Additionally, to avoid all special cases just prefix both the input and your number with a 0.)

Example:

   input number: 01568435466
we already have: 0156

What is the largest next digit we can use? If we use digit d, the smallest possible final number will have d on all remaining places. If this number is small enough, there are some valid tidy numbers with the next digit d, and if this number is too large, there are no valid tidy numbers in which the next digit is d. And that's all.

   input number: 01568435466
we already have: 0156
   we can use 7: 01567777777 is <= input
we cannot use 8: 01568888888 is > input
thus, next step: 01567

My submitted code:

T = int(input())
for t in range(1,T+1):
    V, A = [0]+[int(_) for _ in input()], [0]
    while len(A) < len(V): A.append(max(d for d in range(A[-1],10) if A+[d]*(len(V)-len(A)) <= V))
    print('Case #{}: {}'.format(t,int(''.join(str(_) for _ in A[1:]))))
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +140 Проголосовать: не нравится

    Another simple greedy solution is to notice, that a tidy number can be represented as a sum of at most 9 numbers consisting only of 1s. For example, 133347 = 111111 + 11111 + 11111 + 11 + 1 + 1 + 1. The solution is then to add maximum such number so that the sum doesn't exceed N and the count doesn't exceed 9.

    long long answer = 0;
    int count = 0;
    for (long long ones = 111111111111111111LL; ones > 0; ones /= 10) {
        while (count < 9 && answer + ones <= N) {
            ++count;
            answer += ones;
        }
    }
    
    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 4   Проголосовать: нравится +28 Проголосовать: не нравится

      OMG. In compare, I have a mega overkill: I wrote dp[lengthOfNumber][startingDigit] to find maximum number X, such that X ≤ N and f(X) = f(N), where f(num) =  number of tidy numbers less than or equal to num.

      Code: https://pastebin.com/Pw1c4rXM

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

      I think I have an even simpler solution:

      Reading the number n as a string s, for an index i, 0 ≤ i < s.size() - 1, if s[i] > s[i + 1] then we decrement s[i] and for all j, i + 1 ≤ j < s.size(), s[j] = 9. We then increment i. Since there may be cases like 554 we run the algorithm log(n) times (i.e. cases in which we have a violation of the tidy number constraint that was generated by the algorithm before index i).

      Total running time is log(n)2.

      string s;
      cin >> s;
      for (int t = 0; t < 18; t++) {
          int ix = 0;
          while (ix < (int) s.size() - 1) {
              if (s[ix] > s[ix + 1]) {
                  s[ix]--;
                  for (int i = ix + 1; i < (int) s.size(); i++) {
                      s[i] = '9';
                  }
              }
              ix++;
          }
      }
      

      Afterwards just print s without the leading zeroes.

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

        Without dealing with any leading 0's. Printf res:

        I thought that this is the same approach as above, but I was wrong. It is O(lg N). Remember the smallest digit you constructed so far. If you have something bigger, then decrement it by 1, set all 9's at the end and set that new smallest value to new decremented digit.

                LL N;
                scanf( "%lld", &N );
                
                LL mn = 1;
                LL prev = 9;
                LL res = N;
        
                while (N)
                {
                    if (N % 10 > prev)
                    {
                        // obniz o 1 pozycje i z tylu same 9 daj
                        N--;
                        res = N*mn + mn - 1;
                        prev = N % 10;
                    }
                    else
                        prev = N % 10;
        
                    mn *= 10;
                    N /= 10;
                }
        
        
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Google Code Jam Editorials consider all possible (and impossible) solutions. To me, they are great for increasing knowledge. :)

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

Just out of curiosity

Would you say problem D was comparable to a div2 D level problem, or div2 E in terms of difficulty?

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

    I guess it was a DIV 2E, but then again i'm a noob.

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

    I'd say it is at least div2 E or a bit higher if you consider that div2 E is getting easier and easier (maybe that's just me).

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

      It was a very beautiful problem, especially because it reminded me of a sport I love :)

      I didn't think it would be considered that difficult as close to 1000 people solved it in 27 hrs, but the logic was indeed very good behind the problem.

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

      Which was especially noticeable in the last 408 div2 round.

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

        I hope you're being sarcastic... XD

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

          I'd see it as not sarcastic but last round simply showed that the other div 2 rounds were way easier than what they could be. Also, looks like tons of people misunderstood C's statement, I did that too when looking at the contest later hahaha.

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

            Oh, I kind of misunderstood you comment. I thought you were saying last round's problem E was easy, which is definitely isn't. BTW, I also misunderstood C's statement XD

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

Test cases for B-small were weak. I had an AC solution which actually failed in cases such as 331.

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

For problem — C (large), I got the solution like — write the binary representation of k, then we will compute n for every bit (from right), except the left most bit. If the bit is '0', we get n = n/2, if the bit is '1', we get n = (n-1)/2. After computing for every bit, the answer will be — max(a, b) , min(a, b) where a & b is computed in this way : if(n%2 == 0) a = n/2, b = n/2 — 1; else a = (n-1)/2, b = (n-1)/2

The time complexity of this approach is log(k). But I can't prove why it is correct!!

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

How many people from online round 1 would qualify to round 2, I can't seems to find info from their site? From what I remembered, it is top 1000 of each round, but is it still the same?

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

    Yes, it's still the same (top 1000 in each round 1 subrounds, 3000 total).

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

      thanks! any source for that info?

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

        https://code.google.com/codejam/terms

        "1. You will advance to Code Jam Round 2 if you are one of the highest-ranked 1000 contestants from one of the sub-rounds in Code Jam Round 1. You will be notified by email after the end of each sub-round if you are one of the 3000 contestants advancing to Code Jam Round 2."

»
3 месяца назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

anybody here?

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

Logic for B & C in round 1A please?

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

    I tried to do maximum bipartite matching for B small but incorrect. Probably missed some corner case. I think the large is DP.

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

      I solved B small/large with maximum bipartite matching. If I had to guess it was probably something to do with the range that you can get from each package.

      Edit: forget that, the problem is harder than I thought.

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

    I got AC B-large with greedy. Just sort each row in Q and take earliest match possible.

    C-small I could get AC with BFS, obv. doesn't work for large :D

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

I submitted a max flow solution to B, during contest it passed the small so i submitted the large. The large failed after the contest so I was curious to know what the problem was, I tried submitting the large again in the practice with the same exact code and got a correct verdict! Is it just the test cases are weak for the practice or what

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

    Are there any corner cases in B? I also used maxflow but WA.

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

      well I don't know, actually by comparing with other solutions, my code failed in only a single case out of the 100 and it's this one http://ideone.com/WNzI0X

      My code outputs 4 while the answer should be 3. It's too hard to debug though lol

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

      Keep in mind that a package may be suitable for kits of different sizes. What do you return for this? 4 1 1 1 1 1 100 110 120 130

      I used a simple greedy approach — first try to match the packages with minimum size for each. If that does work, take all and increase answer by one. Otherwise, discard the package with the smallest Qij / Ri and try again, until there are no more packages left. Works in O(N2 * P).

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

        Yes I know, actually I build a flow network of N+2 layers, first layer is source and last is sink. Each layer represents an ingredient and it has P nodes, I add an edge between a node from a layer and the layer next to it if there is at least one common kit size they both can fit in. Basically for each package, the valid kit sizes is a range so you can find if there is a common one or not by a simple range intersection

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

          and my code returns 1 for your input

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

            Yet the correct answer is 0. If the kit is of size >111, you cannot use the first package. If it is of size <119, you can't use the last. Hence, the is no valid kit size, even though the ranges of consecutive ingredients overlap.

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

            It should return 0. The problem is that you need overlapping ranges to choose the packages. For example, (1 — 2), (2 — 3), (3 — 4) these are the ranges of 3 packages and you can't choose them but there will be flow if you simply connect them from one layer to the other.

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

          Sometimes it's better not to know maxflow algorithm at all. You could have thought a bit more and come up with very simple greedy algorithm.

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

            I tried max flow first. Because I couldn't find appropriate network, I wrote the simplest greedy instead.

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

        Can you, please, explain why this greedy strategy will not work when we have arbitrary ranges (according to the official editorial)?

        Especially, I don't see for now why the condition: "for 2 intersecting ranges having at least 1 common point" helps to prove that greedy approach works?

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится -30 Проголосовать: не нравится

Looks like tests for A are weak. For test:

1
3 3
J??
JH?
??H

some accepted solutions (firstly I tried tourist's one) give this result:

JJJ
JHH
HHH

Or I misunderstood statement and this is valid construction?

»
3 месяца назад, # |
Rev. 3   Проголосовать: нравится +23 Проголосовать: не нравится

Very weak test cases for B, I got AC large using a wrong max flow solution that allows to use a package multiple times.

My code gives 2 instead of 1 for this testcase:

1
3 2
10 10 10
10 10
10 1
10 10
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C-large?

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

Anyone else thinks that the problem statement is too long?

For A, I missed no initial appears more than once on the cake. and couldn't solve the problem.

And for B, I missed (Of course, each package can be used in at most one kit.) and only found out after an hour...

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

I hate problem B xD

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

    Same here :P Though C helped me get into top 1000 :D :D

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

      Didn't even read Problem C :S

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

        Even i never open harder problems before even trying easier ones. ! But this time the submited problems count at begining compelled me to try C first !

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

          Can you tell us how to solve C? I can recongise it as DP shortest path but can't handle how to solve the problem with choosing the horse.

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

            for small : just linear dp for each horse i = 1..N for each city j = i+1 to N if j is within limit of horse i through path i..i+1 i+2..j time[j] = min(time[j],time[i]+dist(i..i+1..i+2...j) /spd[i].

            ans = time[n-1];

            for large: for each horse do dijikstras to find min time in which it can reach each city reachable time[i][j] = time for horse [i] to reach city[j] in other words one path from i to j of cost time[i][j]

            then do floyd warshall shortest path for each pair i,j to get final cost array[n][n]

            ans will be in this array

            check my solution in GCJ page : username — sanket407

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

            Just don't choose the horse, always use the horse at the current DP, when you update from a town just update all towns within range, not just the ones connected by edges.

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

    Anyone here have a nice(short) solution to problem B? :)

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

    GCJ people are so good at super-tricky problems. I can't believe very high success rate (more than 30%!).

    For me it looked completely hopeless without stress-testing.

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

      What is tricky about it? You just have to find a bunch of test cases. Frankly I don't see the purpose of such problems. It's not "good at super-tricky problems" it's "annoying problems".

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

How is round 1B problem B meant to be solved? I checked my code over and over even with triangle inequality and I still couldn't solve the small case. I have no clue what's wrong!

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    Did you cover a case that the last horse cant be the same as the first one?

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

    For subtask with O = G = V = 0:

    Assume a >= b >= c the number of occurrences. (Assuming c >= 1, other case is trivial)

    Place a's first. You need (b+c >= a) to seperate all a's. If it is not so then its impossible.

    Place b's after every a and then c until finished.

    Incase you have some extra c's remaining: Let extra = (b+c) — a. Place each of this after every ab: aba -> abca...

    So it goes like abc-abc-abc-ab-ab-ab-ac

    Code

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

How to small B-large ?? B-small could be done by assigning alternately colors in foll, order largest count — then mid count — smallest count

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

    Can I see your code? I did the same thing but it kept saying i had WA.

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

      check my code in google code jam submissions itself! Same username there as handle here : sanket407

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

    If you don't mind, can you please tell what you did when all of them are equal? (As in the first sample test case)

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

    If you know how to solve B-small, that should extend to B-large.

    Notice for the color orange, it can only be adjacent to blues. Suppose there are x blues and y oranges. Of course if we have y > x, then it's impossible, otherwise if we have y=x, it's only possible if y+x = n. After handling this, we can reduce it to a problem where there are x-y blues and 0 oranges. Then, you solve the same case as small, and then replace any single arbitrary occurrence of "B" with "B" + y * "OB"

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

      Honestly, if this was described as part of the problem, I still wouldn't be able to solve it.

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

      During the contest I thought it can make a difference if you join all BOs inti one BOBOBOBOBOB or split into BOB,BOB,BOB, ... Had to bruteforce the numbers of BOBs, RGRs, YVYs. Got AC with that (the numbers sum to N/3 so the max number of combinations could be 111^3).

      Now I see that the amount does not matter, thanks

      PS: and failed C-large, which I thought is simple >_<

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

    Here is an opposite take on the problem, which first solves hard and easy case follows naturally:

    Consider a graph where each of 6 colors is a node. You know the number of edges between orange and blue, and two other pairs, because one should surround the other. You know that in-degree and out-degree of each node should be equal to the total number of unicorns of that color. Loop through a number of edges between, say, R and G, and then the in-degree and out-degree of every other node follows naturally from that. Now you just check if that graph has an Eyler cycle, that is your answer.

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

      So the selection is n^2 and euler cycle takes O(E) and here E ~ N, so O(T * n^3). Isn't it TLE?

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

        No, selection is actually O(N) — you backtrack through the out-degree of one node and the remaining in- and out-degrees follow. Then you need to check whether the obtained graph has an Eyler cycle, which can be done in O(1). Then you output that cycle in O(E) = O(N).

        Actually, I computed the cycle every time and then checked that it had length N, and if so, printed the answer, so the total complexity was O(TN2), that passed.

        Here is the solution: https://pastebin.com/hfxVkTyZ

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

          I had something similar.

          Can't you just check the in/out degree of each vertex in O(1) to check if an Euler cycle exists? This leads to an O(N) algorithm, I think.

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

            That is what I said in the first paragraph exactly.

            The only subtle moment is that you need to also check that the graph is connected — ex. for test 12 2 2 2 2 2 2 you get in your graph 3 connected components, in each of which in- and out-degrees are equal.

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

              Good point. I was just checking that it was possible, not claiming you didn't already say that. I figured you could simply do this in O(1) by doing a DFS through a graph with collapsed edges.

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

          This is so far the best solution for this deadly problem.

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

Either take round1-C in 4am, or say bye-bye to GCJ :(

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

Any ideas why A-large could fail?)

UPD:
I made wrong assumption:
If we sort horses by start position we can ignore all horses starting from first horse that ride faster than previous one.

It passed small input, it's very sad((

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

    You just need to choose the slowest horse and get the velocity for that time from 0 to D should solve the problem.

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

    MAXN error? I had issue with A large because in the beginning it said MAXN = 100 but it was really 1000. (or maybe I just read it wrong the first time)

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

    same with me , was in Top 1000 with 78 points lost top 1000 just because of A-large.

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

1113 Solved C Large. 730 Solved B Large.

This is bad for people who didn't even read C xD xD

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

Kudos for cubelover alex9801 who drunk lot of beers but still passed R1B safely

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

By the way these statements are horrible...

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

    Always this hate, I can't understand it..

    It's a nice variation to shorter statements. I see that statements like these in weekly contests might get annoying, but GCJ is once a year.

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

      You are right that we should appreciate long statements with a nice story behind it but in this exact situation somehow it was really difficult to have fun. (At least for me)

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

In the last Google Code Jam 2016, I finished 1557 in round 1B. Since then, I set the goal to advance to round 2 in Code Jam 2017 (i.e. be in top 1000).

All year, I trained to solve problems almost everyday. I kept journal of how many hours I spent on training per day, per week, per month. According to my journal since May 2016, I spent about 500 hours (and those are only hours when I worked at home in total silence).

So I thought that those efforts are enough to move from 1557 place (2016) to top 1000 (this year).

And here are results of all my efforts during whole year:

Round 1B 2017 — 6617 place!!!

I.e. I became much, much, much worse at competitive programming as a result of ~500 hours of training. It's fu....g unbelievable!!!!!!

Apparently, I have no talent whatsoever and probably I should quit...

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

    dislike my comment if u quit competitive programming after this code jam (Y)

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

    Probably! You should only do it if it's fun!

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

      Will you enjoy losing chess all the time to everybody including those who trained 10 times less than you?

      I won't believe you will enjoy losing game all the time.

      I personally enjoy very much to have an insight and find a clever solution, see my submissions in green light with magic word Accepted. It's awesome feeling. Every time, I solve hard problem (which is rare), I'm so glad and I continue starring at my code for minutes thinking how beautiful my solution.

      But if you spent hours, hours, hours, hours and hours in training to only see:

      WRONG! WRONG! WRONG! TIME OUT! WRONG! YOU WRONG! WRONG! TIME OUT! YOU WRONG AGAIN!

      Then you can't enjoy. You can't enjoy this disaster!

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

        I wouldn't play chess in competitions if I felt I wasn't good enough and hate to lose. But I would still practice playing chess because it's a fun way to spend some time and maybe some day I will be able to enter a chess tournament.

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

        You are right! Life is unfair. But if I can share one lesson from contests, it's that you can't expect to "deserve" results just because you've worked hard. That's not how this works.

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

        Try not to take the competitive part very much serious. Competitive programming is just a thing where competitors of all levels may occasionally compete together. Just imagine if you are placed to compete with world top chess players. With dozens of them. No much point in that, right? The difference is that the CP allows this situation to happen.

        Honestly, I never liked the competitive part itself. I like to solve problems, especially when I learn something by solving them. From this point, competitions don't provide me any motivation reasons, but they do provide modern problems.

        So try just to forget about the competition part. No matter what rating do you have, no matter how are you placed in a contest. The best way may be not to take part in contests for a while, so you will be just facing the problems themselves. And there is no need to take it very formal, like "I've spent X hours today", you should enjoy the process, and I think it's easier to achieve when the process is more free.

        There is no reason in working hard for some placing in some round — it does not show anything at your level. There is no point to take those useless numbers in mind. Enjoy, learn, solve — and only after all that — compete.

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

          Good point. Honestly I don't like the word CP. If someone do web development in a very competitive company he is also doing "competitive programming". Fact is, we do "Algorithmic problem solving", while some fraction of them use "competitive training" to improve their skills, or just for fun.

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

    Your rank in a contest depends completely on the type of problems you've practiced before. eg: if you've practiced lots of graph and not much else, but the contest is full of geometry, probability, etc. then you are bound to fail in that contest because that problemset is not your strong suite. If however there were some tricky graph problems, you might be able to solve it even though the total number of accepted solutions is low ( tricky problem ).

    Today's problemset had my weaknesses. Naturally I failed today. But does that mean I don't have "talent" or anything like that? Mmmm.... I don't know and I don't care.

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

      Here is a problem:

      http://codeforces.com/contest/779/problem/D

      I didn't solve it.

      But when I looked at editorial, solution turned out to be dead simple. There was nothing I didn't know to solve this problem. Yet, I didn't find that solution.

      I honestly can't understand why I didn't find that solution.

      I understand when I failed to solve some problem which uses trick or algorithm I didn't know. But often, it turned out that everything I need to know I already know.

      It's total mystery to me.

      So it turned out that solving problems are not entirely about knowledge.

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

        You expect a lot from yourself, and beat yourself over not being able to fulfill your own expectations. Not just that, you probably spend more time thinking "WHY CAN'T I SOLVE THIS" or "I HAVE TO SOLVE THIS BECAUSE I'VE TRAINED SO MUCH I HAVE TO" than on the problem itself.

        So it turned out that solving problems are not entirely about knowledge.

        This is nothing short of an epiphany! You are right. It's not just about knowledge. You have to know what to let go. Shake off bad days, and keep going.

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

        You can say the same about last round's problem D. Dead simple solution, but only a few people could think it up. So many randomized algos from div1 guys also passed, which means even div1 guys had troube finding the actual solution. It didn't have any DP, tree, graph, mo's algo, centroid decomposition, etc. nothing. Just a dead simple greedy solution that everyone understood when they read the editorial.

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

    I agree with BlackvsKinght. It's just not match with the problems you already trained. Don't quit when the battle isn't over. Let's see it like a bad day and move on. Who knows? Next time maybe you on top 10.

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

    All year, I trained to solve problems almost everyday. I kept journal of how many hours I spent on training per day, per week, per month. According to my journal since May 2016, I spent about 500 hours (and those are only hours when I worked at home in total silence).

    Let's make a deal here and now. Do exactly this again for the year 2017 and let's look at what will happen.

    PS: I've also got far shittier place this year =)

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

    Same for me, took 67th (!) place at 2016 Round 1B. And now 1094th.

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

    Last year in round 1B I screwed up with task B — I spent too much time on it, and at the end I submitted a solution in which my value of infinity was smaller than the correct answers for some test cases (which I didn't catch in the small test set for obvious reasons). I also had no clue that the task C was a standard problem. I ended up 1180th and didn't advance. A week or two later in 1C I lucked out with 31st place and eventually went on to advance to Round 3.

    See how much variance is in such contest? You have good days and bad days. You can still easily qualify in Round 1C while in the first hundred, you'll forget this round and be extremely grateful for all the hard work you've put in to it!

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

Can someone explain how to solve B large in detail.

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

    Hint: O need to be in between Bs, V needs to be in between Ys, and G needs to be in between Rs.

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

    V can only be surrounded by two Ys, so the best way to arrange Vs is 'YVYVY...VY' The whole string can be seen as a single V.

    So we can reduce this problem into the same as the small dataset.

    The only special case is there are only Vs and Ys with the same amount, which is a valid case.

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

Where's round 1B analysis ?!!!

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

Is anyone going to add the recent GCJ rounds to gym?

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

Around what rating(estimated) would you have to be above to solve the first problem? Just curious about how far behind I am :) Thanks!

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

I'd rather have small constraints (say n=1000 instead of n=10^6) than easier problems in small versions.

Now you have to test your large solution carefully, because there arent any pretests.

Fortunately I passed, despite of my c-large failed.

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

Is there any upsolving?

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

    you can practise there on the gcj page itself ! download test files and submit output files !

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

How to solve large C?

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

    I tried all sorts of heuristics and even simulated annealing, without success. My idea was that the reason it's a small input is that with heuristics you need a bit of luck to get it correct, so it's only reasonable to allow multiple tries.

    Can't tell what the correct solutions are doing at a quick glance, so we'll just have to be lazy and wait for the editorial. :(

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

    I only know, how to calculate probability that at least k of n works fine.

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

    Stupid question but how did you solve small C? It looked deceptively simple (judging from the number of successful submissions) but somehow I couldn't crack it after almost an hour. :(

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

      It's a well-known fact that if you know the sum of some numbers and you want to maximize their product, then you need the numbers to be as close to each other as possible.

      In this particular problem, the only thing you can do to make the numbers close is to increase some small numbers so that they become closer to the big numbers we have (or increase all numbers so that they become closer to some greater value). In other words, our goal is to maximize the minimum among all numbers.

      So let's do a binary search over this minimum. Once we fix some minimum V (which is to be maximized), we can take the sum of V - P[i] for all P[i] ≤ V. Then compare this sum to U and proceed with the binary search. Code goes here.

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

    As I saw from some solutions, you need to choose some j >= k, and maximize product of the j highest probabilities (with the method from small C). Choose the best from all such j. Also check the case when you increase the highest probabilities to 1.0 as many as possible.

    I don't know how to prove it.

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

can anyone tell me the approach for A-large B-large?

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

    B large is DP. We want the answer for each of 24*60 seconds such that ith second is cam/jam's responsibility to look after the child such that jam has already looked after the child for t seconds. So the dp table looks like dp[i][cam/jam][t]. Quite simple, but I still couldn't solve it.

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

      How do you account for a possible exchange at midnight with these DP states?

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

        I take the answr for 24*60 + 1th second. Something is wrong with my code as it is currently failing the 1st test case itself, but I think if we take 24*60+1th second, we will get that exchange. This is assuming that there is always an exchange at midnight, unless the read the statement wrong.

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

          Not necessarily. If the same person starts and ends the day, then there would not be a midnight exchange.

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

            So that's what I'm doing wrong. Thanks!

            Well in this case you need one more state to keep track of starting person.

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

    Define f(c,j,i,s) as the smallest number of exchanges so that Cameron has watched the baby for c minutes, Jamie has watched the baby for j minutes and the baby is currently (at the end of c+jth minute) being watched by Cameron (i=0) or Jamie (i=1) and the first one to watch the baby was Cameron (s=0) or Jamie (s=1). Store the activity status of each minute in an array so you can check in constant time who is doing activities at minute c+j-1. Each recursion step is a simple constant time check and there are only 720*720*2*2 states to store in the DP.

    The final answer is min(f(720,720,0,0), f(720,720,0,1)+1, f(720,720,1,0)+1, f(720,720,1,1)).

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

      This looks so much easier to code than what I did :|

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

      1.) Why do we need s i.e. "the first one to watch the baby"?. 2.) I kept the same state except "s" f(c,j,i) and struggled to take into account a possible exchange at midnight. My 1st and 3rd sample input return 1 instead of 2.

      Link to my code:http://ideone.com/JiT8bW

      [Edit] Got it. If the final person is same as the starting person, there is not need of an exchange at night.

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

    In A-large, first sort the pancakes in decreasing order of their radii, so that i+1 can always be placed on i. Let dp[i][j] be max value of exposed surface area of a stack of j pancakes considering only first i in our list.

    Then, dp[i][j] = max( dp[i-1][j], dp[i-1][j-1] - pi*r[i]*r[i] + surface_area(i)) i.e. when we do not place ith pancake or when we place ith pancake on stack of length j-1.

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

      Greedy is sufficient for A large. We can reverse sort based on radius. Then we choose each pancake as the base pancake, and choose k-1 other pancakes with at most this chosen pancake's radius with largest sum of surface area. Once the base pancake is chosen, we know the area of the disk is fixed, we just need maximum area on the sides.

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

      Can it still be

      dp[i][j] = max( dp[i-1][j] , dp[i-1][j-1]+ pi*r[i]*r[i]-pi*r[x]*r[x] + surfacearea(i).

      Where x is the pancakes chosen at for the state (i-1,j-1).

      ?

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

        This is not correct as it would subtract upper surface area of pancake x which is exposed to air.

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

          When the pancake x, was added at state (i-1,j-1), I added the upper surface area of x.

          at (i,j), That pancake x, is glued to the ith pancake so it does not have a lower surface area. We need to subtract both circles of i and x.

          then add the surface area of i. (assuming we choose i at this step.)

          Hos is this incorrect please ?

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

            Let x be the uppermost pancake of j-1 length stack having surface area dp[i][j-1]. We are adding pancake i to this stack. So, the area of x which is now covered by i should be subtracted from dp[i][j] and surface area* of i should be added.

            *Note: We are not considering surface area of it bottom side

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

      I solved it using DP.

      1) Choose all possible top pancake. Let this index = prev.

      2) DP[prev][k] = maximum surface area of choosing k pancakes when prev is the previously chosen pancake.

      The complexity is much larger than it appears as there is an inner loop in the DP. Better approach would be to go with the greedy one by BlackVsKnight.

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

    I used a greedy approach.

    First of all, sort all intervals by start time (along with marking which one belongs to C/J). Now two consecutive intervals might belong to either same person or different person. The answer will atleast be the number of consecutive pairs with different person.

    Answer will increase by 2 only when C looks after the child between two Js or if J looks after the child between two Cs. So I'll try to avoid these situations.

    Code: here

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

For problem A in round 1C, I wasted about 1.5 hour but couldn't find a mistake (many WA attempts) in the approach. I am solving it with dp(index, required) which is index position am currently on and required pancakes, this outputs two values, firstly best answer and secondly last disc index included in this answer, second part is used to add new disc area to existing stack. Finally required answer is DP(n-1,k).first.

I changed my approach at last to make it AC. But it will be really helpful if someone could guide me to the mistake in previous approach.

here is the code

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

    firstly best answer and secondly last disc index included in this answer, second part is used to add new disc area to existing stack.

    We cannot use best result calculated for i + 1 disks and attach it to i'th disk. It may be so that we need to take a disk with a smaller surface area on the i + 1'th place.

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

      Please check the code, the fault is not in the algorithm, I am taking care of it in dp state traversal.

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

        I look through the code several times and I don't yet understand how do you handle that.

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

    The problem with that approach, is that in the intermediate calculations, you might choose to ignore a stack that is part of the best output, in favor of another stack that appears better at the time.

    That is because the score at any moment, is dependent on both the side surface area, and top surface area. And since the top surface area changes as we go back up in the recursion (by adding larger pancakes to the stack), we can't really depend on it while choosing which stack to proceed with.

    I guess it's better explained using an example.

    2
    2 1
    1 15
    5 1
    3 2
    1 15
    5 1
    10 10
    

    In the first case, your code will tend to choose the second pancake (5, 1) over the first (1, 15) as alone it has the larger surface area.

    In the second case, your recursion will lead you to the same case as the first example, and yet again choose the (5, 1) pancake, while it's better to choose the (1, 15), due to the presence of the third one. .

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

How do I solve C small-2 (in round 1C)

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

    I used adding an increment of 0.00001 unit to the lowest priority core in a priority queue repeatedly to solve C small-1

    I tried a similar one for small-2 ( choosing top k cores for prirority queue) but it failed..

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

How to solve "Ample Syrup" in linear time?

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

    I might be wrong but here is my guess, let's take K pancakes with maximal side surface. Then we can prove that in optimal answer there will be at least k — 1 from this set. So we just see which one has maximum upper surface in this set, and change it with one pancake from other N — k pancakes, at a time and see if answer is better. It is O(N).

    EDIT: To make it clear, you don't necessarily remove bottom pancake from those K pancakes, you just choose different pancake from other N — K ones to be the new bottom and remove the one with minimal side surface from starting K pancakes.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Solved 1C A with DP

Just for curiosity, what's the negativity here ? When you ain't sure about the approach and the constraints are small, you should go for DP if it's possible.