i got AC but somehow i did'n understand this problem.(can you help me?)

Posted by

cena 17 Feb 2013 15:04

hi all;

here's a bit simpler algorithm than in the question:

if(x > 0 && y > 0) {

for(i = 1; i <= x + y; ++i) {

y = x * x + y;

x = x * x + y;

y = sqrt((double)x - y);

x -= (2 * y * y);

}

}

could anyone prove it to me how this scary algorithm is the one in O(1),

i mean the one that tests reminders and then swap (if necessary).

thank you.

*Edited by author 17.02.2013 15:05*

*Edited by author 17.02.2013 15:05*

Re: i got AC but somehow i did'n understand this problem.(can you help me?)

Posted by

Steve 1 Jul 2013 01:01

Once you've reduced it that far, you can use algebra to show that all the procedure in the for loop really does is swap the variables. That coupled with the conditions of the for loop give you the O(1) solution.

*Edited by author 01.07.2013 01:03*