fork download
copy 
  1. import java.util.*;
  2.  
  3. class Codechef {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int t = sc.nextInt(); 
  7.  
  8.         while (t-- > 0) {
  9.             int n = sc.nextInt();
  10.             int[] a = new int[n];
  11.             for (int i = 0; i < n; i++) a[i] = sc.nextInt();
  12.  
  13.             System.out.println(countValidSequences(a, n));
  14.         }
  15.     }
  16.  
  17.     static int countValidSequences(int[] a, int n) {
  18.         int validCount = 0;
  19.  
  20.         if (simulate(a, n, 'L')) validCount++;
  21.         if (simulate(a, n, 'R')) validCount++;
  22.  
  23.         return validCount;
  24.     }
  25.  
  26.     static boolean simulate(int[] a, int n, char firstCape) {
  27.         char[] capes = new char[n];
  28.         capes[0] = firstCape;
  29.         char lastCape = firstCape;
  30.  
  31.         for (int i = 1; i < n; i++) {
  32.             int diff = a[i] - a[i - 1];
  33.  
  34.             if (Math.abs(diff) > 1) return false;
  35.  
  36.             if (diff == 1) {
  37.                 if (lastCape != 'L') return false;
  38.                 capes[i] = 'L';
  39.             } else if (diff == -1) {
  40.                 if (lastCape != 'R') return false;
  41.                 capes[i] = 'R';
  42.             } else { 
  43.                 capes[i] = (lastCape == 'L') ? 'R' : 'L'; 
  44.             }
  45.  
  46.             lastCape = capes[i];
  47.         }
  48.  
  49.         int[] prefixL = new int[n];
  50.         int[] suffixR = new int[n];
  51.  
  52.         prefixL[0] = (capes[0] == 'L') ? 1 : 0;
  53.         for (int i = 1; i < n; i++)
  54.             prefixL[i] = prefixL[i - 1] + ((capes[i] == 'L') ? 1 : 0);
  55.  
  56.         suffixR[n - 1] = (capes[n - 1] == 'R') ? 1 : 0;
  57.         for (int i = n - 2; i >= 0; i--)
  58.             suffixR[i] = suffixR[i + 1] + ((capes[i] == 'R') ? 1 : 0);
  59.  
  60.         for (int i = 0; i < n; i++) {
  61.             int actual = prefixL[i] + suffixR[i];
  62.             if (actual != a[i]) return false;
  63.         }
  64.  
  65.         return true;
  66.     }
  67. }
  68.  
Success #stdin #stdout 0.14s 54572KB
comments (?)
stdin
copy 
7
1
1
4
4 4 3 2
3
1 3 2
2
2 1
3
2 2 2
3
3 2 3
3
3 2 2
stdout
copy 
2
1
0
1
2
0
0
https://ideone.com/LLwU5z
language:
Java (HotSpot 12)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!