fcspartakm's blog

By fcspartakm, history, 6 months ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +54
  • Vote: I do not like it  

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

In problem D (n + (n - 1) - sum) / 2

I think it should be (n + (n - 1) - p) / 2

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

    Can you explain me why this formula works?

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

      sorry, I do not understand how it works, I found this after reading other's code.

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

      Yes please. Someone explain D. or atleast how to come up with those ideas and the formulas.

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

        The solution for D is fairly simple to come up with.

        1) Observe that when n < 5, the answer is .

        2) Observe that when n + (n - 1) is of the form 9....9 the answer is 1.

        3) In all other cases, we need to iterate through the possible (i + j)'s that produce the maximum number of nines. So, say the maximum number of nines is x. Start at 9...9 (x times) and increment this to 1(9....9) (x times) 2(9....9) (x times) until we reach n + (n - 1). For each of these numbers we need to calculate how many pairs (i, j) sum up to them. Now, when the number is >= n + (n - 1), we need to add (number / 2) to our answer. This is because we can have: (number / 2) + (number / 2), (number / 2 + 1) + (number / 2 - 1) ...so on to sum up to the number. Otherwise if the number < n + (n - 1), we need to add (n - number / 2) to our answer. This is because we can have: (number / 2) + (number / 2), ..., n + (number - n).

        Here's my submission for reference http://codeforces.com/contest/899/submission/33348429

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

        It can be solved using digit DP. Submission Link Explanation

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

    It should be 1 + (n + (n-1) - p)/2

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

Pardon me for a stupid question.

In Div2B, the 13th test case is the following:

21 30 31 30 31 31 28 31 30 31 30 31 31 30 31 30 31 31 28 31 30 31

and correct output is "YES"

Doesn't this show two consecutive leap years? year 1: 31 28 31 30 31 30 31 31 30 31 30 31, next year: 31 28 31 30 31 ... this should not be possible right?

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

    A leap year has 29 days.

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

      Oh god. I can't believe I made this mistake D: So stupid of me.

      Thanks though!

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

        Look at all the people who failed problem B. They all did same mistake as you. It's because of the problem statement, January, 28 or 29 days in February (depending on whether the year is leap or not) , which gives an idea that correspondly leap has 28 days and not leap has 29 days.

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

I solved C by just making two set and giving element to the smaller sum set in a reverse sorted order.I don't know why this works though. Can anyone help me with proving this method's correctness or tell where it could fail?

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

    I am trying the same approach and in pretest 5 59998 its failing as i am putting 48950 twice. I am not sure why only that case failing :|

    EDIT: a lot of other cases are also failing. have to do something else,

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

      Try to do it in reverse order, so construct your sets starting with n, then n-1, and so on. This will give you a correct solution.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    1. A set of 4 numbers can always be divided into two sets so that their differences is 0. Take n, n-1, n-2, n-3. Set1 contains n, n-3 and Set2 contains n-1, n-2. When dividing a consecutive sequence, you can always start from the last, take a group of 4 consecutive integers, and start dividing like earlier.

    2. If you can't take a group of 4 consecutive integers, the sequences left might be: i) 1, which can be assigned to any set. ii) 1, 2 : where 1 can be assigned to one set and 2 can be assigned the other set. iii) 1, 2, 3: where 1 and 2 has to be assigned to one set and 3 has to be assigned to the other set.

    3. Your algorithm automatically takes care of the first step. When it assigns n to one set, and n-1 to another, then n-2 becomes assigned to the set containing n-1 and n-3 becomes assigned to the set containing n.

    4. Your algorithm also automatically takes care of the 2nd step. A quick thinking will reveal why.

    Hope you understood! :)

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

Can someone please explain solution to problem E. I don't understand the editorial.

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

A much easier solution for C : My solution link... 1. Just take the sum of the numbers= N*(N+1)/2.

  1. If sum is even, then logically you can divide it into two equal halves. Keep giving the largest numbers possible till you form half of the sum.

3.If sum is odd, then logically one group will have one more sum than other group(g2). Let G2 sum be x. Keep giving the largest numbers possible to form x

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

Can someone explain D? Why we are adding those numbers etc..

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

难得有一次cf这么适合Chinese。。。

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

    结果差点忘记比赛..晚了几十分钟

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

Easier way to solve problem C . The sum of the first N numbers is N * ( N + 1 ) / 2, let's call it tot.

If you have a number X less than or equal tot, it is possible to represent it as a sum of first N numbers. ( Iterate from N to 1, and subtract when possible), call that function represent(X). This is very well known.

Now .. if tot is even, we can obtain a difference of zero which we obtain by represent(tot/2). If tot is odd, we can obtain a difference of one which we obtain by represent(tot/2).

In even case, we get the best possible answer, in the odd case it's easy to see that the best we can obtain is a difference of one, and hence the algorithm is optimal.

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

Another way to solve F is keeping a treap for each character. However, it is overkill in my opinion. But if you have template ready to be copied and pasted, then it should be fastest solution.

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

    You are using this loop:

    for(set<int>::iterator re=ya.begin(); re!=ya.end(); re++)
        if((*(re)+i<48)&&(a[*(re)+i]!=j))
            ya.erase(re);
    

    As soon as you do ya.erase(re), the iterator re is invalidated (refer to the first line in heading Iterator validity), so you get unexpected behavior, i.e., you shouldn't use re anymore.

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

My solution to 899C - Dividing the numbers is the following:

We know that for every two consecutive numbers a and b, a-b = 1 if a > b and a-b = -1 if a < b. So if we take the rightmost two consecutive numbers a, b, a > b, and put them in separate groups, we have |group1-group2| = |a-b| = 1; now if we take the next two consecutive number c, d, with c < d, and put c in group1 and d in group2, then |group1-group2| = |(a+c)-(b+d)| = |(a-b)+(c-d)| = |1-1| = 0. If we greedily continue doing this strategy, we would compute two groups that their absolute difference of sums is minimum.

To compute the minimum absolute difference we can check in O(1) if we have a pair number of pairs (it means that every number has his pair in the strategy above) or not.

Code: http://codeforces.com/contest/899/submission/33345931

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

In problem D we can use a binary search for counting the number of pairs with a fixed amount on a interval: 33359972

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

Hey anyone got the solution of E by simulating the process using stacks, as i am getting stuck somewhere in this implementation.

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

Hi guys! Can anybody help me with problem F ?! I tried to solve it using a Multimap and a Fenwick Tree for building the initial positions but I'm getting "Wrong answer" on test 7 :(( Maybe I omit something. Thx in advance!

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

    I solved it by checking if some char already deleted. If yes, don't update

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

      Thank you! I was just deleting characters multiple times. ^^

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

I have a doubt in Problem E.

While merging the two nodes, I can see how we are deleting the right and the left element from the second set(called segments), and then inserting the merged set. I don't understand, how can we perform the same operation in the first set(called lens) ?

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

Hey guys! Here are some of my thoughts on problem E this round, using priority queue and linked list! Have a glance! Use of Linked List and Priority Queue in CF Round 452, Problem E

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

    can you please explain how the merge section and del function is working? I am a beginner and unable to understand it directly from your code.

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

      Yeah. The del function will be called when I need to remove a node.

      For the merge function, when I remove a node, I need to consider whether the node on the left and the one on the right will merge to a longer sequence. For example, after delete [2,2,2,2] in [3,3,3,1,1,2,2,2,2,1,1], the two sequence [1,1] and [1,1] merge together and become a long sequence, that's what the merge function does.

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

In 899F, I didnt understand how would change the current l,r to positions in initial string using segment tree?

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

    we can use binary search the prefix sum on the segment tree。

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

      Please elaborate a bit more.

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

        Sure。 We define a sequence a, a_i equals 0 if the ith element of the original sequence has been deleted, otherwise a_i equals 1. If we need to find the current position of the xth element in the original sequence, then it is equivalent to the smallest i that satisfies the sequence sum [i] = x. Because the sum function is incremented, we can use the binary search to find i that satisfies the condition, This i is the current position of the xth element in the original sequence. We can use the segment tree to maintain this sequence a.

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

    What does it mean for an item to be in the ith position? It means that before it there are i — 1 items before it.

    Now assume for each query you have a data structure that tells you for each original index of the string, how many non deleted elements are before it.

    Now to find index L, you just need to find index i such that there are l — 1 non deleted items before it.

    Can be done by Binary search + fenwick tree or segment tree.

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

Hello guys, Happy Coming New Year to everyone! Can somebody help me, why do I keep getting TL7? Thanks in advance. Solution

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

Hey everyone The editorial for the dividing numbers question is great but have a look at my soluton its easy far.. I uses two pointer approach consider a given n = 11

1 2 3 4 5 6 7 8 9 10 11

now set i = 1 and j = n (i.e 11) now I set the condition in an loop as ::

    for (i = 1,j=n; i+2 != j && i<=j; i++,j--)
       
  • here the condition i+2!=j handle the odd length value of n and i<=j should be valid in each and every case whether it is odd or even. Formally lets run on this example case:when n = 11 i=1,j=11(Basically I put an variable count1 = 1 + 11 which stores the sum of values in an 1 group and only the values are summed when i is odd no denoting that we are putting the values in an 1 group and side by side we are storing the values of group 1 in an array A using the conditions mentioned in the code) correspondingly when i=2,j=10(count2=2+10 for even i) Now in case when n is even all the manipulations are done inside the loop using the below code .
for (i = 1,j=n; i+2 != j && i<=j; i++,j--) {
       
        if(n%2==0){//100% ok
        
        if(i%2==0&&i+1==j){
            if(count2==count1)//extra condition 
            {
                count1+=i,A[k++]=i,count2+=j;
            }
                
            else {count2+=i+j;}
        }
        else if(i%2==0&&i+1!=j){count2+=i+j;}
        
        //coding is love and fun         
        else if(i%2!=0&&i+1==j){
            if(count2==count1)
            {A[k++]=i,count1+=i,count2+=j;}
            else {count2+=i+j;}//extra condition
        }
                
                
        else if(i%2!=0&&i+1!=j){A[k++]=i,A[k++]=j,count1+=i+j;}
        }
        else {//for odd case 
            //for odd lenght both cases for even psotion and odd position 
            if(i%2!=0){A[k++]=i,A[k++]=j,count1+=i+j;}
            else {count2+=i+j;}
            
        }
    
    }

Now in case when n is odd the manipulations are done till the exit condition is not founded which is i+2!=j (founded in every odd case length n) so it will stops at i = 5 and j = 7 then out of the loop I checks that in case when count1 ! =count2 then how to arrange the remaining numbers on the group 1 and group 2.

if(n%2!=0){//this thing is outside the loop
        if(count2!=count1){
            a=(abs((count2+j+i+1)-(count1+i)));
            b=(abs((count2+i+j)-(count1+i+1))),c=(abs((count2+i+i+1)-(count1+j)));
            ans=min(min(a,min(b,c)),min(b,min(a,c)));
            if(ans==a){
                count2=count2+j+i+1,count1+=i,A[k++]=i;}
                else if(ans==b){
                 count2=count2+j+i,count1+=i+1,A[k++]=i+1;}
                    else if(ans==c){ count2=count2+i+i+1,count1+=j,A[k++]=j;}

                }
        
        else {
            A[k++]=i,A[k++]=i+1,count1=count1+i+(i+1),count2+=j;
            
        }
    }    

plzz have a look at the code deeply and plzz try to understand it..and finally

 cout<<abs(count1-count2)<<"\n";
std::cout << k <<" ";//k denotes size of group 1
    for (i = 0; i < k; i++) {
        /* code */
        cout<<A[i]<<" ";
    }

PLZZ TELL ME WHERE I AM LAGGING IN MY SOULTION or which case i am missing you can use my code below completely to run and check which case i am being missed and even try to submit my code thnkss :_) for ur time https://ide.geeksforgeeks.org/kUdLKOkj94 this is the link to my code :)

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

Problem C

Can be solved greedily:

Start with putting N on the left pile and N - 1 on the right one. Then by placing N - 2 on the right and N - 3 on the left we got left - right == 0 and we reduce the problem to the one of the size N - 4.

At some point we end up with one of four possible problem sizes: 0, 1, 2, 3.

In the first case the difference was 0 and it's the best we can do.
In the second case we get 1 which is also the best solution because in than case N = 4k + 1 and the sum = N * (N + 1) / 2 = (4k + 1)(2k) is odd.
In the third case we end up with two numbers: 1 and 2, the best diff of 1 and 2 is 1 again and again it is optimal since N = 4k + 2 and sum = (2k)(4k + 3) is odd.
In the last case we have numbers 1, 2, and 3, we can place them so diff will be 0 which is optimal.

The code

import sys

n = int(sys.stdin.readline())

g = []
ls, rs = 0, 0

for i in xrange(n, 0, -1):
    if ls <= rs:
        g.append(i)
        ls += i
    else:
        rs += i

print abs(ls - rs)
print '{} {}'.format(len(g), ' '.join(map(str, g)))
  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    i have solved it through the editorial way get ACCEPTED VERDICT but i cant figure out why my solution is not working plzz have a look at that it will be very beneficial for me both u and have applied the same thing but u done in mathematical way i done it through observation plzz understand my code link is above :_)

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

    i understand completely ur code i have done the same thing but in different way but after seeing ur algorithm i detected my mistake thnkss for ur algorithm :)

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

This tutorial is not attached to the contest (I can see only Announcement link from there).

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

Problem F can also be done using sqrt decomposition.

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

can anyone tell me why there are 11 pairs for n=15 in Div2D problem 1-8 2-7 3-6 4-5 9-10 8-11 7-12 6-13 5-14 4-15

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

Don't you think the editorials should be more elaborate(eg they can include one example).

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

Can anyone please explain why in problem D we are adding P/2 to the answer when P <= n+1 ?

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

    Because you can take P/2 pairs to form P as sum. Take as example, P = 9 and N+1 something bigger. To form P = 9 as sum of two numbers you can take, 1-8, 2-7, 3-6, 4-5. As you can see if you continue you will take 5-4 which is similar to 4-5. So moving until the middle of P gives you all the pairs and so P/2 occurs.

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

      thanks alot i got it now :-)

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

I've been stuck for ages... anyone know what test #33 was on div2E? http://codeforces.com/contest/899/submission/33345602

My answer is 1 + the correct answer. :(

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

Another solution for F :

Store the positions of every character in an array of Sets (like the tutorial)...

Then after each query we can find the original position which has the Kth order after the previous updates by storing original positions in a Binary Search Tree, such as Treap which I used and delete them from the tree while applying the query. Therefore you can get the range query according to the original positions then you can remove positions from the corresponding set using lower_bound like the Tutorial..

(Sorry about my bad English)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in C for 5998 the answer should be 0

bcoz if n is even then we can always keep all the numbers whose %4 gives 1 or 0 in the first group, while others in the second group. This always give us an absolute difference of 0.

plzz correct me if I m wrong?

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

    sorry I found out my mistake, but could anyone provide a proof for C

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

      Link to a submission based on my proof:

      36503825

      Let's consider first when n is even. Suppose that our solution is A = {2, 4, 6, ..., n} and B = {1, 3, 5, .., n - 1}. We see that

      , and therefore the difference between A and B is exactly . We can reduce this difference to zero or one by swapping elements between A and B.

      If we swap two elements x and x - 1 from A and B respectively we see that we have decreased the absolute difference by exactly two and, in general, we will only be able to reduce the difference in even amounts. Given that the difference is we need this amount to be even in order to be able to reduce it to zero or, in other words, n must be a multiple of 4. If it is not, we will only be able to reduce it to 1. After performing swaps the difference will reach one of these two values.

      If n is odd we have A = {2, 4, ..., n - 1}, and B = {1, 3, 5, ..., n}

      , and these two solutions can be transformed again to vectors that have difference zero or one by swapping x with x + 1 that belong to A and B respectively. The same arguments about being a multiple of 4 hold for the floor of