fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. class EvenOddDP {
  4.  
  5.     public static void main(String[] args) {
  6.  
  7.         Scanner scanner = new Scanner(System.in);
  8.  
  9.         int n = scanner.nextInt();
  10.  
  11.         long[] a = new long[n + 1];
  12.         long[] b = new long[n + 1];
  13.  
  14.         // Input array A
  15.         for (int i = 1; i <= n; i++) {
  16.             a[i] = scanner.nextLong();
  17.         }
  18.  
  19.         // Input array B
  20.         for (int i = 1; i <= n; i++) {
  21.             b[i] = scanner.nextLong();
  22.         }
  23.  
  24.         long[] result = computeEvenOddCounts(n, a, b);
  25.  
  26.         System.out.println("Total Even: " + result[0]);
  27.         System.out.println("Total Odd: " + result[1]);
  28.  
  29.         scanner.close();
  30.     }
  31.  
  32.     public static long[] computeEvenOddCounts(
  33.             int n, long[] a, long[] b) {
  34.  
  35.         // dpA[i][0] = journeys ending at A[i] with EVEN sum
  36.         // dpA[i][1] = journeys ending at A[i] with ODD sum
  37.         //
  38.         // dpB[i][0] = journeys ending at B[i] with EVEN sum
  39.         // dpB[i][1] = journeys ending at B[i] with ODD sum
  40.  
  41.         long[][] dpA = new long[n + 1][2];
  42.         long[][] dpB = new long[n + 1][2];
  43.  
  44.         // ---------------- BASE CASE ----------------
  45.  
  46.         if (a[1] % 2 == 0)
  47.             dpA[1][0] = 1;
  48.         else
  49.             dpA[1][1] = 1;
  50.  
  51.         if (b[1] % 2 == 0)
  52.             dpB[1][0] = 1;
  53.         else
  54.             dpB[1][1] = 1;
  55.  
  56.         // ---------------- TRANSITIONS ----------------
  57.  
  58.         for (int i = 2; i <= n; i++) {
  59.  
  60.             // To reach A[i]:
  61.             // A[i-1] -> A[i]
  62.             // B[i-1] -> A[i]
  63.  
  64.             if (a[i] % 2 == 0) {
  65.  
  66.                 // Adding even keeps parity same
  67.                 dpA[i][0] =
  68.                         dpA[i - 1][0] + dpB[i - 1][0];
  69.  
  70.                 dpA[i][1] =
  71.                         dpA[i - 1][1] + dpB[i - 1][1];
  72.  
  73.             } else {
  74.  
  75.                 // Adding odd flips parity
  76.                 dpA[i][0] =
  77.                         dpA[i - 1][1] + dpB[i - 1][1];
  78.  
  79.                 dpA[i][1] =
  80.                         dpA[i - 1][0] + dpB[i - 1][0];
  81.             }
  82.  
  83.  
  84.             // To reach B[i]:
  85.             // A[i-1] -> B[i]
  86.             // B[i-1] -> B[i]
  87.  
  88.             if (b[i] % 2 == 0) {
  89.  
  90.                 // Adding even keeps parity same
  91.                 dpB[i][0] =
  92.                         dpA[i - 1][0] + dpB[i - 1][0];
  93.  
  94.                 dpB[i][1] =
  95.                         dpA[i - 1][1] + dpB[i - 1][1];
  96.  
  97.             } else {
  98.  
  99.                 // Adding odd flips parity
  100.                 dpB[i][0] =
  101.                         dpA[i - 1][1] + dpB[i - 1][1];
  102.  
  103.                 dpB[i][1] =
  104.                         dpA[i - 1][0] + dpB[i - 1][0];
  105.             }
  106.         }
  107.  
  108.         // ---------------- FINAL ANSWER ----------------
  109.  
  110.         // We can end at either A[n] or B[n]
  111.  
  112.         long even =
  113.                 dpA[n][0] + dpB[n][0];
  114.  
  115.         long odd =
  116.                 dpA[n][1] + dpB[n][1];
  117.  
  118.         return new long[]{even, odd};
  119.     }
  120. }
Success #stdin #stdout 0.14s 56868KB
comments (?)
stdin
copy 
3
1 2 3
4 5 6
stdout
copy 
Total Even: 4
Total Odd: 4
https://ideone.com/dEltDI
language:
Java (HotSpot 12)
created:
1 day 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!