patelvaidik's blog

By patelvaidik, history, 4 weeks ago, In English,

Codeforces Round #592 (Div. 2) 1244C - The Football Season

Hello, In Problem C, we have to find the value of x,y,z for given n,p,w,d value.

x+y+z=n             equation-1
   x*w + y*d = p       equation-2 

   Let assume, if(x,y,z) is one solution, then x*w + y*d = p  where w>d already given.

   ->(x*w + w*d - w*d + y*d = p )  =====>( (x+d)*w + (y-w)*d = p  )
     so if (x,y,z) is valid triplet then (x+d,y-w,z) is also valid triplet.
   ->we know that x>=0 ,y>=0 ,z>=0 is required,

   ->if we do above operation (x,y,z) ====> (x+d,y-w,z) ==> (x+(2*d),y-(2*w),z) ... ==> (x1-d,y1+w,z1) ==> (x1,y1,z1). 
    then finally we get y < w where 1<=w<=10 ^5.

   ->so we linearly check all value of y, for 0<=y<=w-1.
     using y we find appropriate x and z value.

   ->if we do not find any triplet (x,y,z) then print -1.

   Time complexity:- O(n).


Thank you.


  • Vote: I like it
  • -3
  • Vote: I do not like it

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

Auto comment: topic has been updated by patelvaidik (previous revision, new revision, compare).

4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

There is MathJax on site, rewrite your solution in well-formatted style.