Golovanov399's blog

By Golovanov399, history, 6 years ago, In English
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
  • +14
  • Vote: I do not like it

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

Can someone explain exactly why does greedy solution works for Problem C ?
Update :- Understood Now, after translation of editorial

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

    The greedy algorithm I use is a little bit more complicated but you can catch what I mean more easily.

    The algorithm goes as follows:

    1.binary search part. Use binary search to find how much lecture notes you can read In the two days.

    1. greedy part for the checking function of binary search. Iterate through each note from x to 1. For note i, If you can put it in the day which has fewer hours to spend, It's always better. So we just iterate through. If we find a note that we can't put it in any of the days, we try a smaller amount.

    2. To get the answer uses the same algorithm as the checking part. Just iterate from x to 1, and put the note in the day which has fewer hours to spend. If you didn't get this, I may post my code:44658856

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

Quick Editorials! And the editorials for 1031B & 1031C in English were mistakenly published in Russian.

Only I used DP for Div.2 B (maybe because I am just a Pupil), sadly?

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

can u plz explain why this is wrong ?? Div2D 44650538

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

Can you proof why this part-> "Let's iterate over all lecture notes from x to 1 , and on each step we put it into the first day if we can, otherwise if in the first day we have w > 0 free time then we put the lecture note w < x to the first day."

Why mentioned part gives the optimal solution?

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

    There are two possibilities:

    1. All lecture notes are in the first day, this case is trivial.

    2. When we tried to put the x-th lecture note into the first day, there was only w free hours. Let's put the lecture w instead then. Now the first day is full, and since a + b is at least x(x + 1) / 2, the second day is long enough to read the remaining notes.

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

      Why can't we start with 1 ?

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

        I propose an algorithm to divide all lecture notes into two groups properly. If I started with 1, I couldn't fill the first day because the w-th lecture note would have been already used, so iterating from the greatest is crucial for me.

        You can try to start with 1 and act in another way, maybe there is an algorithm which solves the problem.

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

          I tried and it worked. I have started with 1 and filled the first day. The strategy I followed while filling is, I greedily filled the numbers until their sum became greater than the capacity of the first day. Then I removed (sum — a) from the set of the first day. And filled rest in the second day. It worked. Here is my submission : http://codeforces.me/contest/1072/submission/44715934

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

            Yeah I see, it's ok, you fill the first day anyway, but you do it with some set like

            {1, 2, ..., k - 1, k + 1, ..., l - 2, l - 1, l}, 

            while author does it with a set like

            {k, l, l + 1, l + 2, ..., n}.
»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can somebody please explain to me why my O(n^2) code for problem D is getting TLE? Help is very appreciated 44655948

EDIT:It's the string comparison, my mistake

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

Can anyone please help me with question B. I am new to programming and kind of stuck. how to move ahead with the hints given above?

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

    I'm not a native English speaker, sorry for my poor explanation.

    It's easy to find that if we get the first two items of the series t, we will be able to determinate whether it's possible to build a t meets the conditions.

    Then we will try every possibilities for t1 and t2, we will be able to find the relationships between t and a, b.

    Finally we try every possibilities for the first two items (not so much, though), and find if it is possible to meet every ai and bi (we have one item of ti, and it's easy to determinate whether it's OK for the other items).

    My solution using DP is described as following: Let dp[i][j][0] standing for the possibility of i-th number of t is j, and dp[i][j][1] means which number is the number before i-th number of j, we can easily iterate k from 0 to 3 for the last number of t, and we can get:

    Specially, we have dp[1][0][0] = dp[1][1][0] = dp[1][2][0] = dp[1][3][0] = 1.

    Then we can judge if dp[n][·][0] is 1, for YES or NO, and if the answer is YES, use dp[n][·][1] with a stack to print t.

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

    Just use simple depth-first-search. The hint means(I think) that you when you brute force the problem, you will not get a TLE.

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

      Hi, can you elaborate more on your DFS approach? Thanks!

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

        Well this isn't so hard. The code is like the folloing

        If the process give no answer, just output "NO".

        44657446

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

        It seems that DFS can be hacked by this data:

        input:

        100000
        3 3 3 2 3 ...(repeat)
        0 2 0 0 0 ...(repeat)
        

        output:

        YES
        1 2 3 0 2 ...(repeat)
        

        DFS will get TLE or RE (tested in my computer).

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

        Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!

        Because if ti has been determined, ti + 1 will have only one value to choose. Specially, if a = 3, b = 0, t can be 0, 1, 2, 3. But if ti has been determined, we should not worry about ti + 1.

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

    There is some interesting observation.

    there exist at most one value of t(i) for specific value of t(i+1),a(i),b(i).

    formally, if there exist t(i) such that t(i) | t(i+1) == a(i) and t(i)&t(i+1)==b(i) then t(i) can be one of the {0,1,2,3}. it means that the equations t(i) | t(i+1) == a(i), t(i) & t(i+1) == b(i) has exactly one solution of t(i) if we know the value of t(i+1),a(i),b(i) or doesn't exist.

    you can see this fact using my below code. just run the code and you will see that observation. ~~~~~

    include<bits/stdc++.h>

    using namespace std;

    int main(){ for(int i = 0;i<=3;i++){ // values of a(i)

    for(int j = 0;j<=3;j++){ // values of b(i)
    
            for(int k = 0;k<=3;k++){ // values of t(i+1)
    
                cout << i << " " << j << " " << k << " -> ";
    
                for(int l = 0;l<=3;l++){ // possible values of t(i) 
                    if((k & l )== j && ((k|l) == i)){
                        cout << l << " ";
                    }
                }
                cout << endl;
            }
        }
    }
    return 0;

    } ~~~~~

    now simply take t(n) as 0,1,2,3 one by one and find t(n-1),t(n-2),t(n-3)... if there exist sequence for some t(n) then print it otherwise change the value of t(n)..

    see this for full code (c++)

    sorry for my bad english. Please,right me if i'm wrong.

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

Problem 1031A - Golden Plate can be calculated directly by formula:

2k(w + h - 4k + 2)

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

can you please explain problem B a little more ? i was not applying dp . the thing i concluded was these two conditions 1. a[i]|b[i]=a[i] 2. a[i]&b[i]=b[i] . If any of these fails for any index ,it will show "NO". How to proceed for rest solution ?

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

    I'm not a native English speaker, sorry for my poor explanation.

    There is something interesting about Bitwise operation:a^b=(a|b)-(a&b).

    So let c[i]=a[i]-b[i],then just let t[1]=0~4 ,and calculate the others t by array c.After this,just judge the array t if or not satisfy the conditions

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

Golovanov399 I think there is some mistake in editorial of 1031B — Curiosity Has No Limits because 4th case "If t1=0 and a1=1 and b1=1 then t2= 1" is wrong as t2 can't have any value because since t1 is 0 , b1 can never be 1 as b1=t1&t2, instead it should be "then there is no such t2".

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

Can someone explain their solution for 1031D plz ?

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

Can someone help be with this solution for 1031B ? Link:44642434

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

how to solve the Div2.D with above algorithm and not get MLE?

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

In Div2D, how to write DP for the lexicographically smallest path from (i, j) to (n, m) in O(n2) memory? My solution requires O(n3) memory (with recursion using memoization).

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

    I used something bfs-liked instead , I have the list of last-minimum block at that length then(For each row there can only be at most 1 element so this list will never exceed n) name A.

    Considering this example

    bcc
    caa
    ggg
    

    We know that the first character must be 'b' , second character must be 'c' , BUT WE DO NOT KNOW IF THE 'c' IS FROM (1,2) or (2,1) , so after we append 'c' to answer our A must contain both (1,2) and (2,1) for future use.

    For the next length each block in A can generate 2 more blocks. For the sake of simplicity i used std::set name B to store it to get rid of duplicate blocks and auto sort for me.Then the next character of the answer is value of the first block in the set(set sorted for me). So I get all the blocks from B which has the value equal to the minimum block back into A and repeat until we reached the answer's length.

    This way I do not need to store all the string length but only 1 letter for each block in list A. So the total memory used for this step never exceeds O(n) I guess...

    Sorry for my bad English

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

      Thank you! This makes sense. But I think this requires O(n2) time for every time we ask for path from some (i, j) to (n, m). If there are multiple such (i, j) pairs (let M) to check, this would take O(M × n2) time, where M itself can be atmost O(n2). How to handle this?

      UPDATE: I understand it now. We will initialize our set B with these pairs.

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

In question C, why can't be sum of the lecture notes be exactly equal to a+b, it will only affect the last term i.e. x; the sum n+m will still remain same!!

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

    it can be but it won't increase the count of lectures. ex: a = 9, b = 12 output: 2 3 6 4 1 2 4 5 but for a = 10 and b = 12 output: 2 3 7 4 1 2 4 5 OR 2 3 6 4 1 2 4 5 here the sum of lecture notes is exactly a+b but it doesn't affect the count.

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

Why we always can make all elements be equal to zero when n>=8 in problem 1031e?

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

    You can run bruteforce

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

    If you have >= 8, you can get rid of a 1 in any position.

    eg:

    A)

    0 0 0 1 0 0 0 0
    

    Can be done with:

    1 0 1 0 1 0 0 0
    0 0 1 0 1 0 1 0 
    1 0 0 1 0 0 1 0
    

    B)

    0 0 1 0 0 0 0 0 
    

    Can be done with:

    0 0 1 1 1 0 0 0
    

    thus creating 2 instances of (A)

    C)

    0 1 0 0 0 0 0 0
    

    Can be done with:

    0 1 0 0 1 0 0 1
    0 0 0 0 1 1 1 0
    0 0 0 0 0 1 1 1
    

    Similarly, D)

    1 0 0 0 0 0 0 0
    

    Can be done with:

    1 0 0 1 0 0 1 0
    0 0 0 1 1 1 0 0
    0 0 0 0 1 1 1 0
    

    Ones on the right hand side are of course symmetrical

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

      Excuse me,could you please explain it more clearly?I am not very smart so I can't understand it.

      Sorry,but PLEASE!!

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

In the problem C Cram time, I did the exact same thing, and i guess it runs in O(n)time, still it showed me Time limit in test case 15.

I would really appreciate it if someone could check my code once, please. http://codeforces.me/contest/1072/submission/44647241

44647241

Thanks a lot!

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

I have an alternate solution of Div1D without graphs. We can use dynamic programming on each vector (x1, x2, ..., xn).

Assuming that the upper bound of number of divisors isn't great, we have a fast DP the states are (prod, pos), where prod is the target product, pos is the current position in the vector. Iterating over all divisors of prod, let's assume that k is a divisor of prod, then a possible state is (prod / k, pos + 1) and it "costs" abs(x[pos] - k) to go to this state. When we reached the end of the vector, we have another mini-DP to calculate the minimal number of operations to get remaining prod. Then, the answer for (x1, x2, ..., xn) and (y1, y2, ..., yn) is min(dp(i, 0, x) + dp(i, 0, y)), 0 ≤ i ≤ 256.

Due to very small constants it works in no memory and in relatively small time.

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

I think Div.1 C involves some background knowledge about linear algebra. Each operation of flipping ax, ay, az can be viewed as a 01-vector v where only vx, vy, vz are 1. We want to find a linear combination of all such vectors that equals to the given array (modulo 2), and it is easy to verify that only when n > 7 the rank of all such vectors equals to n.

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

Can Anyone point out mistake in my code.(Div2 C) http://codeforces.me/contest/1072/submission/44638820

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

In Problem C My code shows time limit exceed at test case 15.....

please explain why is this happening while I follow the same concept as mentioned above.... 44751444 My code is working properly on test case 15 at (http://ideone.com)

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

    long is 32-bit on Codeforces but 64-bit on Ideone. Use long long instead.

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

How should actually brute force in div2 E work when we are left with <=10 elements?

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

For Div1E, do we really need to consider precision issues and prove that our solutions will be precise enough? Why don't we prove it for other problems which also require floating-point arithmetic?

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

    As a contestant you don't have to prove anything, but as the editorialist, I felt responsible for doing this.

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

Problem C.I want to know why I get WA in test15. I put 1,2...,n into A as many as possible. defined the rest of A is x, I remove the n and put the n+x into A. the I put from 1 to INF if it is not in A.Your text to link here...

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

for Div.2 A I think the input 5 5 2; The answer is 17. Am I right ? ( if you add this to the main test, many would WA...

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

Is it possible to add data after the contest?

I found that almost all AC submissions of Div1.E was wrong

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

    It's possible (the solutions won't be rejudged, though). Moreover, if you happen to mean all AC submissions of Div2.E and during the contest, then more tests have already been added.

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

      I see.There are 3 small sets of data.They are made when I debug my program using some of the AC codes.But I think my outputs are correct but their outputs are wrong.Would you please check if they're correct?

      And I'd like to thank you for holding such a nice contest.

      in1

      3 5 5
      3 4
      2 1 0
      4 2 1
      5 4 2
      

      out1

      1.666667
      

      in2

      2 5 5
      5 0
      1 0 0
      2 4 0
      

      out2

      5.000000
      

      in3

      3 4 4
      2 3
      2 2 2
      4 1 1
      5 0 0
      

      out3

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

        I've just started investigating your tests, and in each of them there is a point with y = 0, while it's forbidden in the problem. As far as I remember, it's essential for the solution.

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

          Oh,I didn't see the data range clearly.I'm so sorry for bothering you.

          Then it turns out that most of the AC codes are correct but only a few have problems.

          in

          3 5 5
          3 2
          2 3 3
          4 3 2
          6 1 4
          

          out

          0.473684
          

          I'm trying to find out why it works.

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

why am i getting wa on test 36 solution link