10730 - Antiarithmetic?

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » Mon Feb 14, 2005 8:23 am

It was wrong, I've just checked :)

I checked that 0,1,2,3...n-1 alter directions, then that 0,2,4,6,... alter directions, then that 0,3,6,9,... alter directions and so on. However, sub-sequences like 1,3,5 wouldn't be tested and that killed the method with smallest counter-example of 6 items. Fortunately (or not) it wasn't in test data. It is: 0 4 2 1 3 5. If we check same way from the higher end, than smallest counter-example consists of 7 items.

My head was too full with number of inverses by the time I developed that wrong algorithm. I am sorry :)

james299
New poster
Posts: 10
Joined: Tue Jul 26, 2005 8:58 am
Location: Taiwan

I'm confused!

Post by james299 » Fri Jul 29, 2005 6:27 am

Hi! :)
The problem statement says
For example, the sequence (2, 0, 1, 4, 3) is an antiarithmetic permutation of 5. The sequence (0, 5, 4, 3, 1, 2) is not an antiarithmetic permutation as its first, fifth and sixth term (0, 1, 2) form an arithmetic progression; and so do its second, forth and fifth term (5, 3, 1).
So, it seems to be ok with decreasing order sequence.
And I mutiply by -1 when the difference is negative.

Code: Select all

If Third = 5 - 3 - 3 ; (< 0)
   Third *= -1;
 if(Third<n&&Y[Third]>j) ...
But I got WA.And I try to get rid of decreasing order sequence as Misof said, it got AC.
:-?
Thanks for your precious time. :D

marif
New poster
Posts: 11
Joined: Sat Jun 24, 2006 11:42 am
Location: BANGLADESH
Contact:

need some critical I/O

Post by marif » Fri Jul 07, 2006 3:29 pm

Anyone please post some critical inputs and outputs on this topic. It will be very helpful.

User avatar
Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

What is the wrong

Post by Tanu » Sat Jul 22, 2006 5:46 am

what is the wrong with my code...
I save the indexes and checked for n, is the position if n+1 and n+2 is greater than position of n...
is there anything wrong understanding with my code...
plz help...

Code: Select all

#include<stdio.h>
#include<string.h>
long in[10005],pos[10005];
main()
{
	char s[15];
	long len,n,i;
	bool flag;
	while(1)
	{
		scanf("%s",s);
		if(strcmp(s,"0")==0)
			break;
		len = strlen(s);
		n = 0;
		for(i=0;i<len;i++)
			if(s[i]>='0' && s[i]<='9')
				n = n*10+(s[i]-'0');
		for(i=1;i<=n;i++)
		{
			scanf("%ld",&in[i]);
			pos[in[i]] = i;
		}
		flag = false;
		for(i=1;i<=n-2;i++)
			if(i<pos[in[i]+1] && pos[in[i]+1] < pos[in[i]+2])
			{
				flag = true;;
				break;
			}
		if(flag)
			printf("no\n");
		else
			printf("yes\n");
	}
	return 0;
}
Thinking you are a kind helper...
...Tanu[/list]

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sat Jul 22, 2006 8:19 am

Now you didn't even check 3 posts above yours...

For 0 4 2 1 3 5 your program gives "yes".

morkoh
New poster
Posts: 2
Joined: Sat Oct 18, 2014 7:22 pm

Re: 10730 - Antiarithmetic?

Post by morkoh » Mon Oct 27, 2014 10:09 pm

Why is it enough to check only rising arithmetic sequences?
My code passes the judge, but it outputs a wrong answer for
5: 0 4 3 2 1 --> "yes"
5: 2 4 3 1 0 --> "yes"
when both should be "no", first one has (4,3,2,1) second (2,1,0).

The code which checks both rising and falling arithmetic sequences also gets accepted.
A bit weird, I guess.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10730 - Antiarithmetic?

Post by brianfry713 » Wed Oct 29, 2014 10:46 pm

That would imply that the judge's I/O is weak if your incorrect code gets AC.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 107 (10700-10799)”