Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 1107 (Div. 3)
F. A Bit Odd Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes → Virtual participation
Alice and Bob have got a binary∗ string s of length n. They have decided to play a game on it, Virtual contest is a way to take part in past
contest, as close as possible to participation
taking turns alternately, with Alice moving first. on time. It is supported only ICPC mode for
virtual contests. If you've seen these
In each move, the player must select a subsequence† which has an odd number of problems, a virtual contest is not for you -
solve these problems in the archive. If you
inversions‡ and delete it. The player who cannot make a move loses. just want to solve some problem from a
contest, a virtual contest is not for you -
Determine who wins the game, assuming both players play optimally. solve this problem in the archive. Never use
someone else's code, read the tutorials or
communicate with other person during a
∗
A binary string is a string that consists only of the characters 0 and 1 . virtual contest.
†
A sequence a is a subsequence of a string b if a can be obtained from b by the deletion of several (possibly
zero or all) characters. Start virtual contest
‡
An inversion in a binary string s is a pair of indices (i, j) such that i < j and si = 1 and sj = 0 .
Input
→ Problem tags
The first line contains a single integer t (1
4
≤ t ≤ 10 ) — the number of test cases.
Description of each test case follows.
data structures games greedy math
No tag edit access
The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10
5
) — the length of
the binary string s .
→ Contest materials
The second line of each test case contains a binary string s of length n. It is guaranteed that
each character of s is either 0 or 1. Announcement (en)
It is guaranteed that the sum of n over all the test cases does not exceed 2 ⋅ 10 .
5
Tutorial (en)
Output
For each test case, print Alice if Alice wins the game and Bob otherwise.
Example
input Copy
3
5
10101
4
0100
6
011001
output Copy
Alice
Alice
Bob
Note
For the first test case, Alice can choose the entire string as it has an odd number of
inversions. Now, Bob is left with an empty string, and he cannot make a move. Thus, Alice
wins.
For the second test case, Alice can choose the subsequence formed by the characters at
indices 1, 2, and 4, i.e., 010. Bob is then left with the character at index 3, namely 0, which
has 0 inversions (an even number). Therefore, Bob cannot choose a subsequence with an
odd number of inversions, so Alice wins.
For the third test case, it can be shown that Bob can guarantee a win irrespective of Alice's
first move.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jul/03/2026 14:56:28UTC+5.5 (h1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by