1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Tavas and Karafs
Contest: Codeforces Round 299 (Div. 2)
Difficulty rating: 1900
Tags: binary search, greedy, math

Karafs is some kind of vegetable in shape of an 1 × h rectangle. Tavaspolis people love Karafs and they use Karafs in almost any kind of food. Tavas, himself, is crazy about Karafs.

Each Karafs has a positive integer height. Tavas has an infinite 1-based sequence of Karafses. The height of the i-th Karafs is si = A + (i - 1) × B.

For a given m, let's define an m-bite operation as decreasing the height of at most m distinct not eaten Karafses by 1. Karafs is considered as eaten when its height becomes zero.

Now SaDDas asks you n queries. In each query he gives you numbers l, t and m and you should find the largest number r such that l ≤ r and sequence sl, sl + 1, ..., sr can be eaten by performing m-bite no more than t times or print -1 if there is no such number r.

Input format:
The first line of input contains three integers A, B and n (1 ≤ A, B ≤ 106, 1 ≤ n ≤ 105).

Next n lines contain information about queries. i-th line contains integers l, t, m (1 ≤ l, t, m ≤ 106) for i-th query.

Output format:
For each query, print its answer in a single line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 1 4
1 5 3
3 3 10
7 10 2
6 4 8

Example output:
4
-1
8
-1

Example input:
1 5 2
1 5 10
2 7 4

Example output:
1
2

Editorial:
Tavas and Malekas
Contest: Codeforces Round 299 (Div. 2)
Difficulty rating: 1900
Tags: greedy, hashing, string suffix structures, strings

Tavas is a strange creature. Usually "zzz" comes out of people's mouth while sleeping, but string s of length n comes out from Tavas' mouth instead.

Today Tavas fell asleep in Malekas' place. While he was sleeping, Malekas did a little process on s. Malekas has a favorite string p. He determined all positions x1 < x2 < ... < xk where p matches s. More formally, for each xi (1 ≤ i ≤ k) he condition sxisxi + 1... sxi + |p| - 1 = p is fullfilled.

Then Malekas wrote down one of subsequences of x1, x2, ... xk (possibly, he didn't write anything) on a piece of paper. Here a sequence b is a subsequence of sequence a if and only if we can turn a into b by removing some of its elements (maybe no one of them or all).

After Tavas woke up, Malekas told him everything. He couldn't remember string s, but he knew that both p and s only contains lowercase English letters and also he had the subsequence he had written on that piece of paper.

Tavas wonders, what is the number of possible values of s? He asked SaDDas, but he wasn't smart enough to solve this. So, Tavas asked you to calculate this number for him.

Answer can be very large, so Tavas wants you to print the answer modulo 109 + 7.

Input format:
The first line contains two integers n and m, the length of s and the length of the subsequence Malekas wrote down (1 ≤ n ≤ 106 and 0 ≤ m ≤ n - |p| + 1).

The second line contains string p (1 ≤ |p| ≤ n).

The next line contains m space separated integers y1, y2, ..., ym, Malekas' subsequence (1 ≤ y1 < y2 < ... < ym ≤ n - |p| + 1).

Output format:
In a single line print the answer modulo 1000 000 007.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample test all strings of form "ioioi?" where the question mark replaces arbitrary English letter satisfy.

Here |x| denotes the length of string x.

Please note that it's possible that there is no such string (answer is 0).

Example input:
6 2
ioi
1 3

Example output:
26

Example input:
5 2
ioi
1 2

Example output:
0

Editorial:
Tavas and Pashmaks
Contest: Codeforces Round 299 (Div. 2)
Difficulty rating: 2600
Tags: geometry, math

Tavas is a cheerleader in the new sports competition named "Pashmaks".

This competition consists of two part: swimming and then running. People will immediately start running R meters after they finished swimming exactly S meters. A winner is a such person that nobody else finishes running before him/her (there may be more than one winner).

Before the match starts, Tavas knows that there are n competitors registered for the match. Also, he knows that i-th person's swimming speed is si meters per second and his/her running speed is ri meters per second. Unfortunately, he doesn't know the values of R and S, but he knows that they are real numbers greater than 0.

As a cheerleader, Tavas wants to know who to cheer up. So, he wants to know all people that might win. We consider a competitor might win if and only if there are some values of R and S such that with these values, (s)he will be a winner.

Tavas isn't really familiar with programming, so he asked you to help him.

Input format:
The first line of input contains a single integer n (1 ≤ n ≤ 2 × 105).

The next n lines contain the details of competitors. i-th line contains two integers si and ri (1 ≤ si, ri ≤ 104).

Output format:
In the first and the only line of output, print a sequence of numbers of possible winners in increasing order.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3
1 3
2 2
3 1

Example output:
1 2 3

Example input:
3
1 2
1 1
2 1

Example output:
1 3

Editorial:
Zebras
Contest: Codeforces Round 469 (Div. 1)
Difficulty rating: 1600
Tags: greedy

Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a zebra, if it starts with a bad day, ends with a bad day, and good and bad days are alternating in it. Let us denote bad days as 0 and good days as 1. Then, for example, sequences of days 0, 010, 01010 are zebras, while sequences 1, 0110, 0101 are not.

Oleg tells you the story of days he lived in chronological order in form of string consisting of 0 and 1. Now you are interested if it is possible to divide Oleg's life history into several subsequences, each of which is a zebra, and the way it can be done. Each day must belong to exactly one of the subsequences. For each of the subsequences, days forming it must be ordered chronologically. Note that subsequence does not have to be a group of consecutive days.

Input format:
In the only line of input data there is a non-empty string s consisting of characters 0 and 1, which describes the history of Oleg's life. Its length (denoted as |s|) does not exceed 200 000 characters.

Output format:
If there is a way to divide history into zebra subsequences, in the first line of output you should print an integer k (1 ≤ k ≤ |s|), the resulting number of subsequences. In the i-th of following k lines first print the integer li (1 ≤ li ≤ |s|), which is the length of the i-th subsequence, and then li indices of days forming the subsequence. Indices must follow in ascending order. Days are numbered starting from 1. Each index from 1 to n must belong to exactly one subsequence. If there is no way to divide day history into zebra subsequences, print -1.

Subsequences may be printed in any order. If there are several solutions, you may print any of them. You do not have to minimize nor maximize the value of k.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Example input:
0010100

Example output:
3
3 1 3 4
3 2 5 6
1 7

Example input:
111

Example output:
-1

Editorial:
Simple greedy works here. Let's go from left to right and assign each element to some subsequence. At each moment we have two types of already built subsequences: zebras ("0", "010", "01010", ...) and "almost zebras" ("01", "0101", "010101"). If next element of the string is '1' we should add it to some zebra making it "almost zebra". If there are no zebras at this moment it's impossible to divide string into zebra subsequences. If next element of the string is '0' we should add it so some "almost zebra" making it simple zebra. If there are no "almost zebra"'s now just create new zebra consisting of this '0'.
If there are no "almost zebra"'s at the end answer exists and built zebras satisfy all requirements otherwise there is no answer.
BONUS (easy): Find answer minimizing length of longest subsequence.
BONUS (hard): Find answer minimizing number of subsequences.
A Leapfrog in the Array
Contest: Codeforces Round 469 (Div. 1)
Difficulty rating: 1700
Tags: constructive algorithms, math

Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored with easy solutions of this problem, and he has come up with the following extravagant algorithm.

Let's consider that initially array contains n numbers from 1 to n and the number i is located in the cell with the index 2i - 1 (Indices are numbered starting from one) and other cells of the array are empty. Each step Dima selects a non-empty array cell with the maximum index and moves the number written in it to the nearest empty cell to the left of the selected one. The process continues until all n numbers will appear in the first n cells of the array. For example if n = 4, the array is changing as follows:

You have to write a program that allows you to determine what number will be in the cell with index x (1 ≤ x ≤ n) after Dima's algorithm finishes.

Input format:
The first line contains two integers n and q (1 ≤ n ≤ 1018, 1 ≤ q ≤ 200 000), the number of elements in the array and the number of queries for which it is needed to find the answer.

Next q lines contain integers xi (1 ≤ xi ≤ n), the indices of cells for which it is necessary to output their content after Dima's algorithm finishes.

Output format:
For each of q queries output one integer number, the value that will appear in the corresponding array cell after Dima's algorithm finishes.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The first example is shown in the picture.

In the second example the final array is [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7].

Example input:
4 3
2
3
4

Example output:
3
2
4

Example input:
13 4
10
5
4
8

Example output:
13
3
8
9

Editorial:
In odd position p value $${ \frac { p + 1 } { 2 } }$$ will be set.
For even position p let's find out position from which value has arrived and iterate over such position until we will arrive to odd position for which we know answer.
At the moment of jumping to cell p there are $$\frac{\pi}{2}$$ elements to the right of the position p. So there are $$n - \frac{p}{2}$$ elements to the right of this position and jump to cell p was done from position $$p + \left( n - \frac{p}{2} \right)$$. During each such jump length of jump decreases at least by 2 times, so there are no more than $${\mathcal {O}}(\log n)$$ jumps and solution works in $${\mathcal{O}}(q\log n)$$.
Game With Sticks
Contest: Codeforces Round 258 (Div. 2)
Difficulty rating: 900
Tags: implementation

After winning gold and silver in IOI 2014, Akshat and Malvika want to have some fun. Now they are playing a game on a grid made of n horizontal and m vertical sticks.

An intersection point is any point on the grid which is formed by the intersection of one horizontal stick and one vertical stick.

In the grid shown below, n = 3 and m = 3. There are n + m = 6 sticks in total (horizontal sticks are shown in red and vertical sticks are shown in green). There are n·m = 9 intersection points, numbered from 1 to 9.

The rules of the game are very simple. The players move in turns. Akshat won gold, so he makes the first move. During his/her move, a player must choose any remaining intersection point and remove from the grid all sticks which pass through this point. A player will lose the game if he/she cannot make a move (i.e. there are no intersection points remaining on the grid at his/her move).

Assume that both players play optimally. Who will win the game?

Input format:
The first line of input contains two space-separated integers, n and m (1 ≤ n, m ≤ 100).

Output format:
Print a single line containing "Akshat" or "Malvika" (without the quotes), depending on the winner of the game.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Explanation of the first sample:

The grid has four intersection points, numbered from 1 to 4.

If Akshat chooses intersection point 1, then he will remove two sticks (1 - 2 and 1 - 3). The resulting grid will look like this.

Now there is only one remaining intersection point (i.e. 4). Malvika must choose it and remove both remaining sticks. After her move the grid will be empty.

In the empty grid, Akshat cannot make any move, hence he will lose.

Since all 4 intersection points of the grid are equivalent, Akshat will lose no matter which one he picks.

Example input:
2 2

Example output:
Malvika

Example input:
2 3

Example output:
Malvika

Editorial:
Sort the Array
Contest: Codeforces Round 258 (Div. 2)
Difficulty rating: 1300
Tags: implementation, sortings

Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array a consisting of n distinct integers.

Unfortunately, the size of a is too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the array a (in increasing order) by reversing exactly one segment of a? See definitions of segment and reversing in the notes.

Input format:
The first line of the input contains an integer n (1 ≤ n ≤ 105) — the size of array a.

The second line contains n distinct space-separated integers: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109).

Output format:
Print "yes" or "no" (without quotes), depending on the answer.

If your answer is "yes", then also print two space-separated integers denoting start and end (start must not be greater than end) indices of the segment to be reversed. If there are multiple ways of selecting these indices, print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Sample 1. You can reverse the entire array to get [1, 2, 3], which is sorted.

Sample 3. No segment can be reversed such that the array will be sorted.

Definitions

A segment [l, r] of array a is the sequence a[l], a[l + 1], ..., a[r].

If you have an array a of size n and you reverse its segment [l, r], the array will become:

a[1], a[2], ..., a[l - 2], a[l - 1], a[r], a[r - 1], ..., a[l + 1], a[l], a[r + 1], a[r + 2], ..., a[n - 1], a[n].

Example input:
3
3 2 1

Example output:
yes
1 3

Example input:
4
2 1 3 4

Example output:
yes
1 2

Editorial:
Predict Outcome of the Game
Contest: Codeforces Round 258 (Div. 2)
Difficulty rating: 1700
Tags: brute force, implementation, math

There are n games in a football tournament. Three teams are participating in it. Currently k games had already been played.

You are an avid football fan, but recently you missed the whole k games. Fortunately, you remember a guess of your friend for these k games. Your friend did not tell exact number of wins of each team, instead he thought that absolute difference between number of wins of first and second team will be d1 and that of between second and third team will be d2.

You don't want any of team win the tournament, that is each team should have the same number of wins after n games. That's why you want to know: does there exist a valid tournament satisfying the friend's guess such that no team will win this tournament?

Note that outcome of a match can not be a draw, it has to be either win or loss.

Input format:
The first line of the input contains a single integer corresponding to number of test cases t (1 ≤ t ≤ 105).

Each of the next t lines will contain four space-separated integers n, k, d1, d2 (1 ≤ n ≤ 1012; 0 ≤ k ≤ n; 0 ≤ d1, d2 ≤ k) — data for the current test case.

Output format:
For each test case, output a single line containing either "yes" if it is possible to have no winner of tournament, or "no" otherwise (without quotes).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Sample 1. There has not been any match up to now (k = 0, d1 = 0, d2 = 0). If there will be three matches (1-2, 2-3, 3-1) and each team wins once, then at the end each team will have 1 win.

Sample 2. You missed all the games (k = 3). As d1 = 0 and d2 = 0, and there is a way to play three games with no winner of tournament (described in the previous sample), the answer is "yes".

Sample 3. You missed 4 matches, and d1 = 1, d2 = 0. These four matches can be: 1-2 (win 2), 1-3 (win 3), 1-2 (win 1), 1-3 (win 1). Currently the first team has 2 wins, the second team has 1 win, the third team has 1 win. Two remaining matches can be: 1-2 (win 2), 1-3 (win 3). In the end all the teams have equal number of wins (2 wins).

Example input:
5
3 0 0 0
3 3 0 0
6 4 1 0
6 3 3 0
3 3 3 2

Example output:
yes
yes
yes
no
no

Editorial:
Count Good Substrings
Contest: Codeforces Round 258 (Div. 2)
Difficulty rating: 2000
Tags: math

We call a string good, if after merging all the consecutive equal characters, the resulting string is palindrome. For example, "aabba" is good, because after the merging step it will become "aba".

Given a string, you have to find two values:

1. the number of good substrings of even length;
2. the number of good substrings of odd length.

Input format:
The first line of the input contains a single string of length n (1 ≤ n ≤ 105). Each character of the string will be either 'a' or 'b'.

Output format:
Print two space-separated integers: the number of good substrings of even length and the number of good substrings of odd length.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In example 1, there are three good substrings ("b", "b", and "bb"). One of them has even length and two of them have odd length.

In example 2, there are six good substrings (i.e. "b", "a", "a", "b", "aa", "baab"). Two of them have even length and four of them have odd length.

In example 3, there are seven good substrings (i.e. "b", "a", "b", "b", "bb", "bab", "babb"). Two of them have even length and five of them have odd length.

Definitions

A substring s[l, r] (1 ≤ l ≤ r ≤ n) of string s = s1s2... sn is string slsl + 1... sr.

A string s = s1s2... sn is a palindrome if it is equal to string snsn - 1... s1.

Example input:
bb

Example output:
1 2

Example input:
baab

Example output:
2 4

Editorial:
Devu and Flowers
Contest: Codeforces Round 258 (Div. 2)
Difficulty rating: 2300
Tags: bitmasks, combinatorics, number theory

Devu wants to decorate his garden with flowers. He has purchased n boxes, where the i-th box contains fi flowers. All flowers in a single box are of the same color (hence they are indistinguishable). Also, no two boxes have flowers of the same color.

Now Devu wants to select exactly s flowers from the boxes to decorate his garden. Devu would like to know, in how many different ways can he select the flowers from each box? Since this number may be very large, he asks you to find the number modulo (109 + 7).

Devu considers two ways different if there is at least one box from which different number of flowers are selected in these two ways.

Input format:
The first line of input contains two space-separated integers n and s (1 ≤ n ≤ 20, 0 ≤ s ≤ 1014).

The second line contains n space-separated integers f1, f2, ... fn (0 ≤ fi ≤ 1012).

Output format:
Output a single integer — the number of ways in which Devu can select the flowers modulo (109 + 7).

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
Sample 1. There are two ways of selecting 3 flowers: {1, 2} and {0, 3}.

Sample 2. There is only one way of selecting 4 flowers: {2, 2}.

Sample 3. There are three ways of selecting 5 flowers: {1, 2, 2}, {0, 3, 2}, and {1, 3, 1}.

Example input:
2 3
1 3

Example output:
2

Example input:
2 4
2 2

Example output:
1

Editorial:
01 Game
Contest: Educational Codeforces Round 90 (Rated for Div. 2)
Difficulty rating: 900
Tags: games

Alica and Bob are playing a game.

Initially they have a binary string $$$s$$$ consisting of only characters 0 and 1.

Alice and Bob make alternating moves: Alice makes the first move, Bob makes the second move, Alice makes the third one, and so on. During each move, the current player must choose two different adjacent characters of string $$$s$$$ and delete them. For example, if $$$s = 1011001$$$ then the following moves are possible:

1. delete $$$s_1$$$ and $$$s_2$$$: $$$\textbf{10}11001 \rightarrow 11001$$$;
2. delete $$$s_2$$$ and $$$s_3$$$: $$$1\textbf{01}1001 \rightarrow 11001$$$;
3. delete $$$s_4$$$ and $$$s_5$$$: $$$101\textbf{10}01 \rightarrow 10101$$$;
4. delete $$$s_6$$$ and $$$s_7$$$: $$$10110\textbf{01} \rightarrow 10110$$$.

If a player can't make any move, they lose. Both players play optimally. You have to determine if Alice can win.

Input format:
First line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Only line of each test case contains one string $$$s$$$ ($$$1 \le |s| \le 100$$$), consisting of only characters 0 and 1.

Output format:
For each test case print answer in the single line.

If Alice can win print DA (YES in Russian) in any register. Otherwise print NET (NO in Russian) in any register.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case after Alice's move string $$$s$$$ become empty and Bob can not make any move.

In the second test case Alice can not make any move initially.

In the third test case after Alice's move string $$$s$$$ turn into $$$01$$$. Then, after Bob's move string $$$s$$$ become empty and Alice can not make any move.

Example input:
3
01
1111
0011

Example output:
DA
NET
NET

Editorial:
If there is at least one character 0 and at least one character 1, then current player can always make a move. After the move the number of character 0 decreases by one, and the number of character 1 decreases by one too. So the number of moves is always $$$min(c0, c1)$$$, where $$$c0$$$ is the number of characters 0 in string $$$s$$$, and $$$c1$$$ is the number of characters 1 in string $$$s$$$.
So if $$$min(c0, c1)$$$ is odd then Alice wins, otherwise Bob wins.
Pluses and Minuses
Contest: Educational Codeforces Round 90 (Rated for Div. 2)
Difficulty rating: 1300
Tags: math

You are given a string $$$s$$$ consisting only of characters + and -. You perform some process with this string. This process can be described by the following pseudocode:

Note that the $$$inf$$$ denotes infinity, and the characters of the string are numbered from $$$1$$$ to $$$|s|$$$.

You have to calculate the value of the $$$res$$$ after the process ends.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The only lines of each test case contains string $$$s$$$ ($$$1 \le |s| \le 10^6$$$) consisting only of characters + and -.

It's guaranteed that sum of $$$|s|$$$ over all test cases doesn't exceed $$$10^6$$$.

Output format:
For each test case print one integer — the value of the $$$res$$$ after the process ends.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
--+-
---
++--+-

Example output:
7
9
6

Editorial:
Let's replace all + with 1, and all - with -1. After that let's create a preffix-sum array $$$p$$$ ($$$p_i = \sum\limits_{j=1}^{i} s_j$$$). Also lets create array $$$f$$$ such that $$$f_i$$$ is equal minimum index $$$j$$$ such that $$$p_j = -i$$$ (if there is no such index $$$p_i = -1$$$).
Let's consider the first iteration of loop $$$for ~ init ~ = ~ 0 ~ to ~ inf$$$. If $$$f_1 = -1$$$ then process ends and $$$res = |s|$$$. Otherwise the condition $$$if ~ cur ~ < ~ 0$$$ fulfilled then the value of $$$i$$$ will be equal to $$$f_1$$$. So, the value of $$$res$$$ is equal to $$$f_1$$$ after first iteration.
Now, let's consider the second iteration of loop $$$for ~ init ~ = ~ 0 ~ to ~ inf$$$. If $$$f_2 = -1$$$ then process ends and $$$res = f_1 + |s|$$$. Otherwise the condition $$$if ~ cur ~ < ~ 0$$$ fulfilled then the value of $$$i$$$ will be equal to $$$f_2$$$. So, the value of $$$res$$$ is equal to $$$f_1 + f_2$$$ after second iteration.
In this way we can calculate the value of $$$res$$$ after the process ends.