The problem can be reduced to a matching problem.
It can be solved by Dinic's algorithm.

Some useful tests for WA3:
3 3
2 2 3
answer: NO

4 3
2 2 3
answer: YES

Actually, you can solve it as a graph problem, where numbers 0, 1, ..., n are vertices, which connected like: 0-1, 1-2, ...

Please, tell me what is in Test4???????

Here is my solution and used test cases. I don't understand why I
always get WA. 8-(

Test 1.
5 4 2 0 1 2: NO

Test 2.5 4 2 0 1 5: YES

Test 3.
5 4 2 0 3 5: YES

Test 4.
5 4 2 0 3 4: YES

Test 5.
5 5 2 0 3 4 5: YES

Test 6.
5 5 2 0 2 4 5: YES

Test 7.
5 6 2 1 2 4 5 0: NO

Test 8.
5 4 1 2 2 3: YES

Test 9.
5 5 1 2 3 4 3: YES

Test 10.
5 5 1 1 0 3 4: NO

Test 11.
5 3 0 0 1: NO

Test 12.
5 3 0 1 1: NO

Test 13.
5 3 1 2 2: YES

Test 14.
5 3 1 1 2: YES

Test 15.
5 3 4 4 5: NO

Test 16.
5 3 3 4 4: YES

Test 17.
5 3 4 5 5: NO

Test 18.
5 3 3 4 5: YES

Test 19.
2 2 1 1: YES

Test 20.
2 2 2 2: NO

Source code:

[code deleted]

Edited by moderator 13.02.2007 20:57

There is my code:

Program t1134;

Const MaxN=1000;

Var Card      : array[1..MaxN]of boolean;
    Numb      : array[1..MaxN]of integer;
    Use       : array[1..MaxN]of boolean;
    M,N,i,j   : integer;
    ex        : boolean;

begin
Read(N,M);
if (M>N)or(m=0) then begin
 writeln('NO');
 halt(0);
end;
for i:=1 to N do Card[i]:=false;
for i:=1 to M do Use[i]:=false;
for i:=1 to M do begin
 read(Numb[i]);
 if (Numb[i]<0)or(Numb[i]>n) then begin
   writeln('NO');
   halt(0);
 end;
end;
for i:=1 to M do
 if Numb[i]=0 then begin
  Use[i]:=true;
  if Card[1] then begin
    writeln('NO');
    halt(0);
  end;
  Card[1]:=true;
 end else
 if Numb[i]=n then begin
  Use[i]:=true;
  if Card[n] then begin
    writeln('NO');
    halt(0);
  end;
  Card[n]:=true;
 end;
for i:=1 to m-1 do if not(use[i]) then
 for j:=i+1 to m do if not(use[j]) then
  if numb[i]=numb[j] then begin
   if (card[numb[i]])or(card[numb[j]-1]) then begin
    writeln('NO');
    halt(0);
   end;
   card[numb[i]-1]:=true;
   card[numb[i]]:=true;
   use[i]:=true;
   use[j]:=true;
  end;
repeat
ex:=true;
for i:=1 to m do if not(use[i]) then
 if (card[numb[i]])or(card[numb[i]-1]) then begin
  if (card[numb[i]])and(card[numb[i]-1]) then begin
    writeln('NO');
    halt(0);
  end;
  if card[numb[i]] then begin
   card[numb[i]-1]:=true;
   use[i]:=true;
  end else begin
   card[numb[i]-1]:=true;
   use[i]:=true;
  end;
 end;
until ex;
Writeln('YES');
end.

Sorry for my bad english

I'm see all exists tests, and  I'm get a correct result on these tests(according comments).

Let <ms> is init array, <flag> is (answer is YES?).
1. I do check that (the number in <ms>) is not greater than <n>
2. I'm sorted <ms>.
3. I'm create a <isFills> = new Array[Boolean](n+1)

And then I use the following code:

     if (m>1 && ms(1) == 0) return false  // (ms(0)==ms(1)==0) => "NO"
     if (m>1 && ms(m-2)==n) return false  // (ms(m-2)==ms(m-1)==n) => "NO"

     isFills(max(ms(0)-1, 0)) = true
     for (i <- 1 until m) {
       if (!isFills(ms(i)-1) || !isFills(ms(i))) {
         if (!isFills(ms(i)-1)) isFills(ms(i)-1) = true
         else                   isFills(ms(i))   = true
       } else return false
     }
     return flag

     Console.println(if (getFlag==true) "YES" else "NO")
Full code:
object Main {
   import java.util.Scanner
   import math._

   val scan = new Scanner(System.in)
   val n = scan.nextInt()
   val m = scan.nextInt()
   val ms = new Array[Int](max(m,1))
   for (i <- 0 until m) ms(i) = scan.nextInt()
   scan.close()

   def getFlag: Boolean = {
     var flag = true

     for (i <- 0 until m) flag &&=  ms(i)<=n
     if (!flag) return flag

     java.util.Arrays.sort(ms)
     val isFills = new Array[Boolean](n+1)


     if (m>1 && ms(1) == 0) return false
     if (m>1 && ms(m-2)==n) return false

     isFills(max(ms(0)-1, 0)) = true
     for (i <- 1 until m) {
       if (!isFills(ms(i)-1) || !isFills(ms(i))) {
         if (!isFills(ms(i)-1)) isFills(ms(i)-1) = true
         else                   isFills(ms(i))   = true
       } else return false
     }
     flag
   }
   Console.println(if (getFlag==true) "YES" else "NO")

   def main(args: Array[String]){}
}
Edited by author 26.12.2015 23:56

Edited by author 26.12.2015 23:57

please tell me how 1 1 2 2 can be YES.Because if Nick take cards for example that

0 1 reads 1
1 2 reads 1
2 3 reads 2
and he can't write 1 2 and 2 3 and answer must be NO i think

Sorry I understnd all :)

Edited by author 17.08.2008 04:31

Edited by author 17.08.2008 04:32

linear time input + O(nlogn) time sorting + O(n)time availability checking gives ac in .015 sec and 150 kb.
I think better solution is possible. Please, let me know.

i tryed all possible tests but i am still getting mistake on the fifth test. can somebody give me some tricky tests to help me?

The new compiler supports regex and thus the problem can be solved with 12 lines of real code (263 chars) and a 5-line header (include, ...).

I use n^4 algorythm and works for 0.015 secs. :P

m positive integer numbers are listed

in sample there is number 0. So 'positive' should be replaced by 'non-negative'.

Remember, that (0,1) belong to the FIRST Card.
If your get RE - check, that after Sorting every number < nCards =)

Subj.

PS
Im sorry for my english.
Same in Russian:
Сколько раз Ник может ошибиться?

Ok, here are some:
Test 1:
8 6
1 2 2 3 4 4
ANSWER: NO

Test 2:
8 4
0 1 2 2
ANSWER: NO

My code works fine with the test cases discussed here ...
But still am getting wrong answer for test case #11
Can anyone give a tricky test case tat would help me ??

don't think about the minus and you will find it so easy...think about it as if all numbers are written positive.:)

I got WA on test 12.
please give me some test.

thank you.