Page 1 of 1

Problem Hidden Password from ACM-ICPC

Posted: Mon Oct 10, 2005 2:04 pm
by EfEr
I tried to solve the problem from http://acmicpc-live-archive.uva.es/nuev ... php?p=2755
I got WA, even though I got Accepted on another on-line judge (with exactly the same source), and I got 100 points at a romanian contest in which it was a similar problem (I tested it with the tests from that contest).
I think the tests are wrong, but still there are some Accepted solutions...

Here is my code:

Code: Select all

#include <cstdio>
#include <cassert>

int n;
inline int next(int s) {
	return (s + 1) % n;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("t.in", "rt", stdin);
#endif

	const int nmax = 100000;
	int ts;
	scanf("%d", &ts);
	for (int it = 0; it < ts; ++ it) {
		scanf("%d", &n);
		char s[nmax];
		scanf("%s", s);
		int w[nmax], t = n;
		for (int i = 0; i < n; ++ i)
			w[i] = i;
		for (; t > 1;) {
			int nt = 0;
			for (int i = 0; i < t; ++ i) {
				if (i + 1 < t) {
					int s1 = w[i], s2 = w[i + 1], j = 0;
					const int l = s2 - s1;
					assert(l > 0);
					for (; s[s1] == s[s2] && j < l; ++ j, s1 = next(s1), s2 = next(s2));
					if (j < l && s[s1] > s[s2])
						w[nt ++] = w[i + 1];
					else w[nt ++] = w[i];
					++ i;
				}
				else w[nt ++] = w[i];
			}
			t = nt;
		}

		printf("%d\n", w[0]);
	}
	return 0;
}

Wrong input file

Posted: Mon Oct 10, 2005 3:39 pm
by EfEr
Well, I managed to solve it after all... The problem was that the number of tests was different then it should have been... I got AC when I read until I got EOF

Posted: Thu Oct 20, 2005 8:50 pm
by ledins
your coding style rocks:

Code: Select all

      for (; t > 1;)