ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1214. Strange Procedure

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