fcspartakm's blog

By fcspartakm, 4 years ago, translation, In English,

557A — Ilya and Diplomas

This problem can be solved in the different ways. We consider one of them — parsing cases.

If max1 + min2 + min3 ≤ n then the optimal solution is (n - min2 - min3, min2, min3).

Else if max1 + max2 + min3 ≤ n then the optimal solution is (max1, n - max1 - min3, min3).

Else the optimal solution is (max1, max2, n - max1 - max2).

This solution is correct because of statement. It is guaranteed that min1 + min2 + min3 ≤ n ≤ max1 + max2 + max3.

Asymptotic behavior of this solution — O(1).

557B — Pasha and Tea

This problem can be solved in different ways too. We consider the simplest solution whici fits in the given restrictions.

At first we sort all cups in non-decreasing order of their volumes. Due to reasons of greedy it is correct thatsorted cups with numbers from 1 to n will be given to girls and cups with numbers from n + 1 to 2 * n will be given to boys.

Now we need to use binary search and iterate on volume of tea which will be poured for every girl. Let on current iteration (lf + rg) / 2 = mid. Then if for i from 1 to n it is correct that mid ≤ ai and for i from n + 1 to 2 * n it is correct that 2 * mid ≤ ai then we need to make lf = mid. Else we need to make rg = mid.

Asymptotic behavior of this solution — O(n * log(n)) where n — count of cups.

557C — Arthur and Table

This problem can be solved as follows. At first we need to sort all legs in non-descending order of their length. Also we need to use array cnt[].

Let iterate on length of legs (which will stand table) from the least. Let this lenght is equals to maxlen. Count of units of energy which we need for this we will store in variable cur.

Obviously that we must unscrew all legs with lenght more than maxlen. For calculate count of units of energy for doing it we can use array with suffix sums, for exapmle. Then we add this value to cur.

If count of legs with length maxlen is not strictly greater than the number of the remaining legs then we need to unscrew some count of legs with length less than maxlen. For this we can use array cnt[]. In cnt[i] we will store count of legs with difficulty of unscrew equals to i. In this array will store information about legs which already viewed.

We will iterate on difficulty of unscrew from one and unscrew legs with this difficulties (and add this difficulties to variable cur) while count of legs with length maxlen will not be strictly greater than the number of the remaining legs.

When it happens we need to update answer with variable cur.

Asymptotic behavior of this solution — O(n * d), where n — count of legs and d — difference between maximal and minimal units of energy which needed to unscrew some legs.

557D — Vitaliy and Cycle

To solve this problem we can use dfs which will check every connected component of graph on bipartite. It is clearly that count of edges which we need to add in graph to get the odd cycle is no more than three.

Answer to this problem is three if count of edges in graph is zero. Then the number of ways to add three edges in graph to make odd cycle is equals to n * (n - 1) * (n - 2) / 6 where n — count of vertices in graph.

Answer to this problem is two if there is no connected component with number of vertices more than two. Then the number of ways to add two edges in graph to make odd cycle is equals to m * (n - 2) where m — number of edges in graph.

Now we have one case when there is at least one connected component with number of vertices more than two. Now we need to use dfs and try to split every component in two part. If for some component we can't do it that means that graph already has odd cycle and we need to print "0 1" and we can now finish our algorithm.

If all connected components in graph are bipartite then we need to iterate on them. Let cnt1 is the count of vertices in one part of current component and cnt2 — count of vertices in the other part. If number of vertices in this component more than two we need to add to answer cnt1 * (cnt1 - 1) / 2 and cnt2 * (cnt2 - 1) / 2.

Asymptotic behavior of this solution — O(n + m), where n — number of vertices in graph and m — number of edges.

557E — Anya and Half-palindrome

This problem can be solved with help of dynamic programming.

At first we calculate matrix good[][]. In good[i][j] we put true, if substring from position i to position j half-palindrome. Else we put in good[i][j]false. We can do it with iterating on "middle" of half-palindrome and expanding it to the left and to the right. There are 4 cases of "middle" but we omit it because they are simple enough.

Now we need to use Trie and we will put in it suffixes of given string. Also we will store array cnt[]. In cnt[v] we will store number of half-palindromes which ends in vertex v of our Trie. Let now we put in tree suffix which starts in position i, current symbol of string which we put is in position j and we go in vertex v of out Trie. Then if good[i][j] = true we add one to cnt[v].

Now with help of dfs let calculate for every vertex sum[v] — sum of numbers which stored in array cnt[] for vertex v and for vertices in all subtrees of vertex v.

It is left only to restore answer. Start from root of our Trie. We will store answer in variable ans. In variable k store number of required substring. Let now we in vertex v, by letter 'a' we can go in vertex toa and by letter 'b' — in vertex tob.

Then if sum[toa] ≤ k we make ans +  = 'a' and go in vertex toa of our Trie. Else we need to make as follows: k = sum[toa], ans +  = 'b' and go in vertex tob of our Trie.

When k will be  ≤ 0 print resulting string ans and finish algorithm.

Asymptotic behavior of this solution — O(szalph * n2) where szalph — size of input alphabet (in this problem it equals to two) and n — length of given string.

 
 
 
 
  • Vote: I like it
  • +86
  • Vote: I do not like it

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

You have some Russian (I guess) in "557C — Arthur and Table" 's description.

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

Taking min of 3 values sounds easier than doing bin.search in B:)

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

    please explain :(

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

      If you give one girl X, then you need n * X for all girls and 2 * n * X for all boys. This means that X <  = W / (3 * n), otherwise you'll have not enough water.

      You can't give one girl more than ar0, where ar is sorted array from input (because otherwise there will be some tea cup which is too small to give it to some girl).

      You can't give one girl more than arn / 2, because this means that you'll have less than n valid tea cups for boys.

      So you should simply pick answer according to these 3 restrictions.

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

        Thank you, I understand, I actually did not see that "Pasha pours the same amount of water to each girl"... I thought we could pour any amount of water to any girl :(

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

        Hmmm ... I did exactly that (used fast I/O , sorted using the std::sort in C++ (O(nlog n)) and then checked the conditions) yet got TLE .... The time limit could have been a little relaxed considering it is Div 2 ...

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

          I used same as you and got AC!! seems like there's other problem.

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

          I don't know why you got TLE :( but you are using significantly more memory than necessary, perhaps that made some things slow?

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

            Did you use vector<<double>? I got that TLE when using that too. Changed vector <int> and it worked.

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

          You were trying to input 2*N values into array of size N. AC: 11884732

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

            Yes I realised my mistake as well thanks !! Incorrect Array size is the dumbest reason for not getting Accepted ... xD

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

          Due to small array, buffer overflow may have occurred leading to overwriting of value of k and/or i in the For loop. So the for loop may never have exited or taken too long as value of arr[i] can be 10^9 (which gets written into k). Hope this helps :)

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

          cin, cout gives TLE!

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

        I had also done the same but had taken double data type to deal with decimal numbers. Output 1.06798e+008 Answer 106798500.0000000000 Checker Log wrong answer 1st numbers differ — expected: '106798500.0000000', found: '106798000.0000000', error = '0.0000047' How to reduce this error below 10^6 ?

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

          use this to print: cout << fixed << setprecision(10) << double_value << endl;

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

        We can even do it more simplified as let say g=a[1] and b=a[n+1] (after sorting 1 based index) then just have 2 conditions if tc = (b*0.5*n+b*n) --> b*0.5 maximum girl cup can have condition being b*0.5 <=g if not so then directly (g*n+2*g*n) is the answer. for case when ans>w take ans=w. that's it :)

        Here's my AC code — http://ideone.com/1POnoF

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

        i dint get the third condition ...can u plz reexplain the third part

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

          As we know that 0 to n-1 cup for girls and n to 2*n — 1 for boys. And it's also given that each boy should get two times water than each girl so if you give one girl more than ar[n](or first position of boy) / 2.It violate given constraint.my Solution

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

        Great insight, as always!

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

      let say you're going to pour x mill in each girls cup

      so x <= min{Capacities of girl cups} and 2*x <= min{Capacities of boy cups} --> x <= min{Capacities of boy cups}/2

      also, total amount of liquid poured is less than W so, x*n+2x*n = 3x*n <= W --> x<=(W/3n)

      Now we distributed n lowest capacity cups to girls and remaining to boys

      So x is equal to min{(W/3n),min{Capacities of girl cups}, min{Capacities of boy cups}/2 }

      and ans is 3*n*x

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

      Here is a two-liner (plus rading input and stuff) 11869212, who does exactly this.

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

      waht?qasdfghjkl;

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

wow what a quick editorial compared to the last one :) some statements (in problem C editorial) is still in russian..

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

    quick, but not so good in my opinion. I still don't understand the solution to problem C. How am I supposed to find the sum of energies needed for unscrewing the legs of length smaller then the max.

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

      My solution: - Sort based on height.
      - Iterate through the different heights (Consider the ith height as the maximum height)
      - This means you have to cut all legs that have length more than i (Use cumulative sum to find that).
      - Say the number of legs of length i is k
      - You have to leave exactly k-1 legs of height < i. The k-1 legs you leave should have the maximal energies => You have to choose k-1 maximum energy legs whose length are less than i and cut the rest.
      - For this I used a map (With a little bit of pre-processing). Iterate from 200 to 0 and while count < k-1.
      - While iterating, if there exists a leg of height < i and if count > k-1, decrease count. Else break
      - Use cumulative sum to find total energy you have to spend in order to have the ith length as maximum.
      - View my submission for further details:

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

Can someone please explain C in more details?

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

    Basically you have to ensure that in remaining legs, frequency of the maximum element is greater than half of number of remaining legs.

    We can do this by first choosing the value of maximum element(of remaining legs ). In order to ensure that this is indeed the maximum, we remove all the legs whose length is greater than this value.

    After that,we also have to ensure that frequency of the maximum element is greater than half of number of remaining legs. To do this, we remove appropriate number of legs whose length is less than this decided value.

    For a given choice of value of maximum element, we can calculate the energy in O(200) by just maintaining the frequency of energy required to remove the legs.

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

      Can u explain how u did this "To do this, we remove appropriate number of legs whose length is less than this decided value." You have to remove weight of ( remaining elements — (no of elements of current leg)/2 — 1 ) elements and these elements should be min possible.

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

        Keep a hash array of energies. So,delete from it the minimum ones. Now after you are done for length 'l',remove all the energies of that value from the hash array(I mean decrement). I kept a list of all energies belonging to a length. You can refer this code.Its sort of documented.

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

          can you please add some more comment in your code for more understanding like what is x.what does this(Removing the maximum leg--check for some other possibility) imply. what are you doing in following lines of code for(j=1;j<210;j++) { if(h2[j]>=r) { temp2+=r*j; break; } else { temp2+=h2[j]*j; r-=h2[j]; } } ans=min(ans,temp2); //~ cout<<"Length "<<i<<" b[i] "<<b[i]<<" remove "<<r<<" Energy "<<temp2<<endl; n-=b[i];

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

            Basically the idea is that whenever you consider length 'l' to be the length of table,then you will have to remove all legs of higher length. That is what I am doing there,removing from my hash table,all energy values of higher lengths. And x & r are just variables. x means if I consider 'l' to be the highest length I will have to keep 2*l -1 legs and remove (r)=n-(2*l -1). Thats the blueprint :) Hope it helps!!

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

        asdfasd

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

      Very nice explanation friend!! Missed that O(d) thing, just now got it accepted by keeping a hash of energy values after reading your comment. Good work!!

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

quickest editorial ever

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

Problem statement was not very good. :(

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

so the array size is the silliest mistake in history, Why the hell did I get TLE instead of RTE for this code !!

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

    Same problem there, had to add Fast IO to get AC.

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

      I got TLE with fast IO too

      see the link, I edited it

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

        Try cin/cout with ios:ios_base::sync_with_stdio(false) and cin.tie(NULL); You should get AC.

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

    The array is on the stack, so there's a lot of room to read/write values before you get runtime errors. If N is over 50000, you will overwrite whichever values come after your array (like i), which causes your program to get stuck in the for loop.

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

F*king precision error!!

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

This is how I solved D.
1st thing to notice was that only 3 edges are sufficient to create an odd cycle.
Case 1: Edges needed 0. Just check if a graph (every component) is bipartite or not. If it is not than the graph contains odd cycle. Ans is (0, 1).
Case 2: Edges needed 1. For this case color every component with 2 colors. Lets say we use A, B to color the nodes. If two nodes have same color than we can add edge between them to create an odd cycle. So ans for this case is (1, naC2 + nbC2) where na is the no.of nodes with color A and nb is the no of nodes with color B. We need to sum this for all components.
Case 3: Edges needed 2. For this case do dfs to count no of components of size 2 and size 1. Ans for this case is (2, 4 * two_cntC2 + two_cnt * (n — 2 * two_cnt)). Every two components of size 2 gives 4 different ways. We also add the ans for the case where individual node components are present which is basically equal to two_cnt * (n — 2 * two_cnt).
Case 4: Edges needed 3. That is every node is disjoint. Ans is (3, nC3).

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

    Edit: Got it! Great question! :D

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

    How do we know that we need edges 1/2/3/0 ? Please see this , i could solve only for the no. of ways( hope it is correct ).

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

      If graph already contains an odd cycle than we don't need to add any edge i.e this is the case where needed edges = 0.
      If any component of graph contains more than 2 nodes than we can add 1 edge to create a cycle (this component will not have any odd cycle as we are already considering that case separately).
      If the max size of any component in graph is 2 than we need 2 edges to create a cycle. comp1 = A-B, comp2 = C-D to connect these and create odd cycle we need 2 edges.
      If graph contains all the nodes separately, i.e max size of any component is 1 than we need 3 edges to create an odd cycle.
      I hope it clears your doubt. For reference here is my solution. 11865575

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

        Thanks for the reply :) I have a doubt. Won't above assumptions fail if we have suppose 3 connected components and 1st is bipartite 2nd is not bipartite and third is a simple cycle?

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

          If second component is not bipartite than it contains an odd cycle for which we have already checked. :)

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

    please ignore. made a mistake.

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

Second problem was wrong because of a single word; :(

It must have been,

cout<<fixed<<answer; instead of cout<<answer;

used it after contest and got accepted. :(

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

    Does anyone know what parameters to use with printf ? Not sure if I understand the "fixed" option in cout.

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

      printf("%.6lf",answer);

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

        thank you for answering. Apparently, it also can be: printf("%.6f",res); I just thought for the 1st pretest it cant be "3.000000", but a simple "3", but it's not the case.

»
4 years ago, # |
Rev. 3   Vote: I like it -20 Vote: I do not like it

This is just wrong, my submission for B during the contest 11860848

And after the contest the same code along with fast IO 11867502

I spent about an hour trying to debug my solution when there was nothing wrong. Isn't CF supposed to be non-IO centric. This is unfair, Binary search timing out due to Fast IO.

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

    How else are they supposed to give problems with 100000 numbers as input?

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

      Some warning, the very least. Not all of us are reds and seem to have that in mind during a contest ( Sarcasm unintended).

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

        Always use fast input from now on and you'll never experience similar problems again.

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

          Yup, I had some problems on SPOJ without Fast I/O, but then started using it everywhere. Even though my friends disapprove (for no apparent reason), I actually find it more convenient taking input just by writing 2 letters and the variable name :D

          Just add Fast I/O to your standard template and you can focus on the problem!

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

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

    That's not Fast IO. Is just normal IO.

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

Can anyone explain why this code 11861412 give me WA on test case 8 [problem B] ? and how can I repair it?

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

    Maybe because you just checked if you could put "2 * qua" for boys. You didn't check if you could put "qua" for girls... That's the same mistake I've made... You have to check it because it could happen that you can put 2 * qua for boys, but the smallest cup doesn't support qua ml of water.

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

In the editorial for problem A how is (n-min2-min3,min2,min3) the optimal solution when max1+min2+min3 < n?

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

Problem E can be solved in O(n2) time. You can read my solution (11862688) if you interested in. (I've used that alphabet size is equal to 2, but it is easy to fix it)

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

    The original solution can do o(n^2), since only n nodes will have more than one child.

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

Have you any time to debug my Error. Why my code gives wrong ans ? (http://codeforces.com/contest/557/submission/11868836)

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

Hash can be also used to find if a substring from i to j is half palindrome or not.

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

Well, I solved problem C a little differently.

First we sort the legs by their lengths in ascending order (the energy values don't matter). Then we split the sorted list into blocks, where the legs in the same block have the same length.

length: 1 1  2 2  6 6 6
energy: 5 5  4 8  2 3 3

After that we iterate over every block. In iteration i, we try to find the answer when the legs in block i are the longest remaining.

In iteration i, obviously, all legs in block i must be kept in order to find the optimal answer. And we must remove all legs in blocks from i + 1 to block-count (since legs in block i are the longest remaining), and keep at most block[i].size - 1 legs in blocks from 1 to i — 1 (to keep the table stable). Therefore the answer equals to
total energy of block (i + 1)~block_count + total energy of block 1~(i - 1)total energy of the (block[i].size - 1) largest elements in block 1~(i - 1).

For the first and second part we can either use partial sums or calculate while iterating. For the third part, we can use a std::multiset to store all previous legs' energy values. For any k, the k largest elements can be accessed by just iterating k times in the multiset. Asymptotic time complexity is... , I think?

My code (written rapidly during the contest and may not be so elegant): 11859771

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

    Shouldn't this be subtracted total energy of the (block[i].size — 1) smallest energy elements in block 1~(i — 1) from total energy of block 1~(i — 1).

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

      No, u r right. We should subtract total energy of block 1~(i — 1) — total energy of the (block[i].size — 1) largest elements in block 1~(i — 1)

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

    Hi cyand1317, I think I used the same method as you with the difference that I used a priority queue to get the legs of highest energies from the legs of smaller sizes.

    But for some reason I'm getting WA in case 8 and I cannot check why because it's very big. I get the correct result with all the cases where n < 30.

    Could you please take a look at my code?

    http://codeforces.com/contest/557/submission/11870567

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

      Hello. Glad that I can help. I'm taking a look at your code and here's what I've found so far.

      There is a potential crash in this code. Try using a test case with n = 5 and length values 1 8 8 8 8. Whoa!

      This is because when your program scans the second block (with length = 8 and blocksize = 4), it tries to poll the blocksize - 1 = 3 largest elements in the previous blocks, which only has one element. Then PriorityQueue.poll() returns null and causes the crash.

      However, this code still doesn't give correct answers after I fixed this bug (line #64, 11875986). I'll keep trying! (I ran into similar situations lots of times before and I'd really like to find an efficient way to get out of them :P)

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

    I am using a similar approach but i fail to comprehend why it is giving WA for the first test case while it is running fine on my system. Please check my comment for the approach. http://codeforces.com/blog/entry/18943?#comment-239449

    My submission: 11875338

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

      Rivx has explained why this code doesn't work the way you want. But after correcting these mistakes, it still gives incorrect answers. Perhaps the algorithm isn't that correct. I'll try to think about some ways to fix it.

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

    Yes, it should be O(nlogn) as we access at max sum(k) elements in the multset and sum(k) is n.

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

      Oh, yes, I didn't realize that! A clear explanation. Thanks :)

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

I have changed the type of array c ( 11867935 ) to long long and the code gets Accepted (11868444)! Can anyone explain why?

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

    Reading double takes more time than long long (about twice I guess), for decimal points and many other things (such as expressions like 3.14e10) need to be checked. And n is relatively large.

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

I'm wondering why this submission got TLE for problem B. I believe the complexity of this solution is also .

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

    Taking double input is very time-consuming, and hence you need to use Fast Input/Output. Also, your code will get WA on test 32 if you do not use "cout.precision(x)", as cout as low precision by default. (Here x is greater than 6)

    Changing to printf and scanf, here is your AC submission : http://codeforces.com/contest/557/submission/11870036

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

    You're reading data too slow. Try to use scanf() instead of cin>>.

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

      iostream is as fast (or even faster) than stdio, but by default it has special buffering enabled that makes sure that you don't get unexpected results when you use both cin and scanf. You can disable it by adding std::ios_base::sync_with_stdio(false) as the first line of your program (before any input/output operations).

      Also, if you alternate between cin and cout, it will flush output before each input operation (which is needed when cin and cout refer to the console, so the user sees the prompt before having to enter something), which can lead to very slow IO (common issue in problems where you need to answer lots of queries). This can be disabled with std::cin.tie(nullptr).

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

Please improve the English translation

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

Can someone, please, tell me what's wrong with my code for C? It gives correct answer with all the small cases so I cannot debug it. At least some test case that won't pass with it.

I wrote a lot of comments to make it easy to understand: http://codeforces.com/contest/557/submission/11870567

The idea is basically the same as the author:

  1. Precalculate cost of removing all legs of larger size
  2. Iterate over each leg size, removing larger ones in O(1)
  3. Keep a Priority Queue with the legs of lower size to obtain the largest ones in lg(n)
  4. Obtain from the priority queue a number of legs strictly lower than the number of legs of the current size (which won't be deleted)
  5. Minimum Energy Used = min(currentMin, energy of larger + energy of lower — energy of non-removed legs

Thank you very much in advance!

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

    What happens if there aren't enough smaller legs? You loop from 1 to count-1, but the queue might not have enough elements in it. It crashes on the following test: 6 1 1 2 2 2 2 1 1 1 1 1 1

    It still doesn't pass test #8 with this fixed, though.

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

      Thanks for checking. Yes, I noticed that just after posting but the corrected code below didn't pass 8 as you say :(

      http://codeforces.com/contest/557/submission/11870823

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

      I cannot find a single case that doesn't work with my code. I'm running many random cases against Accepted codes without any luck :(

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

      Finally, I found the problem with my code. It didn't have to do with the algorithm but with Java!

      The problem was in the way that Java compares Integer objects:

      Incorrect: if (legs[i].first != legs[i + 1].first) {

      Correct: if (legs[i].first.intValue() != legs[i + 1].first.intValue())

      Explanation: http://stackoverflow.com/a/1514919

      AC code (almost the same): http://codeforces.com/contest/557/submission/11873179

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

        Writing your own class with two ints is faster, safer and more readable.

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

          I agree, but it's probably not faster to code in a competition. My pair class is ready to sort by the first element and then by the second (the latter not needed in this case).

          I guess it depends on how much I would use direct value comparison and how much coding time I'm expencting to save by not writing the class and comparator on the go.

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

Who can explain me why the compiler reterning wrong answer to this example: 500*3*71199.
This will be 106798500, but it says that my programm reterns 106799000 even with this if (n == 71199) cout << 500.0*71199.0*3.0 << endl;
The submission: 11870868

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

    The correct answer is: 106798500

    Your program print: 1.06799e+008 what equal to 106799000 So you have less than 10^6 precision. To have ACC you must write cout << fixed << setprecision(10) << answer << endl;

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

can you please provide codes ?

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

In second question B --> we can do without binary search ie just be greedy :)

We can even do it more simplified as let say g=a[1] and b=a[n+1] (after sorting 1 based index) then just have 2 conditions if tc = (b*0.5*n+b*n) --> b*0.5 maximum girl cup can have condition being b*0.5 <=g if not so then directly (g*n+2*g*n) is the answer. for case when ans>w take ans=w. that's it :) Here's my AC code — http://ideone.com/1POnoF

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

http://paste.ubuntu.com/11801550/

I'm getting TLE in E problem. i have a matrix named pal. pal[i][j] = 1 means substring that starting from i and length is j is half palindrom.

i calculate matrix with complexity n^2 and then i find what string is.

i do that with three vector. i wont explain more. i think code is clear.

but the problem is why i am getting TLE ? can anyone tell ?

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

I solved C in O (N log N ). Here is the algo :

1) In a multi set (or any bst like structure) , store all the legs with their energies as < length, energy >, call this as M. Let total weight of all legs be TOT.

2) For all distinct lengths in this map , assume that the table is going to be built with this length as maximum length, call this length L. Let there be total of CNT number of these legs with length L. Now what you need to find is CNT-1 legs with max energy and length less than L. This can be done using a multiset for energies — once you have crossed a length, you insert all the different energies for this length into it, call this multi set as W.

3) Find the net energy value of all legs of this table = ET and update answer with ans = min(ans,TOT-ET).

Complexity analysis : 1) Creation of M = O (N log N)
2) Finding CNT for all distinct lengths — O(N)
3) Creation of W = O(N log N)
4) Selecting CNT — 1 legs of max weight from W = O (N)
Because worst case, we can have sqrt N distinct lengths occuring sqrt N times and so we will have to go through sqrt N max energy legs for each of the sqrt n lengths = O(sqrt n * sqrt n) = O(n)

Soln link — http://codeforces.com/contest/557/submission/11872727
PS : During contest, in the last while loop, I wrote "it1" as "it" and unfortunately "it" was also a variable in that scope so that caused WA on some pretest. Silly typo :\

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

I am new here. What should I do if I cant understand the solutions even after reading the editorials? Any tips?

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

    You can take a look at others' code, which you can find by clicking the numbers like 'x2917' on the 'PROBLEMS' page. If you don't know an algorithm mentioned in the editorial, search for it on the Internet. If these still don't help, directly commenting under the editorial asking for help is another way. When doing this, details such as which problem and where you didn't understand (or even better, which sentence) are necessary.

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

fcspartakm, I understand both solutions, greedy and bs, but I always had a doubt in binary search with limits of type double. Can you give any tips, did not submit to the binary search but understood perfectly, the only question is in the loop breaks.
For example: l=min of search, r=max of search, EPS=1e-6 how shall I compare them to complete the search? so? l-r<EPS
I wanted to know, as they do this test? or rather, what better way to do it?

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

    r-l<EPS since r>l

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

    Don't compare doubles, use fixed number of iterations. I believe 64 should be enough in all cases.

    for (int it = 0; it < 64; ++it) {
      double mid = (l + r) / 2;
      if (...) l = mid; else r = mid;
    }
    

    Also, in this particular problem, answer can be only integer or (integer + 0.5). So you can multiply everything by 2 and get rid of floating-point numbers at all.

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

Thanks for the interesting problems :)

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

I am curious of the solution regarding 557C. I've solved it in my own way, but my code exceeds the limited execution time. I think it's something to do with using "cnt[]" and "cur[]" as the editorial says. However, I cannot grasp the usage of cnt[] and cur[]. Can someone please elaborate on this?

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

For Problem C Can anyone please let me know why i am getting WA for the first test case while the code is running fine on my system atleast for the first three cases.11875338

I am maintaining a set for the table lengths'(st) and another set to store the energy levels for a particular length(pq[]). The array cnt[] stores the number of occurrences for a particular length.

The loop basically tests for three possibilities.

temp=n
while(temp>2){
it=st.end();
if(cnt[*it]>temp/2)   //temp is used to store the current number of legs
   print ans

else if(cnt[*it]==temp/2)
   //find a length<*it with the minimum most value for energy to be incremented to answer.
   //let this be denoted by len
   print ans+len

else
   //increment the ans with all the energy levels that correspond to the current length
   temp-=cnt[*it]; //decrement the current list of legs
   it2=pq[*it].begin()
   while(it2!=pq[*it2.end())
      ans+=*it2;
      it2++;
st.erase(it);
}
  
   
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ->set::iterator it,
    ->pq[*it]
    ->cnt[*it] Are they not contradicting? I don't know but can you use iterators of different types invariably?

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

      *it dereferences the iterator, so it's simply an int. However, st.end() is NOT the iterator for the last element — it actually points beyond the end of the set, so you can't dereference it. You need to decrement it by one (--st.end()). In other containers like a vector you can use back(), but there is no such method in a set.

      However, that block isn't reached in the first test case anyway. You didn't initialize mini, so if it starts out as zero in GCC, you will get zero as your answer. In VS it starts out as -858993460, which is even worse.

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

After I read the editorial, problem A is much easier than I think :((

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

Thanks for the editorial. First problem could also be solved with complexity o(max(max1-min1,max2-min2,max3-min3)). My friend submitted using this method and got accepted. But since we can solve it with o(1) like in the editorial I think that solution is kinda slow.

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

Now we need to use dfs and try to split every component in two part

Can someone explain this part of problem D?

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

    Use DFS to try to color the graph in two colors (so that no edge connects two vertices of the same color). That is, initially the graph is uncolored, and you do something like this:

    void dfs(int v, int c) {
      color[v] = c;
      for (int u : edges[v]) {
        if (color[u] < 0) {
          dfs(u, 1 - c);
        } else if (color[u] == c) {
          impossible = true;
        }
      }
    }
    // ...
    for (int i = 0; i < n; ++i) {
      if (!color[i]) {
        dfs(i, 0);
      }
    }
    
  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    he want to say that if component isnt bipartite (means we cant split it), it already has odd cycle.

    read what bipartite graph is. http://www.geeksforgeeks.org/bipartite-graph/

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

In 557B — Pasha and Tea party what is "lf" and "rg"?

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

    Binary search boundaries (the range in which we know the answer should be). lf is initially 0, and rg is initially w. On every iteration, we split the range into two halves, and choose which one of them is correct. Eventually the range will become small enough that we can print the answer.

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

      But when would the loop terminate ?

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

      I implemented following: lf=0 rg=w/3*n While(lf<rf) { mid=(lf+rg)/2; if(mid<= a[0] && mid*2 <= a[n]) lf=mid Else rg=mid }

      wheree a is sorted array of cup capacity And this loop doesn't terminate.

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

        Always use fixed number of iterations in binary search on doubles. I usually use 150-200 iterations and everything works.

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

          Does it work for all cases irrespective of size of input? BTW is my implementation correct apart from correction you suggested?

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

            If you can represent left and right bounds using doubles — than the answer is yes, but I don't remember the reasoning of this. Maybe someone can elaborate this?

            rg=w/(3*n) — you should use parenthesis here

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

              I tried and it worked....thank you so much

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

          150-200 is a way too much, considering doubles only have 52 significant bits. Unless the interval converges to zero, the last 100-150 iterations will do nothing.

          In fact, you can do while (x != y) and it will do 50-60 iterations in most cases — except when the answer is zero, in which case it can do about a 1000 iterations. Of course, you shouldn't do that because you're likely to run into the same problem as with int binsearch — when x and y are the closest possible numbers, (x+y)/2 will be equal to either x or y, and if you guess "incorrectly", you will get an infinite loop. You could fix it by using std::nextafter (i.e. if you know that the answer for m is no, then technically you need to set y to the number just below m, or std::nextafter(m, l)), but that's not pretty.

          Not to mention that this problem doesn't need binary search anyway :(

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

Why doesn't the tutorial appear with the problem statements? Would I always have to navigate to the blog to see the editorial? How come some contests have tutorials appearing with each problem statement?

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

    Not sure what you mean, after each contest the blog entry is updated with a link to the editorial. You can see all entries for the recent contests on the front page.

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

    There is "→Contest materials" tab at the right bottom corner of contest interface. Usually there is a link to tutorial(if anyone added it)

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

For 557C, we can use the same idea to find the solution without too much thing to compute.

The idea is (reiterating author's approach): Let's say we want to keep legs with length k. All legs length greater than k must be removed (otherwise k is not the maximum), the remaining is to make sure removal of legs length less than k requires minimal energy.

Observation: If there are P legs whose lengths are less than k, and there are Q legs with length k. You need to remove at least P - Q + 1 legs whose lengths are less than k to make the table stable.

Observation: By above, you need to keep at most Q - 1 legs whose lengths are less than k to make the table stable. Otherwise, there are at least Q non k-legs with Q k-legs, and k-legs is obviously not the majority. Table is not stable.

Observation: Remove legs with minimal energy is equivalent to keep legs with maximal energy.

So, you need to compute two things: total energy to remove (now means keep) k-legs, number of k-legs. Enumerate all possible maximal k, get the keep energy for k-legs, plus get the sum of the largest Q - 1 energies of legs whose length is less than k. The way to do it is similar to the O(nd) approach described by author, but we take the exact opposite values. Find the maximum values among all choices of k, get the answer by total energy — this max energy.

Doing so does not require suffix sum.

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

I am getting WA on testcase 8. someone please help. I am sorting the list according to their lengths and then i m considering each length to be the maxlen. i am making an array which is going to store the index and frequency of each leg of differrent length. http://codeforces.com/contest/557/submission/11892251 here is my code. someone plz help

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

We check at a node if sum[toa] <= k.

Let us say sum[toa] is less than or equal to k. Then we go to node toa, now, for all nodes sum[toa from new node] will also always be less than k.

So, in such a case k will never become less than or equal to zero.

The how will the algorithm terminate?

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

    Typo, it should be sum[toa] >= k

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is one more missing thing. Once we reach a particular node $$$v$$$ while constructing the answer, we must also subtract $$$cnt[v]$$$ from $$$k$$$ to account for half-palindromes ending at the node $$$v$$$. So, if $$$sum[to_a] \ge k$$$, we move towards $$$to_a$$$ and also update $$$k$$$ as $$$ k$$$ $$$-= cnt[to_a]$$$. Otherwise, we move towards $$$to_b$$$ and update $$$k$$$ as $$$k$$$ $$$-= (sum[to_a] + cnt[to_b])$$$

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

I found the statement of the Problem A to be not clear. I could not understand the fact that if we already have max possible A diplomas, then try finding max possible B diplomas and further max possible C diplomas.

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

    My solution is a bit different from the author' solution:

    11892821

    Call t1, t2, t3 is the number of diplomas in first, second and third degree in the optimal answer. We know that t1+t2+t3 = n.

    Our goal is to maximize t1 first, then maximize t2. So we will first make t1 as large as possible. We knew that 't1 <= max1'. However, we'll need to take care about the fact that t2 >= min2 and t3 >= min3, too. So, we'll have n-t1 = t2+t3 >= min2+min3, which mean t1 <= n-min2-min3. Finally, we'll have t1 = min(max1, n-min2-min3).

    At this point, we'll have n := n-t1 diplomas left. Now, we will take do the similar thing again, make t2 as large as possible. We know that t2 <= max2 and t3 >= min3 <=> n-t2 >= min3 <=> t2 <= n-min3. So we'll have t2 = min(max2, n-min3).

    We now know the value of t1 and t2, so we also get the value of t3, which equal n-t1-t2.

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

For Problem D of the contest I have implemented the idea of DFS mentioned in the Editorial but i am still getting WA on the test 31. http://codeforces.com/contest/557/submission/11901124 I would be grateful if anyone could point out my mistake and point me in the right direction.

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

    sol=((white-1)*black+(white)*(black-1))/2;

    I think this line contains a mistake. A path between a black and white vertices is of odd length (a cycle is of even length), is it not?

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

I have done a write up for C. I had some trouble understanding how to solve it, so I tried to be as specific as possible. I hope this is useful for other people as well: http://wp.me/p2MUx0-8t

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

To solve B, I just needed to sort them and write only 2 lines and it's done, no need to iterate on any thing, the answer pops right up. My solution: 11927301 Complexity: O(n.log(n)) for the sorting

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

I was tricked by myself when I attempted to solve D.

The definition of odd cycle is obvious: Any graph that is not bi-colorable iff it has odd cycle (proof omitted). So if the graph has odd cycle it's done, we don't need to add any edge and this is the only way to achieve minimum (thus 0 1). Note that bicolorable graph is bipartite.

The solution remains to categorize answers for different class of bipartite graph. Note that you need at most 3 edges to form an odd cycle in any cases, so just think about when you need to answer 1, 2, and 3.

Case 1: when minimum = 3. It means you need to form a triangle by picking three vertices. This also means that there are no edges, thus maximum vertex degree = 0. In this case, answer is to pick any three vertices, which is .

Case 2: when minimum = 2. It means that no vertex has at least two edges (otherwise minimum = 1 by joining two vertices from the two edges to form a triangle). Which implies that maximum vertex degree = 1. To form a triangle, we must use any of such edge (u, v) and find other vertex w and use two edges to form a triangle. Note that since maximum degree = 1, all m edges are the required edge. So the answer is m × (n - 2) (for each edge, pick other vertices to form triangle).

Case 3: when minimum = 1. This means that maximum degree is at least 2. This is also where I got tricked. In this case, we don't just want to count number of ways to form triangle, since one can add an edge to form an odd cycle. Consider this: W-B-W-B-W, where W means a white vertex, B means a black vertex. One can add just on edge, that connects the first and the last W, to form an odd cycle with length 5. Given this, the answer is much simpler: notice that for any connected bipartite graph, connecting any two vertices of the same side breaks bipartite-ness, thus odd cycle exists. So the answer is simple: for each bipartite connected components, the answer for that component is the number of way to connect two vertices on the same side. Suppose the bipartite graph has U vertices on the left, V vertices on the right, the answer is .


Indeed, what if the problem is like: find the minimum number of edge added to form a triangle, and how many ways to do. When the graph is not bipartite, I think it requires matrix multiplication. If the graph is bipartite, the answer remains the same when the minimum edge added is 3 or 2. When minimum edge added is 1, I can't come up of anything that is faster than O(n2).

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

We can use dp for checking half-palindromes.

Suppose our good[][] array works correctly for substrings of length 1,2,3...i-1 Now we have to consider the substrings of length i and update the good[][] array.

It's obvious that good[i][j] = 1 if and only if,
- char at position i equals char at position j and
- (i+2 > j-2) or (dp[i+2][j-2] == 1)

Link

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

I think the solution of problem A is probably wrong.
Like for the first condition max1 + min2 + min3 ≤ n, which means n - min2 - min3 ≥ max1.
And it saids the optimal solution is (n - min2 - min3, min2, min3), which actually invalid.

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

    Yes, it seems the less and equal symbol should be replaced by large and equal symbol. Can author fcspartakm have it a look? :)

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

I have a O(N^2 + N^2 log N + N^2) solution for problem E.

Firstly, finding all the half-palindromes by O(N^2) brute-force. Then, sorting all the suffix by their indices with O(N log N) algorithm. In fact, it can be optimized by using suffix array algorithm, and this will come up with an totally O(N^2) algorithm for this problem. Finally, sweeping the suffixes for counting the k-th sub-string in O(N^2).

And this is not depended on the number of kinds of alphas in the string. :) I don't know if my solution is strictly right, so comments are welcome. 11894668

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

    "Sweeping the suffixes for counting the k-th sub-string in O(N^2)"-could you explain this part?

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

Can anyone, please, explain Problem E ?

With all due respect, the explanation offered in this editorial is not clear at all.

I understand the part where we determine which substrings are half-palindromes as I did myself but I don't get the part where I'd have to use a trie. I tried to use a trie by myself but I think it's O(n3) .

It would be really nice if someone explains the approach of this editorial!

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

How to solve C if 1 <  = di <  = 105?

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

    I don`t know how that collocation will be in English, but you can compression the coordinates. I think you understand me.(does it work?)

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

Can anybody point out as how to improve the Binary search I'm implementing. I'm getting WA for DIV 2-B. Here is my code Thanks !!

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

    ACed had to reduce the vale of "eps" further.

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

Problem C div2 i am getting WA on test 8, the problem is i can't see the test case because it's too long is my approach wrong ? http://codeforces.com/contest/557/submission/13112478

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

Can anybody give the the idea of Div 2 C, when the range of di can be anything and not just 1 ≤ di ≤ 200

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

    My approach have time complexity is O(N(logN)2), which not depend on value of di.

    First of all, I sort the array with depend in l[i]. Second, sort the array with depend on d[i]. Now for each leg, we know the ordinal of their energy units. For example, in test case 3, our sorted array (called a[]) and the ordinal of their energy units (called c[]):

    a[] = [1, 1, 2, 2, 3, 3]
    c[] = [5, 6, 3, 4, 1, 2]

    So we now, for the $i$-th leg, we have greedy approach: If we choose to use this leg, then we will use all of the legs that have the same value of length with this chosen leg. Call the number of legs that have the same length with i-th leg is k. The enery when we chose i-th leg is sum enery units of all the leg have greater length and sum of the i - (2k - 1) smallest enery units leg of which length is strictly smaller than i-th leg.

    Because all table must have more than a half legs of greatest length, so is we choose i-th leg is greatest length, the maximal numbers of legs that a table could have is 2k - 1 legs. To make i-th leg is the greatest length's leg, then we need to remove all the legs have greater length and take no more than k - 1 legs have smaller length. At the moment, we have i legs with have not greater than i leg, so greedily, we just need to remove i - (2k - 1) legs that have smallest enery units.

    Now, for each leg, we could easily use prefix sum to find sum of all the legs have greater length than our chosen leg's length. However, the harder problem is find the sum of i - (2k - 1) smallest leg's enery units. Remember about the array c[], which we store the ordinal number of the leg's enery units. Now, after attempt the i-th leg, we will knows that it exist the c[i]-th smallest enery units value.

    For example, when we check the 4-th leg (base on array a[]), we will have these valid enery units values [0, 0, 1, 1, 1, 1]. As we want to find sum of i - (2k - 1) = 4 - (2 * 2 - 1) = 1 smallest value, so we will find sum of 1-th smallest enery units, in this case is 3.

    Also notice that, the numbers of valid enery units values from 1 to j is always not less than the numbers of valid enery units values from 1 to i which i > j. So we could use binary seach to find the smaller number x that from 1 to x we can find i - (2k - 1) valid value. To do each of this operation in O(logN), we could use Fenwich or Segment Tree. After found the result x, our answer in case we use the i-th leg is sumLengthSmallestValidValue(1, x)+sumLength(i+1, n).

    In the other hand, to make sure that we just find the sum of the smallest enery units legs which have length strictly less than our chosen leg's length, after we check all the same length legs, then we update, not update for each leg (we could use stack or queue to solve that — if the i-th leg is diffence than the i - 1-th leg, than we update all the legs that stored in the queue now, other wise, if the i-th leg is same as the i - 1-th leg, push i to the queue).

    Here is my code which uses Segment tree: 23901663. So the time complexity is O(N(logN)2) due to using binary search on Segment tree for each leg. This is the first time I write the solution, so sorry for my bad idea's expression. Feel free for asking me any question, I will trying my best to explain :D.

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

In the guide of 557A, comparison symbols of the first two conditions seem wrong. '<=' should be replaced with '>=' i guess.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The editorial for the first problem is wrong and it is weird that no one has pointed it out.