Solution of A\B\C @ Round#27

Solution of A\B\C @ Round#27

By onlyone, 12 years ago,

A: it's very easy. a bool vis[] is ok.

B: it can think as a directional Graph. xi->yi. there are two (a ,b), they appeer time less than N-1. we can do dfs from a to b, to check whether a can reach b, if it can, cout  a b , else cout b a.
ps:What a bad thing is I got WA during the contest, because I wrote  a 'j' as i. = =....

C: let change the sequence to a sequence only have -1,0, 1.
   s[1] = 0, if in[i]-in[i-1] > 0, s[i] = 1, else if less than 0, s[i] = -1, no change to oh.

First, we can know, if the shortest unordered subsequence exist, the length is 3, and the first number can be one of the three. scan S[i] from 2->N, if S[i]!=0, break,b=i, then continue scan, if exist S[i]+S[b]==0,break, c = i, then the ouordered subS exist.
sub is 0 1 -1 or 0 -1 1,


From -100 0 100 98 =>0 1 1 -1, but as the method above, a = 1, b = 2, c = 4, but they are ordered. the ans should be a, c-1, c. a is always 1.

why?   b is the first 1(-1), c is the first -1(1), so the number between b and c, is less than numb[b] && larger than numb[c] / larger than b && less than c, also may equal to numb[b] so compare "numb[c-1] to numb[a]" is the same "numb[b] to numb[a]" ,larger or less. numb[c] only compared to numb[c-1] from the S[]. so a c-1 c can be the ans.

/* my code:
val[1] = 0;
          scanf("%d",&a);
          for (i = 2; i <= N; i++)
          {
              scanf("%d",&b);
              val[i] = (b-a);
              a = b;
              if (val[i]<0) val[i] = -1;
              else if (val[i]>0) val[i] = 1;
          }
      //    if (N <= 2) {printf("0\n");continue ;}

k = 1;
          a = 1;

for (i = 2; i <= N; i++)
              if (val[i]) break;

if (i <= N)
          {
             b = i;
             k++;
             for (i++; i <= N; i++)
             if (val[i]+val[b]==0)
                break;               

if (i<=N)
             {
              k++;
              b = i-1;
              c = i;
             }
          }

*/

I was Hacked by others. After thinking problem E, I find the bug -100 0 100 98, but the contest is over.

This Round....How tragical I am !!!
I will do better the next Round.


I want to know how to solve the Problem D and Problem E, can you help me? thanks..