Google Kick Start Archive — Practice Round 2019 problems


Thank you for participating in Kick Start 2019 practice round. This was the first round using a redesigned UI — we hope you enjoyed solving the problems and had a smooth experience. Please don't hesitate to let us know if you encountered any issues by emailing

Looking forward to having your participation in upcoming rounds.

A. Number Guessing

Welcome to the Practice Session!

If you experience any technical issues interfering with your ability to participate in the Practice Session, please email us immediately at We will have limited support during the session, but will get back to you as soon as possible. For all other feedback, we invite you to submit your thoughts and suggestions via this feedback form after the Practice Session.


This problem is a well-known classic; we present it primarily as an opportunity for you to try out the interactive judging system.

We are thinking of an integer P within the range (A,B] — that is, A < P ≤ B. You have N tries to guess our number. After each guess that is not correct, we will tell you whether P is higher or lower than your guess.

Input and output

This problem is interactive, which means that the concepts of input and output are different than in standard Code Jam problems. You will interact with a separate process that both provides you with information and evaluates your responses. All information comes into your program via standard input; anything that you need to communicate should be sent via standard output. Remember that many programming languages buffer the output by default, so make sure your output actually goes out (for instance, by flushing the buffer) before blocking to wait for a response. See the FAQ for an explanation of what it means to flush the buffer. Anything your program sends through standard error is ignored, but it might consume some memory and be counted against your memory limit, so do not overflow it. To help you debug, a local testing tool script (in Python) is provided at the very end of the problem statement.

Initially, your program should read a single line containing a single integer T indicating the number of test cases. Then, you need to process T test cases.

For each test case, your program will read a single line with two integers A and B, representing the exclusive lower bound and inclusive upper bound, as described above. In the next line, you will read a single integer N, representing the maximum number of guesses you can make. Your program will process up to N exchanges with our judge.

For each exchange, your program needs to use standard output to send a single line with one integer Q: your guess. In response to your guess, the judge will print a single line with one word to your input stream, which your program must read through standard input. The word will be CORRECT if your guess is correct, TOO_SMALL if your guess is less than the correct answer, and TOO_BIG if your guess is greater than the correct answer. Then, you can start another exchange.

If your program gets something wrong (e.g., wrong output format, or out-of-bounds values), the judge will send WRONG_ANSWER to your input stream and it will not send any other output after that. If your program continues to wait for the judge after receiving WRONG_ANSWER, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive the appropriate verdict (Wrong Answer, Runtime Error, etc.) instead of a Time Limit Exceeded error. As usual, if the total time or memory is exceeded, or your program gets a runtime error, you will receive the appropriate verdict.

If your test case is solved within N tries, you will receive the CORRECT message from the judge, as mentioned above, and then continue to get input (a new line with two integers A and B, etc.) for the next test case. After N tries, if the test case is not solved, the judge will print WRONG_ANSWER and then stop sending output to your input stream.

You should not send additional information to the judge after solving all test cases. In other words, if your program keeps printing to standard output after receiving CORRECT for the last test case, you will get a Wrong Answer judgment.


1 ≤ T ≤ 20.
A = 0. N = 30.
Time limit: 10 seconds per test set.
Memory limit: 1GB.

Test set 1 (Visible)

B = 30.

Test set 2 (Hidden)

B = 109.

Sample interaction

Here is a piece of pseudocode that demonstrates an interaction for one test set. Suppose there are three test cases in this test set. The pseudocode first reads an integer t, representing the number of test cases. Then the first test case begins. Suppose the correct answer P is 9 for the first test case. The pseudocode first reads three integers a, b, and n, representing the guessing range and maximum number of tries, respectively, and then outputs a guess 30. Since 30 is greater than 9, the string TOO_BIG is received through stdin from the judge. Then the pseudocode guesses 5 and receives TOO_SMALL in response. The guess 10 is subsequently printed to stdout which is again too big. Finally the pseudocode guesses 9, and receives CORRECT because 9 is the correct answer.

  t = readline_int()         // reads 3 into t
  a, b = readline_two_int()  // reads 0 into a and 30 into b; note that 0 30 is one line
  n = readline_int()         // reads 30 into n
  printline 30 to stdout     // guesses 30
  flush stdout
  string s = readline()      // because 30 > 9, reads TOO_BIG into s
  printline 5 to stdout      // guesses 5
  flush stdout
  s = readline()             // reads TOO_SMALL into s since 5 < 9
  printline 10 to stdout     // guesses 10
  flush stdout
  s = readline()             // reads TOO_BIG into s since 10 > 9
  printline 9 to stdout      // guesses 9
  flush stdout
  s = readline()             // reads CORRECT into s

The second test case shows what happens if the code continues to read from stdin after the judge stops sending info. In this example, the contestant guesses 31, which is outside the range (0, 30]. As a result, the judging system sends WRONG_ANSWER to the input stream of the pseudocode and stops sending anything after that. However, after reading WRONG_ANSWER into string s, the code continues to read for the next test case. Since there is nothing in the input stream (judge has stopped sending info), the code hangs and will eventually receive a Time Limit Exceeded Error.

  a, b = readline_two_int()  // reads 0 into a and 30 into b; note that 0 30 is one line
  n = readline_int()         // reads 30 into n
  printline 31 to stdout     // guesses 31
  flush stdout
  string s = readline()      // reads WRONG_ANSWER
  a, b = readline_two_int()  // tries to read for the third test case but hangs since
                             // judge has stopped sending info to stdin

If the code in the example above exits immediately after reading WRONG_ANSWER, it will receive a Wrong Answer judgment instead.

  a, b = readline_two_int()  // reads 0 into a and 30 into b; note that 0 30 is one line
  n = readline_int()         // reads 30 into n
  printline 31 to stdout     // guesses 31
  flush stdout
  string s = readline()      // reads WRONG_ANSWER
  exit                       // receives a Wrong Answer judgment

Testing Tool

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.

Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.

Download testing tool


Thanh wants to paint a wonderful mural on a wall that is N sections long. Each section of the wall has a beauty score, which indicates how beautiful it will look if it is painted. Unfortunately, the wall is starting to crumble due to a recent flood, so he will need to work fast!

At the beginning of each day, Thanh will paint one of the sections of the wall. On the first day, he is free to paint any section he likes. On each subsequent day, he must paint a new section that is next to a section he has already painted, since he does not want to split up the mural.

At the end of each day, one section of the wall will be destroyed. It is always a section of wall that is adjacent to only one other section and is unpainted (Thanh is using a waterproof paint, so painted sections can't be destroyed).

The total beauty of Thanh's mural will be equal to the sum of the beauty scores of the sections he has painted. Thanh would like to guarantee that, no matter how the wall is destroyed, he can still achieve a total beauty of at least B. What's the maximum value of B for which he can make this guarantee?


The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing an integer N. Then, another line follows containing a string of N digits from 0 to 9. The i-th digit represents the beauty score of the i-th section of the wall.


For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum beauty score that Thanh can guarantee that he can achieve, as described above.


1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.

Small dataset (Test set 1 - Visible)

2 ≤ N ≤ 100.

Large dataset (Test set 2 - Hidden)

For exactly 1 case, N = 5 × 106; for the other T - 1 cases, 2 ≤ N ≤ 100.


Sample Input
content_copy Copied!
Sample Output
content_copy Copied!
Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31

In the first sample case, Thanh can get a total beauty of 6, no matter how the wall is destroyed. On the first day, he can paint either section of wall with beauty score 3. At the end of the day, either the 1st section or the 4th section will be destroyed, but it does not matter which one. On the second day, he can paint the other section with beauty score 3.

In the second sample case, Thanh can get a total beauty of 14, by painting the leftmost section of wall (with beauty score 9). The only section of wall that can be destroyed is the rightmost one, since the leftmost one is painted. On the second day, he can paint the second leftmost section with beauty score 5. Then the last unpainted section of wall on the right is destroyed. Note that on the second day, Thanh cannot choose to paint the third section of wall (with beauty score 8), since it is not adjacent to any other painted sections.

In the third sample case, Thanh can get a total beauty of 7. He begins by painting the section in the middle (with beauty score 1). Whichever section is destroyed at the end of the day, he can paint the remaining wall at the start of the second day.

C. Kickstart Alarm


Shil has a very hard time waking up in the morning each day, so he decides to buy a powerful alarm clock to Kickstart his day. This Alarm is called a Kickstart Alarm. It comes pre-configured with K powerful wakeup calls. Before going to bed, the user programs the clock with a Parameter Array consisting of the values A1, A2, ..., AN. In the morning, the clock will ring K times, with the i-th wakeup call having power POWERi.

To calculate POWERi, the alarm generates all the contiguous subarrays of the Parameter Array and calculates the summation of the i-th exponential-power of all contiguous subarrays. The i-th exponential-power of subarray Aj, Aj+1, ..., Ak is defined as Aj × 1i + Aj+1 × 2i + Aj+2 × 3i + ... + Ak × (k-j+1)i. So POWERi is just the summation of the i-th exponential-power of all the contiguous subarrays of the Parameter Array.

For example, if i = 2, and A = [1, 4, 2], then the i-th exponential-power of A would be calculated as follows:

  • 2-nd exponential-power of [1] = 1 × 12 = 1
  • 2-nd exponential-power of [4] = 4 × 12 = 4
  • 2-nd exponential-power of [2] = 2 × 12 = 2
  • 2-nd exponential-power of [1, 4] = 1 × 12 + 4 × 22 = 17
  • 2-nd exponential-power of [4, 2] = 4 × 12 + 2 × 22 = 12
  • 2-nd exponential-power of [1, 4, 2] = 1 × 12 + 4 × 22 + 2 × 32 = 35
so the total is 71.

Tonight, Shil is using his Kickstart Alarm for the first time. Therefore, he is quite worried about the sound the alarm might make in the morning. It may wake up the neighbors, or, worse yet, it may wake up the whole planet! However, calculating the power of each wakeup call is quite difficult for him. Given K and the Parameter Array A1, A2, ..., AN, can you help him by calculating the summation of power of each wakeup call: POWER1 + POWER2 + ... + POWERK?


The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with nine integers N, K, x1, y1, C, D, E1, E2 and F. N is the length of array A, K is the number of wakeup calls. Rest of the values are parameters that you should use to generate the elements of the array A, as follows.

Use the recurrences below to generate xi and yi for i = 2 to N:

  • xi = ( C × xi-1 + D × yi-1 + E1 ) modulo F.
  • yi = ( D × xi-1 + C × yi-1 + E2 ) modulo F.
We define Ai = ( xi + yi ) modulo F, for all i = 1 to N.


For each test case, output one line containing Case #x: POWER, where x is the test case number (starting from 1) and POWER is the summation of POWERi, for i = 1 to K. Since POWER could be huge, print it modulo 1000000007 (109 + 7).


1 ≤ T ≤ 100.
Time limit: 90 seconds per test set.
Memory limit: 1 GB.
1 ≤ x1 ≤ 105.
1 ≤ y1 ≤ 105
1 ≤ C ≤ 105.
1 ≤ D ≤ 105.
1 ≤ E1 ≤ 105.
1 ≤ E2 ≤ 105.
1 ≤ F ≤ 105.

Small dataset (Test set 1 - Visible)

1 ≤ N ≤ 100.
1 ≤ K ≤ 20.

Large dataset (Test set 2 - Hidden)

1 ≤ N ≤ 106.
1 ≤ K ≤ 104.


Sample Input
content_copy Copied!
2 3 1 2 1 2 1 1 9
10 10 10001 10002 10003 10004 10005 10006 89273
Sample Output
content_copy Copied!
Case #1: 52
Case #2: 739786670

In Sample Case #1, the Parameter Array is [3, 2]. All the contiguous subarrays are [3], [2], [3, 2].

For i = 1:

  • 1-st Exponential-power of [3] = 3 × 11 = 3
  • 1-st Exponential-power of [2] = 2 × 11 = 2
  • 1-st Exponential-power of [3, 2] = 3 + 2 × 21 = 7
So POWER1 is 12.

For i = 2:

  • 2-nd Exponential-power of [3] = 3 × 12 = 3
  • 2-nd Exponential-power of [2] = 2 × 12 = 2
  • 2-nd Exponential-power of [3, 2] = 3 + 2 × 22 = 11
So POWER2 is 16.

For i = 3:

  • 3-rd Exponential-power of [3] = 3 × 13 = 3
  • 3-rd Exponential-power of [2] = 2 × 13 = 2
  • 3-rd Exponential-power of [3, 2] = 3 + 2 × 23 = 19
So POWER3 is 24.

Analysis — A. Number Guessing

Test set 1

Since A = 0 and B = 30 in this test set, and since we get N = 30 tries per test case, we can simply guess every number from 1 to 30 until the judge sends back CORRECT.

Test set 2

In test set 2, since the answer could be anywhere in the range (0, 109] and we still have only 30 guesses, we will use binary search.

Initially, we know the answer P is in [1, 109], which is a big range! To cut that range by half, our first guess will be (1 + 109) / 2 = 5×108. If the judge sends back TOO_SMALL, we will know that P is in [1, 5×108). Similarly, if the judge sends back TOO_BIG, P is in (5×108, 109]. Otherwise, P is 5×108 and we are done.

We will cut that range further by making our next guess the middle number in that range. Again, based on the judge response that we get, we will know that either we have guessed P correctly, or P is in the upper or lower half of the range. We will do this repeatedly, until CORRECT is received.

Each time we make a wrong guess, the range that we must examine next will always be at most half the size of our previous range. So, it will take at most log2109 = 29.897353 < 30 tries to guess P correctly.

Sample Solutions

This problem was intended as an opportunity to get used to our interactive judges. Here are some example solutions in all languages that we support so far:


read t
for p in $(seq 1 $t); do
  read -a line
  read n
  head=$(( a+1 ))
  while true; do
    mid=$(( (head+tail)/2 ))
    echo $mid
    read s
    if [[ "$s" == "CORRECT" ]]; then
    elif [[ "$s" == "TOO_BIG" ]]; then
      tail=$(( mid - 1 ))
    elif [[ "$s" == "TOO_SMALL" ]]; then
      head=$(( mid + 1 ))
      # Wrong answer; exit to receive Wrong Answer judgment
      exit 0


#include <stdio.h>
#include <string.h>

int main() {
  int T; scanf("%d", &T);

  for (int id = 1; id <= T; ++id) {
    int A, B, N, done = 0;
    scanf("%d %d %d", &A, &B, &N);
    for (++A; !done;) {
      int mid = A + B >> 1;
      char result[32];
      printf("%d\n", mid);
      scanf("%s", result);
      if (!strcmp(result, "CORRECT")) done = 1;
      else if (!strcmp(result, "TOO_SMALL")) A = mid + 1;
      else B = mid - 1;
  return 0;


using System;

public class Solution
  static public void Main ()
    int num_test_cases = Convert.ToInt32(Console.ReadLine());
    for (int i = 0; i < num_test_cases; ++i) {
      string[] lo_hi_s = Console.ReadLine().Split(' ');
      int[] lo_hi = Array.ConvertAll(lo_hi_s, int.Parse);
      int num_tries = Convert.ToInt32(Console.ReadLine());
      int head = lo_hi[0] + 1, tail = lo_hi[1];
      while (true) {
        int m = (head + tail) / 2;
        Console.WriteLine (m);
        string s = Console.ReadLine();
        if (s == "CORRECT") break;
        if (s == "TOO_SMALL")
          head = m + 1;
          tail = m - 1;


#include <iostream>
#include <string>

int main() {
  int num_test_cases;
  std::cin >> num_test_cases;
  for (int i = 0; i < num_test_cases; ++i) {
    int lo, hi;
    std::cin >> lo >> hi;
    int num_tries;
    std::cin >> num_tries;
    int head = lo + 1, tail = hi;
    while (true) {
      int m = (head + tail) / 2;
      std::cout << m << std::endl;
      std::string s;
      std::cin >> s;
      if (s == "CORRECT") break;
      if (s == "TOO_SMALL")
        head = m + 1;
        tail = m - 1;
  return 0;


package main

import (

func main() {
  var t int
  fmt.Scanf("%d", &t)
  for i := 1; i <= t; i++ {
    var a, b, n int
    fmt.Scanf("%d %d", &a, &b)
    a = a + 1
    fmt.Scanf("%d", &n)
    for {
      m := (a + b) / 2
      var str string
      fmt.Scanf("%s", &str)
      if strings.EqualFold(str, "CORRECT") {
      } else if strings.EqualFold(str, "TOO_SMALL") {
        a = m + 1
      } else if strings.EqualFold(str, "TOO_BIG") {
        b = m - 1


import System.IO

getNum :: IO Int
getNum = do
    x <- getLine
    let n = read x :: Int
    return n

bisect :: Int -> Int -> Int -> String -> IO ()
bisect a b m "CORRECT" = return ()
bisect a b m "TOO_SMALL" = singleCase (m+1) b
bisect a b m "TOO_BIG" = singleCase a (m-1)

query :: Int -> IO String
query m = do
    putStrLn ( show m )
    hFlush stdout
    x <- getLine
    return x

singleCase :: Int -> Int -> IO ()
singleCase a b = do
    let m = (a+b) `div` 2
    response <- query m
    bisect a b m response
    return ()

solve :: Int -> IO ()
solve 0 = return ()
solve n = do
    [a, b] <- fmap(map read.words)getLine
    _ <- getNum
    singleCase (a+1) b
    solve (n-1)

main = do
    hSetBuffering stdout NoBuffering
    t <- getNum
    solve t


import java.util.Scanner;

public class Solution {
  public static void solve(Scanner input, int a, int b) {
    int m = (a + b) / 2;
    String s =;
    if (s.equals("CORRECT")) {
    } else if (s.equals("TOO_SMALL")) {
      solve(input, m + 1, b);
    } else {
      solve(input, a, m - 1);

  public static void main(String args[]) {
    Scanner input = new Scanner(;
    int T = input.nextInt();
    for (int ks = 1; ks <= T; ks++) {
      int a = input.nextInt();
      int b = input.nextInt();
      int n = input.nextInt();
      solve(input, a + 1, b);


var readline = require('readline');
var rl = readline.createInterface(process.stdin, process.stdout);

expect = 'begin';
rl.on('line', function(line) {
  if (expect === 'begin') {
    num_test_cases = parseInt(line);
    expect = 'lo_hi';
    case_counter = 0;
  } else if (expect === 'lo_hi') {
    lo_hi = line.split(' ');
    head = parseInt(lo_hi[0]) + 1;
    tail = parseInt(lo_hi[1]);
    expect = 'num_tries';
  } else if (expect === 'num_tries') {
    num_tries = line; // not used.
    expect = 'solve';
    mid = parseInt((head + tail) / 2);
  } else if (expect === 'solve') {
    if (line === 'CORRECT') {
      ++case_counter === num_test_cases ? rl.close() : 0;
      expect = 'lo_hi';
    } else {
      line === 'TOO_SMALL' ? head = mid + 1 : tail = mid - 1;
      mid = parseInt((head + tail) / 2);



function solve($a, $b) {
  $m = ($a + $b) / 2;
  printf("%d\n", $m);
  fscanf(STDIN, "%s", $s);
  if (strcmp($s, "CORRECT") == 0) {
  } else if (strcmp($s, "TOO_SMALL") == 0) {
    $a = $m + 1;
  } else {
    $b = $m - 1;
  solve($a, $b);

fscanf(STDIN, "%d", $t);
for ($ks = 0; $ks < $t; $ks++) {
  fscanf(STDIN, "%d %d", $a, $b);
  fscanf(STDIN, "%d", $n);
  solve($a + 1, $b);


import sys

def solve(a, b):
  m = (a + b) / 2
  print m
  s = raw_input()
  if s == "CORRECT":
  elif s == "TOO_SMALL":
    a = m + 1
    b = m - 1
  solve(a, b)

T = input()
for _ in xrange(T):
  a, b = map(int, raw_input().split())
  _ = input()
  solve(a + 1, b)


import sys

def solve(a, b):
  m = (a + b) // 2
  s = input()
  if s == "CORRECT":
  elif s == "TOO_SMALL":
    a = m + 1
    b = m - 1
  solve(a, b)

T = int(input())
for _ in range(T):
  a, b = map(int, input().split())
  _ = int(input())
  solve(a + 1, b)


$stdout.sync = true

def solve(a, b)
  m = (a + b) / 2
  puts m
  s = STDIN.gets.chomp
  if s.eql? "CORRECT"
  elsif s.eql? "TOO_SMALL"
    solve(m + 1, b)
    solve(a, m - 1)

t = STDIN.gets.chomp.to_i
ks = 1
while ks <= t
  a, b = &:to_i;
  n = STDIN.gets.chomp.to_i
  solve(a + 1, b)
  ks = ks + 1

Analysis — B. Mural

Mural: Analysis

We can observe that we will have painted ceil(N/2) sections in the end, and all these sections would form a contiguous subarray of the input array. Since painting and destroying is done alternatively, it might not be possible to paint any subarray of our choice. Our objective is to find the maximum subarray sum among the set of "paintable" subarrays.

Small dataset

An intuitive approach would rely on Dynamic Programming and try to define a DP state that could encapsulate the state of the painted and the destroyed sections at any point in time. Note that painted section is contiguous, and the destroyed sections are prefixes and suffixes of the input array.
Hence, we can define f(i, j, l, r) as the maximum possible achievable score if i and j are the lengths of the destroyed prefix and suffix, respectively; whereas l and r denote the left and the right boundaries of the painted subarray. A recurrence can easily be derived by considering at most four further possibilities: we have two ways to extend the mural (by painting the section either to the left or to the right of the already painted boundary), and two ways to extend the destroyed part (either the prefix or the suffix).
Note that it would seem that there are O(N4) different valid states in the above approach, but that is not the case since the sum of lengths of painted and destroyed parts is always the same. We can get rid of the index of the right boundary of the painted subarray (i.e. variable r), as it can be implicitly derived from the variables i and j.
The overall complexity of this approach is O(N3) and that will suffice for the Small dataset.

Large dataset

The solution to the Large dataset relies on an interesting observation that all possible contiguous subarrays of length ceil(N/2) are "paintable". If we can prove this fact, we can simply do an O(N) rolling window approach over all such subarrays and output the maximum possible sum.

Let's think of an intuitive way to prove this. Say, if we paint the i-th section on the first day, what could be the smallest possible index of the left boundary of the mural in the worst case? To achieve the smallest possible index, we will always extend the boundary on the left side; and in the worst case the flood can always extend the prefix, allowing us to paint only the indices after index ceil(i/2)(inclusive). And similarly, there would be an upper limit on the maximum possible index of the right boundary.
This means that given the desirable left boundary of the mural, we can figure out the "central point" from which we would begin painting. Now, irrespective of the sequence of destructions, we can always meet the desirable left boundary by always extending our subarray to the left whenever a section on the left is destroyed. Similar arguments can be applied to the right boundary.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

Analysis — C. Kickstart Alarm

Kickstart Alarm: Analysis

The problem asks us to calculate the summation of power of each wakeup call: $$$POWER_1 + POWER_2 + \ldots + POWER_K $$$, where $$$POWER_i$$$ is just the summation of the $$$i$$$-th exponential-power of all the contiguous subarrays of the Parameter Array.

Small dataset

For Small dataset, we can iterate over every subarray of the given array and calculate the summation of $$$POWER_i$$$ for all $$$i \le K$$$. Thus, the simplest brute solution will work for Small dataset.

Pseudocode for Small dataset:

  result = 0
  for(k in 1 to K) {
    for(L in 1 to N) {
      for(R in L to N) {
        for(j in L to R) {
          result = result + A[j] * pow(j-L+1,k)
          result %= 1000000007

In the above pseudcode, we can precompute all the $$$pow(a,b)$$$ values for $$$1 \le a \le n$$$ and $$$1\le b \le k$$$.
The overall time complexity is $$$O(N^3 \times K)$$$.

Large dataset

The above solution will not work for Large dataset. To solve for Large dataset, let's iterate over every position $$$x$$$ and calculate the contribution by $$$A_x$$$ to the result for all subarrays where this element is $$$y$$$-th element in the subarray.

  • If $$$y>x$$$, there is no subarray such that $$$A_x$$$ can be $$$y$$$-th element.
  • For $$$y \le x$$$, there is exactly one index where the subarray must start (i.e $$$y-1$$$ places before $$$x$$$). Hence, all the subarrays starting at $$$(n-(y-1))$$$ and ending on or after index $$$x$$$ will have $$$A_x$$$ at position $$$y$$$ in the subarray. Therefore, the number of subarrays with element $$$A_x$$$ at $$$y$$$-th position in the subarray will be $$$(n-x+1)$$$.
    Contribution from this element as $$$y$$$-th element in one subarray = $$$A_x \times y^1 + A_x \times y^2 + \ldots + A_x \times y^K$$$.
    Let us denote with $$$S(x,y)$$$ as the contribution from this element as $$$y$$$-th element in all subarrays. Combining above observations, we can show that $$$S(x,y) = (n-x+1) \times A_x \times (y^1 + y^2 + \ldots +y^K) $$$.
  • $$$ S(x,y) = 0 $$$ for $$$ y > x $$$.
  • $$$S(x,y) = A_x \times K\times (n-x+1)$$$ for $$$y=1$$$.
  • $$$S(x,y) = \frac{(n-x+1) \times A_x \times y\times (y^K-1)}{(y-1)}$$$ for $$$y \le x$$$ and $$$y>1$$$.

Contribution by element at position $$$x$$$ to the result (let us say $$$C(x)$$$ ) = $$$\sum S(x,y)$$$ for $$$1 \le y \le n$$$
$$$= (n-x+1)\times A_x \times (K + \frac{2\times (2^K-1)}{(2-1)} + \frac{3\times (3^K - 1)}{(3-1)} + \ldots \frac{x\times (x^K-1)}{(x-1)})$$$.

So we can find the contribution by element at position $$$x$$$ in $$$O(N\times \log(K))$$$. This gives us a $$$O(N^2 \times \log(K))$$$ solution to compute contribution of all the elements.

Let us define $$$G(x) = \frac{C(x)}{(A_x\times (n-x+1))} = K + \frac{2\times (2^K-1)}{(2-1)} + \frac{3\times (3^K - 1)}{(3-1)} + \ldots \frac{x\times (x^K-1)}{(x-1)}$$$.
Now if we look closely at $$$G(x)$$$ and $$$G(x+1)$$$, we can observe that
$$$G(x+1) = G(x) + \frac{(x+1)\times ((x+1)^K -1)}{x}$$$.
Hence we can compute $$$G(x+1)$$$ from $$$G(x)$$$ in $$$O(\log(K))$$$ time. And subsequently $$$C(x+1)$$$.

Therefore the total time complexity = $$$O(N\times \log(K))$$$.

Pseudocode for Large dataset:

  G[1] = K
  C[1] = A[1] * K * n
  result = C[1]
  for(i in 2 to n){
    // Using the formula derived above to get G[i] from C[i-1]
    G[i+1] = G[i] + i * (i^K - 1) / (i - 1)
    C[i] = G[i] * A[i] * (n - i + 1) 
result = result + C[i] result %= 1000000007 }
Test Data
info We recommend that you practice debugging solutions without looking at the test data.

Statistics — A. Number Guessing

Statistics — B. Mural

Statistics — C. Kickstart Alarm