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 1024. Permutations

Keep getting WAs
Posted by Frankie 28 Nov 2011 19:34
kkk, i figured out about the LCMs pretty much myself, but i just keep getting WAs on tests like 4 or 3 and that's sooo embarassing
<code>
#include <stdio.h>
#include <cmath>
#include <set>

using namespace std;

long long gcd(long long a, long long b) {
return !b ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
return (a / gcd(a,b) * b);
}

int main()
{

int n;

scanf("%d", &n);

set<int> ds; // a usual stl set which stores the distaces of all elements
int tmp;
for(int i=1;i<n+1;i++) {
scanf("%d", &tmp);
ds.insert(abs(i-tmp));
}

long long res;
if(ds.size() == 1 && ds.count(0)) res = 1;
else {
if(ds.count(0)) ds.erase(ds.find(0));
res = 1;
for (set<int>::iterator it = ds.begin(); it != ds.end(); ++it) {
res = lcm(res,*it);
}
}

printf("%lld", res);

}
</code>
And the worst thing is I just can't think of a straightforward test for which that gives a wrong answer.
5  4 1 5 2 3 => 6
1  1 => 1
5  1 2 3 4 5 => 1
6  6 5 3 4 2 1 => 15
didn't check for ns like 100 and i don't think that's the problem. also i don't think the problem is about malformed longlong operation, cause if i replace that with ints the WAs are all the same.
would really like if someone helped me 'bout that ((

Edited by author 28.11.2011 19:38
Re: Keep getting WAs
Posted by Frankie 29 Nov 2011 11:28
"Every problem has a simple, fast and wrong solution."
- that one is soooo right :D

i mean, i came up with the distances of the items, but those actually should be the lengths of cycles ))
it was like 4 1 5 2 3 => 3 2 1 2 2
but should be like 4 1 5 2 3 => 3 3 2 3 2
- and it's really straightforward to figure out how it works :D
the worst thing about my initial solution is that it worked in some trivial cases :)

now i made something like that:
[code deleted]
and finally got AC after 23 WAs :) so happy 'bout that

Edited by moderator 04.12.2019 20:47
Re: Keep getting WAs
Posted by Bogatyr 13 Sep 2012 23:49
Look out for left over debug prints!   I was tearing my hair out over WAs after I figured out doing the LCM of all the unique cycle counts and was convinced the approach was correct, and I was right!   But one left over debug print messed me up until I finally saw it.