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 kickstart@google.com.
Looking forward to having your participation in upcoming rounds.
If you experience any technical issues interfering with your ability to participate in the Practice Session, please email us immediately at codejam@google.com. 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.
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.
B = 30.
B = 109.
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
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.
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.
2 ≤ N ≤ 100.
For exactly 1 case, N = 5 × 106; for the other T - 1 cases, 2 ≤ N ≤ 100.
4 4 1332 4 9583 3 616 10 1029384756
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.
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:
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:
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.
1 ≤ N ≤ 100.
1 ≤ K ≤ 20.
1 ≤ N ≤ 106.
1 ≤ K ≤ 104.
2 2 3 1 2 1 2 1 1 9 10 10 10001 10002 10003 10004 10005 10006 89273
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:
For i = 2:
For i = 3:
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.
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.
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
a=${line[0]}
b=${line[1]}
read n
head=$(( a+1 ))
tail=$b
while true; do
mid=$(( (head+tail)/2 ))
echo $mid
read s
if [[ "$s" == "CORRECT" ]]; then
break
elif [[ "$s" == "TOO_BIG" ]]; then
tail=$(( mid - 1 ))
elif [[ "$s" == "TOO_SMALL" ]]; then
head=$(( mid + 1 ))
else
# Wrong answer; exit to receive Wrong Answer judgment
exit 0
fi
done
done
#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);
fflush(stdout);
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;
}
else
{
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;
else
tail = m - 1;
}
}
return 0;
}
package main
import (
"fmt"
"strings"
)
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
fmt.Println(m)
var str string
fmt.Scanf("%s", &str)
if strings.EqualFold(str, "CORRECT") {
break
} 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;
System.out.println(m);
String s = input.next();
if (s.equals("CORRECT")) {
return;
} 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(System.in);
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);
console.log(mid);
} 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);
console.log(mid);
}
}
}).on('close',function(){
process.exit(0);
});
<?php
function solve($a, $b) {
$m = ($a + $b) / 2;
printf("%d\n", $m);
fscanf(STDIN, "%s", $s);
if (strcmp($s, "CORRECT") == 0) {
return;
} 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
sys.stdout.flush()
s = raw_input()
if s == "CORRECT":
return
elif s == "TOO_SMALL":
a = m + 1
else:
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
print(m)
sys.stdout.flush()
s = input()
if s == "CORRECT":
return
elif s == "TOO_SMALL":
a = m + 1
else:
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
$stdout.flush
s = STDIN.gets.chomp
if s.eql? "CORRECT"
return
elsif s.eql? "TOO_SMALL"
solve(m + 1, b)
else
solve(a, m - 1)
end
end
t = STDIN.gets.chomp.to_i
ks = 1
while ks <= t
a, b = STDIN.gets.split.map &:to_i;
n = STDIN.gets.chomp.to_i
solve(a + 1, b)
ks = ks + 1
end
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.
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.
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.
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.
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)$$$.
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.
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
}