desert97's blog

By desert97, history, 6 years ago, In English

Preliminary, changes to come possibly.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +107
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

No solutions?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long int
    int main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
    #ifndef ONLINE_JUDGE
    // freopen("input1.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif
        ll n, sum=0 ;
    int v[]={100,20,10,5,1};
        cin >> n;
    int i=0;
    while(n!=0){
    sum+=n/v[i];
    n%=v[i];
    i++;
    }
    cout<<sum;
    return 0;
    }
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Explain to someone how the solution working for O (n ^ 2) has been tested in task B

»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I see some of the participants passed Div.1 C by random shuffling and greedy approach. Could anyone explain the rationale behind this solution?

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

    My solution shouldn't have worked but it did. Basically i was taking vectors greedily but because i knew there were countertests, i did so starting from the last vector and going back to the first.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I think creating test cases to break a greedy algorithm is pretty tricky — each vector needs to be roughly orthogonal to the greedy sum of the previous ones, and as soon as one adds some randomisation it's basically impossible to break.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      To avoid the use of randomization, the authors may put some constraints like the found solution should be lexicographically smallest by defining -1 < 1 or vice versa.

      But at the same time, this would mean that the problem is looking for the unique solution which can be obtained only if the solution is similar to intended solution.

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

For Div1 F, what is the O(n) interpolation you had in mind? I used Lagrange interpolation in O(n^2), and while I can see how one could optimise that to O(n) by incrementally computing each term from the previous one, it would add a lot of complexity.

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    Though I don't have the formula on hand, if you write out what Lagrange interpolation gives and then substitute x = D into the formula, it becomes a sum of the dp values times some binomial coefficients. We can do this in O(n) with some preprocessing.

    Here is the code: http://codeforces.com/contest/995/submission/39639811

    You should post it here if you figure out what it is :P

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

      That's more-or-less what I had in mind, although that code is still O(n^2). It would be pretty easy to make O(n) though by first computing and then using that to get for each j.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C-tesla, in the first sample, why am I getting WA cause I put car No 5 in (4, 1) as temp place? I will put it in right place after that.

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

    The problem statement says that a car can only be moved into row 1 or 4 if that is its designated parking spot.

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

    You can't do that. "Furthermore, Allen can only move one of his cars into a space on the first or fourth rows if it is the car's designated parking space."

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Rating drop for sure now :/ this was a bad day.

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

    Just now, I wrote something very similar to your solution with E except I used random_shuffle and it passed, you should give it a go.

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

      How did your solution work? We can't choose vectors randomly right?

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        We choose them greedily

        let's say the vector pointing to current position is p

        we calculate

        p — a[i] and p + a[i]

        and choose which one has the smallest distance from (0,0)

        Now this is definitely incorrect greedy and there is probably a counter-case, but it is sort of hard to break.

        But now, seeing that the process is O(n), I thought if I scrambled it it is unlikely the solution would fail the constraints over a thousand times so I continued to run this process until it passed.

        Also note I used "sqnorm" which is just the magnitude squared, becauseI wanted to avoid floating-points and sqrt() function, but I don't think it's necessary.

        UPD: Good job on solving :D

»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Problem E says "We can show that the answer always exists."

While statistically I'd be very surprised if it didn't, does anyone have an actual proof?

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

    I wanted to ask the same question. Even though I pretty quickly thought of "random" solution which I was sure will pass, I though that authors should have an actual proof to state something like this which would probably be a constructive provable solution.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +14 Vote: I do not like it

      Well, this graph is called the "Margulis expander". An expander graph is a graph that kind of "expands" optimally in a BFS. There are explicit lower bounds on the expansion using deep number theory.

      In other words, yeah I can "prove" the solution works, but not in a way that works in contest. To be honest, I just was feeling experimental with this problem.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +37 Vote: I do not like it

        LOL. I had exam in university like two weeks ago and large part of that course was about expanders. We had 'Margulis expander' in the course but I found the proof so big and ugly so I didn't even tried to learn it and even forget the what it is about :) Could save me some time on trying to come up with actual solution.

»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

math tasks

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for B.would any one explain how the following two codes differ in logic... one is accepted while other is giving TLE.. http://codeforces.com/contest/996/submission/39630623 http://codeforces.com/contest/996/submission/39631431

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2-E, I don't know what is the difference but in the solution I submitted during contest, I processed each vector in the order given and kept changing the position vector through my algorithm which got WA on TC 79. However,after contest I did a slight change and stored all the vectors and then iterated in reverse manner, from n-1 to 0 using the same algo and I got an AC. Can anyone explain to me what is the difference?

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

    It is hard to make good data. Probably the latter solution just gets lucky.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please share the model solution ? Most solutions I’m finding use randomisation.

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

    Even I got WA on TC 79. Did you use the fact that whenever we add a vector we just try to be greedy and hence take that sign which reduces the distances and nothing more? Is there any problem with this approach?

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

      I did the same and I dont know what is wrong with the approach.

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

    Sir, I want to know why that claim is right. If I have two vector, one of them is (5,6) and its length is max, the other is (5,5). But their sum is better than the length of (5,6). So, why that chaim is right?

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem E. Here is BFS, that finds the answer of length  ≤ shortest_path_length + 3. http://codeforces.com/contest/995/submission/39632072

(It's simple bidirectional bfs with used array for buckets of size 4 on bitset),

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

desert97, the complexity of making an entire circle is actually 2*n, not k.

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

    There are only k cars in the cycle. So advancing k cars by one is O(k).

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

      But at each move, you move into neighbouring empty space which means you move one by one. It's not clearly described though.

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

        The time complexity of it is O(2n) (unless you do it in a clever way), but the number of moves is O(k).

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody give me the source code of Div.2 B no problem with the same approach which has been provided in the editorial?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have solution for div1 C as described in editorial (the binary tree and vectors as leaves)

»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

nice Python solution for DIV2 problem B

n, a, m, res = int(input()), [*(map(int,input().split()))], 10e9,-1
k = [ math.ceil((ai-i)/n) for i,ai in enumerate(a) ]
print(k.index(min(k))+1)

you can find more like this here: https://codeforces.com/blog/entry/60059

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone solved Problem C using dynamic approach please share it. Thank You

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Finding a linear time solution to “suit and tie” is equivalent to counting inversions in and array. As far as I know there is no known exact algorithm for calculating inversions in O(n).

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

    Okay, you're right. So is probably the best we can do.

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

    How do you reduce counting inversions to suit and tie?

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Look at your solution.i got idea of counting inversion from your solution :P

      but what is idea behind f[a[i]]<f[a[j]] will add into answer

      count how many value already less than f[a[i]] and update it using BIT!!

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        This is not what I asked. What I am asking is: Given a problem of counting invesions, can we reduce it to an instance of the problem "suit and tie", which is necessary for equivalence.

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

          Consider a permutation of 1 through n, and place 1 2 3 ... n to the left of this array. Then the answer for suit and tie is the same as the number of inversions of the permutation plus n(n-1)/2.

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

            Then the answer for suit and tie is the same as the number of inversions of the permutation plus n(n-1)/2.

            I'm sorry but this fact is not obvious to me. Can you please elaborate ?

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

              As in the editorial, we only need to consider for each pair, the relative ordering and add up the number of swaps needde. If a < b, the possible orderings in our sequence is a ... b ... b ... a or a ... b ... a ... b.

              In case a b b a there is one inversion in original array and two swaps needed.

              In case a b a b there is no inversion in original array and one swap needed.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      If you know where everything should go, you can relabel the people to numbers 1..2N. Now, you are asking the question “given a permuation of 2N values, how many adjacent swaps are needed to sort it”.

      The general idea is that your array will become sorted when there are 0 inversions left, and that each adjacent pair swap will eliminate (or add, but we don’t want that) 1 inversion. So therefore the number of adjacent swaps needed is equal to the number of inversions.

      https://stackoverflow.com/questions/20990127/sorting-a-sequence-by-swapping-adjacent-elements-using-minimum-swaps

      Edit: ksun has commented how to turn inversion counting back into the suit and tie problem.

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

        So is the problem equivalent to -

        1. Relabel the integers from 1 to 2n
        2. Count the number of inversions

        I believe the number of inversions of a permutation can be found in O(n) time. So, is this an O(n) solution ?

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

            Wait ... What about when you decompose into cycles ?

            int no_of_swaps = 0;
                vector <int> visited(n + 1, false);
                for(int i = 1; i <= n; i++)
                {
                    if(!visited[i])
                    {
                        int cycle_size = 0;
            
                        for(int current = i; !visited[current]; current = permutation[current])
                        {
                            visited[current] = true;
                            cycle_size++;
                        }
            
                        no_of_swaps += cycle_size - 1;
                    }
                }
            

            Am I wrong ?

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

              4 3 2 1

              The cycles are 1 → 4 → 1, 3 → 2 → 3. Your algorithm will return 2, while the answer is 6.

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

                I understood the mistake. Cycle decomposition counts the parity of the permutation in O(n) time, not the exact number of inversions !

                Thanks !

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        I have a doubt about how to do the relabelling. Can you help me understand how exactly to relabel the integers ? I was thinking every pair but that’s not optimal. Do you need to know the optimal arrangement apriori before reducing it to inversion counting ?

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

          You can do the relabelling in increasing order. Let the original array be 3 1 2 3 1 2. Relabel 3 as 1 , 1 as 2 and 2 as 3. The transformed array is 1 2 3 1 2 3. Then find the number of inversions in the transformed array.

          Code

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          I did the relabeling in the following manner: a: original array. b: relabeled array.

          num=1000;
                  
                  outer: for(i=0;i<N;i++)
                  {
                      for(j=i-1;j>=0;j--)
                      {
                          if(a[i]==a[j])
                          {
                              b[i]=b[j];
                              continue outer;
                          }
                      }
                      
                      b[i]=num++;
                  }
          
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Great contest ! It met my expectations and the editorial is very well written compared to most CodeForces tutorials.

In Div 2 E, I didn’t understand why two vectors in the same 60 degree segment have sum less than r. Can someone please explain ?

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

    Geometry: If AB < 1, AC < 1 in a triangle, and , then BC < 1. This is because the angle opposite an angle less than 60 cannot be the longest side of the triangle.

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

      Wow ! Great proof. Should have been included in the editorial !

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone please tell me whats wrong with this code for problem 996B.39614833 . Somebody plz help me

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Wrong logic.

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

    You forgot that he can go many laps around the queues, so after your for loop, if it didn't find any empty queue you can't just output the last queue you must instead let him walk around the queues again and again until he finds an empty queue.

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

someone plz explain how greedy approach will work for div2 D

If the leftmost person is in pair a, swap the other person in pair a left, to the second position. Now the first two people are both in pair a, and we repeat the process on the remaining n−1 pairs of people recursively.

i am not getting this line :|

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Notice that by switching the other person to the left, we will switch everyone between them to the right. We don't want to switch the leftmost pair because there's a chance that some person inbetween the pair will be farther than before

    For example this tc: 1 2 3 2 4 1 3 4 -> 1 2 3 2 1 4 3 4 -> 1 2 3 1 2 4 3 4 -> 1 2 1 3 2 4 3 4 -> 1 1 2 3 2 4 3 4 -> 1 1 2 2 3 4 3 4 ....

    If we switch the right 1, all other pair won't be farther than before (2 pair distance will be the same, 3 and 4 pair will be closer). But by switching the left 1, the 3 pair and the 4 pair will be farther.

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

      okay got it!!

      can u explain me logic behind this solution

      http://codeforces.com/contest/995/submission/39620454

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

        For each number(i), we will eventually need a swap with j (j < i) if a[i] leftmost number < a[j] leftmost number

        1 2 3 2 4 1 3 4 -> 6th number and 7th number will eventually swap with 5th number, but 5th number won't need to swap with number before it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A, why does this matter? "The solutions works because each number in the sequence 1, 5, 10, 20, 100 is a divisor of the number after it."

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Basically, this is a special version of the coin change problem.

    In general, this problem cannot be solved by Greedy, and instead you should use Dynamic programming, however if the coin system has certain properties, it can be proved that greedy works. The proof goes as follows for each coin you get the maximum amount you can do, and argue that any larger, it's better to use coin i + 1.

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

    Lets say you have different coins. For instance coins with the values 1, 3, 4. Try to form the value 6 with them. The optimal solution is 3 + 3, while the greedy one gives the worse result 4 + 1 + 1.

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

      I think he asked for a proof of why does greedy algorithm work for that particular denomination and not for an example of how greedy fails.

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

        Yeah that's exactly what I want.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          Here's a mathematical proof for it:

          Let denote with (a, b, c, d, e) a solution (you take a coins of value 1, b coins of value 5, ...) If you apply the greedy algorithm, then you obviously get a solution with . Also you can convert each such tuple back into its value a·1 + b·5 + c·10 + d·20 + e·100, a non-negative number.

          Obviously these two operations form inversions. E.g. if you apply the greedy algorithm on the number x = a·1 + b·5 + c·10 + d·20 + e·100, you will get e coins with value 100, because a·1 + b·5 + c·10 + d·20 ≤ 4·1 + 1·5 + 1·10 + 4·20 = 99. In the same way you get d coins with value 20, since a·1 + b·5 + c·10 ≤ 4·1 + 1·5 + 1·10 = 19. And so on.

          So the greedy approach is a bijective function between [0, ∞) and [0, 5) × [0, 2) × [0, 2) × [0, 5) × [0, ∞).

          Now, assume you have an optimal solution (a, b, c, d, e) for some x, that is not identical to the greedy solution. Because the greedy approach is a bijection, the solution cannot be in [0, 5) × [0, 2) × [0, 2) × [0, 5) × [0, ∞). Therefore either a ≥ 5, b ≥ 2, c ≥ 2 or d ≥ 5. In either case we can replace some coins and get an even better solution. Therefore we have a contradiction, which means that the greedy solution is always optimal.

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            Very nice proof. Thanks. For denominations where one of them is not a divisor of the next, we cannot have such bounds for a,b,c,d,e, so greedy solution may or may not work for such cases right ?

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

              Yes, you can't find bounds that will form a bijection.

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

              You can still use greedy exchange though.

              This videa has nice proof starting at 9:30 and only takes about 10 minutes.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think in editorial for 996 B the condition k+tn>=ak is not correct because on first step nothing is decreased so it should be k+tn>ak.

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

    We start indexation since 0.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

" (Maybe it can be even done in O(n), anyone?)."

This is regarding div-2 D. Can anyone please link me an O(n) solution? desert97

»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Isn't it too easy for coding when you have the idea of the problems? Div1 DEF can all be solved in 50-60 lines(maybe less) . I think a good contest should also focus on the implement difficulty.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did this bruteforce approach for Div-2 B get accepted ? Code : http://codeforces.com/contest/996/submission/39628778

»
6 years ago, # |
  Vote: I like it +76 Vote: I do not like it

div1F , a much simpler solution is to just calculate dpi = number of ways to assign i distinct numbers to the tree nodes , then answer is just .

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    rajat1603 can you explain how dp[i] is calculated? I am also confused on how to calculate D choose i for large D values efficiently.

    EDIT: I'm good with the D choose i part, since i is at most 3000.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +24 Vote: I do not like it

      dp1i =  the number of ways of assigning numbers  ≤ i to tree [just the solution to the original problem] , this can be calculated as .
      now to calculate dpi =  number of ways of assigning exact i distinct numbers to tree , we can use the formula .

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

    I don't get how this is the solution to original problem.

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone please explain Div-2E(Div-1C) — Leaving the Bar? I have read the editorial but unable to understand anything. I can't visualize the solution described in the editorial and can't relate the editorial with the problem statement.

Thanks in advance.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

basel-99 USACOW The solutions works because each number in the sequence 1,5,10,20,100 is a divisor of the number after it.

»
6 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Here are my solutions to the problems of this contest.

I found Div2 E/ Div 1 C a very different question. So, I tried my best to explain it here with the help of the editorial here.

Here's my editorial to Div 2 D/ Div 1 D

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

For the Div. 1 E problem, what would be a rough value of the probability for Solution 1? I don't find the probability of an "intersection" very high. Could you please show how to do the calculations? Thanks.

»
6 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I did weird implementation of Suit and Tie of O(n sqr.) complexity:
http://codeforces.com/contest/996/submission/39659575

Happy Coding

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone direct me to the idea of Lagrange Interpolation? I understand the general idea of it, but how do you put it to work in div1F?

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

    Given n+1 points, Lagrange interpolation lets you find the polynomial of degree bound n which passes through all the given points. Basically we define a polynomial f(x), which gives us the answer for d=x. Now, we calculate the first n+1 integer values of this polynomial via dynamic programming (f(0) through f(n)), and then use Lagrange interpolation to find the polynomial f(x) (which has degree bound n as per lemma in editorial), and then evaluate the polynomial, at f(d), to get the answer.

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

      mmmm and since Lagrange interpolation is the only unique solution at the lowest degree this fit. First of all thanks, I got the idea now because of that :) Maybe you also know why the lemma is correct? it has a maximum of x(x-1)(x-2)...(x-n) I guess because it will always use "d choose n" at max. Although this is true, how can you know this beforehand...?

      Never the less, this does make the code writing very simple...

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

        Let P(x, a) denote the no of possible labellings for the subtree rooted at node n, and the label of node a equals to x. Now

        You can show that prefix sum of any polynomial on integers will have degree 1 higher than the polynomial itself (relate on the lines of sum of kth powers of first n natural numbers).

        Let ss[i] denote the subtree size of node i
        To make induction work, we assume for now that the degree of polynomial for every child i of node a was ss[i] - 1. Hence,
        The base case for this induction will be the leaf nodes, where P(x, a) = 1 and thus the assumption is valid. Hence, our induction holds.
        Now, the final answer will be which'll have degree ss[1] = n

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      But why the complexity of the interpolation is O(n) mentioned in the tutorial? I think the normal Lagrange interpolation is O(n2). I don't really get the point.

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

desert97 if div2C tesla had asked about the minimum number of moves to park all the cars, I guess rotating the circle wouldn't have been a good strategy. Any idea on how could we find it?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I doubt it's possible in polynomial time. Might even be possible to show it's NP-hard.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you post links to your solutions desert97

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please disscuss the Binary indexed tree approach for Suit and Tie Ques

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

    You can just simulate the process from the editorial. Let's say that the sequence looks like this: abc....ab...c.... First we want to bring the second a next to the first one. This takes |number of elements between a and a| steps. Then you want to bring the second b next to the first one. This takes |number of elements between b and b without the a-s| steps, because the second a is already to the left of the first b (if we simulate the process). And so on.

    To solve this with BIT. Initialize the bit with an array of 1s. For each letter you to range_sum steps, and afterwards you delete the two elements by setting them to 0.

    I'm sure that there are multiple approaches.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem Div 2E / 1C editorial : Any two points in this sector will have distance at most r. How to prove this ?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If div2 — 995C leaving the bar — if I greedily take every vector's sign so that it reduces the distance from the origin than this approach shows WA on TC79. What is wrong with this approach?

My submission — #39620913

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Try this :

    3
    1000000 0
    0 1000000
    707105 707105
    

    Draw the figure on paper and you'll know the greedy approach is wrong. You may want to see the discuss above.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div2.F / Div1.D , how can we get (v_i,0+v_i,1)/2=E_f by induction ? I tried some ways including induction, but failed. Can someone please explain it ?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

According to the solution of problem B, shouldn´t the result for test case n = 3 and {5, 5, 5} be 2? Since for the first gate, you can write 1 + 3*2 = 7 > 5, for the second one 2 + 3*1 = 5, and for the third one 3 + 3*1 = 6 > 5. Can someone explain to me why is the answer 3?

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

    I'm not sure why it says >= in the editorial when I think it should just be >. In your example, there are 5 people in each of the queues so the queues are only available starting at minute 6. So for each i you find the minimum t such that k + t*n > a[k] instead of >= a[k].

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For div2.E/div1.C, I implemented in a tricky way like this.

I wonder if this can be proved to be correct and if not, how to hack it.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please elaborate the euclidean algorithm solution to E? Thanks!

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +21 Vote: I do not like it

    First, since all operations are reversible, we can just get u and v to some common number (which is 1 in this case).

    Let (a,b) represent the number a*b^(-1) modulo p (for v != 0). Then, we can see the following operations:

    • Subtract one operation corresponds to moving from (a,b) -> (a-b,b)
    • Inverse operation corresponds to moving (a,b) -> (b,a)

    This is similar to the euclidean algorithm (we do the first operation if a > b, otherwise we do operation 2, until we get to (gcd(a,b), gcd(a,b))).

    Of course, this might not be very fast for (u,1), but we can instead do it with (u*x mod p, x) for some x!=0, which is an equivalent state. The claim without proof is that for random x, it is likely this will take < 100 steps (not sure why this is true either).

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

      Thanks for the clear explanation!

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I tried the gcd approach, however picking a single random x does not seem to work, but it does work for small enough number of attempts with different values of x to get an AC verdict. The submission is 39734619. Am I missing something here?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How the problem 996A Hit The Lottery can be solved using dp ? Please help if anyone knows.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi

I was trying Problem C Tesla.

I have written this code which gives Time Limit Exceeded on test case 6.

http://codeforces.com/contest/996/submission/39723591

I am rotating the cars clockwise.

Can anyone tell me why is my program taking so much time? I think it is O(n^2). How do I reduce running time?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain the initial dp used in F?

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

    let f[i][j] = the answer of the i-th subtree and the max salary won't exceed j . Then f[i][j] = f[i][j-1] + π(f[son[i]][j]) where π means the product of all things involved in the brace .

»
6 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

In div2-E, div1-C
39809949
39809939
I don't know why first code is wrong but second is right. Difference is just for-loop 0 to n -> for-loop n-1 to -1. why? why second is right??
How about testcase like below
3
600000 -600000
0 999999
1000000 0
When input this testcase, first code output 1 1 -1, so p = (-40000, 399999) and second code output -1 1 1, so p = (40000, 1599999).

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

    It is hard to design data to break all solutions in this problem. The second one just got lucky.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh, i know that make all-round testcase is hard.

      Anyway, I'm glad it's a tastcase-problem ... I thought there was something else I did not know about. Thx!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had seen some people's solution of Problem C. And some of the code are wrong when I input test case below: 3 600000 -600000 0 999999 1000000 0

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Leaving the Bar problem, how can we be sure that it is always possible to construct a circle through any 3 points of some radius r with origin as the center?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Of Div.1 C, what is the probability to pass a worst case performing $$$k$$$ times random_shuffle and greedy algorithm?