Sharon's blog

By Sharon, history, 22 months ago,

We got an AI to generate programming problems, after being trained for hundreds of hours on problem 4A. (This is what we used to train it: https://colab.research.google.com/drive/1gWn1uN4cULoDnBJTSGqrUxxao5q3xHeI)

We omitted samples, time limits, and memory limits because they don't make much sense.

Here are the funniest results:

<|title|>
E. Back to the Future
<|time-limit|>
4 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
After escaping from the crashed time machine, Marty McFly was transported to present-time! He landed on the lawn where his damaged car was parked. He was given the coordinates of the car's location x y.
Marty quickly recognized that this car park is located at a distance of 1 meter from the starting position x, and its maximum speed is v. He also noticed that the car's navigation system is malfunctioning. For some inexplicable reason the system tells Marty that the distance between a pair of stationary objects is the sum of the car's speed.
Marty is not able to understand this. Why does the car choose such an arbitrary location. Help Marty.
<|input-specification|>
The first line contains two integers x and y (1 ≤ x, y ≤ 100) — the initial coordinates of Marty's car.
The second line contains a single integer v (0 ≤ v ≤ 100) — the maximum speed of the navigation system.
<|output_specification|>
Print a single integer — the number of stationary objects that will be able to reach the starting position x.


========================

<|title|>
B. Batch Sort
<|time-limit|>
1 second
<|memory-limit|>
256 megabytes
<|problem-text|>
Mikhail and Peter are good friends. They always have a problem to discuss. Masha asked Peter for a graph as a birthday present. Peter gave her the graph. Then he suddenly died. Masha has been trying to construct a graph since, well, he died. She wants to construct a graph like Peter.
Masha has a sequence


========================

<|title|>
E. Marina and a Bit of a Jerkass
<|time-limit|>
1.5 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
While walking down the street Marina saw a huge number of assholes walking in a row. Asshole number i has ai assholes facing him (each of these assholes has a number ai assholes facing him). Marina decided to follow them and start a fight.
She starts walking with her k-th asshat in a row and nicknames him uppercut. Namely, Marina puts her asshat number i, then nick "umac" and nick "x". When she nick "umac" she also removes all the asshat with number ai who is facing her, she also nick "x" and all the asshat with number ai who is facing her in the end.
Now Marina wants to end up with a new asshat asshat. To do this, she nick "x" and nick "y". When she nick "x" she also removes the asshat with number ai who is facing the current asshat.
Even though Marina wants to end up with a new asshat, she worries that people will think she is crazy if and only if she becomes pregnant. So Marina wants to know what is the smallest number of assholes she has to replace or say that she will be okay with the resulting situation.
<|input-specification|>
The first line contains a single integer n (1 ≤ n ≤ 106) — the number of assholes.
Asshole number i is named ai in the input. It is guaranteed that all the assholes are distinct.
<|output_specification|>
Print a single integer — the minimum number of assholes that Marina can replace or say that she will be okay with the resulting situation.


========================

<|problem-text|>
Let's assume that
Find .
<|input-specification|>
The first line contains one integer number $n$ ($2 \leq n \leq 2 \cdot 10^5$).
<|output_specification|>
Print one integer number: the sum of the digits of pi.


========================

<|title|>
E. A Twisty Movement
<|time-limit|>
1 second
<|memory-limit|>
256 megabytes
<|problem-text|>
A dragon symbolizes wisdom and wealth. On Lunar New Year's Day, people will invoke the dragon once to represent wealth.
A flock of eels symbolizes wisdom and wealth. On Lunar New Year's Day, people will invoke the dragon once to represent wisdom.
A tiger symbolizes innocence and strength. On Lunar New Year's Day, people will invoke the tiger once to represent strength.
None of the eels is a virgin, so when the dragon says "Lala la la la," she should immediately turn her back to the dragon.
The dragon will say "AaA" (Arabic root of  - 1) if he saw some of her shining red spots on the Day. Aa means Red spot.
You will be given q events of one of the following types:
Namely, let's say the position of the eels at the moment of time 0. Let's say that the location of the i-th eel is considered to be a rectangle with vertices at the points (0, 0), (100, 0), (100, ∞). The Dragon will say that the i-th eel is at the point with coordinates (xi, 0). Then he will then say that he will move to this point with speed v1, and will move to the point with coordinates (0, ∞). The Dragon will say that a beautiful girl named Lala appears at this point with speed v2. From the position of the eels at the moment of time 0, he will then say that he will fly to the point with coordinates (xi, yi).
The speed of the dragon is equal to the distance he has traveled in the corresponding direction. The moment of time 0 will be integer. It is guaranteed that the dragon will not be angry and will fly to exactly the point with the coordinates ( - 1, 0), where he will hide.
Lala is a very friendly dragon, so she will gladly fly to any point with integer coordinates, even 0. However, she hates close calls, so if the dragon calls her while flying to some point with integer coordinates she will promptly turn him


========================

<|title|>
Vasya's Revenge
<|time-limit|>
1 second
<|memory-limit|>
256 megabytes
<|problem-text|>
Vasya likes to play his own version of the game. He plays a board on a table. Players move in turns, the player who can move first moves first.
The board has n rows numbered from left to right. The cells of the board are numbered from left to right, and the rows are numbered from left to bottom. Each cell is represented by a number from 1 to n, inclusive.
Vasya is playing a game. There are m characters on the board, each character is either "A", "E", or "U". The board has a left cell (the character "A") and a right cell (the character "E") (not necessarily distinct).
In his turn, Vasya moves to the cell (x, y) and plays a card. He can play a card from the cell (x, y) to the cell (x, y + 1).
You have to make as few cards as possible in your turn. You can put a card anywhere on the board, but it can't be placed on the cell (x, y).
Vasya is allowed to play cards from the board without paying a cost, but he is not allowed to play cards from the board on the table.
Consider that there are m cards in the deck. Vasya has an empty hand. Vasya can't play any cards from the deck.
Vasya's hand contains only two cards, the first card is card "E", the second card is card "U". Vasya can play any of his cards (he can't play any other card).
Vasya's opponent is playing a game. Here is how the game is played.
In the game, Vasya plays two cards. First Vasya plays a card with the character (n, w). Then Vasya plays a card with the character (m, w). Vasya's opponent plays a card with the character (k, m). Vasya can play the first card at any cell (x, y). Vasya can't play the second card.
Vasya's opponent has an empty hand. Vasya can play any card from the opponent's hand.
Your task is to determine whether Vasya's opponent can play any cards from the opponent's hand.
<|input-specification|>
The first line contains a single integer m (1 ≤ m ≤ 105) — the number of cards in Vasya's opponent's hand. The second line contains m integers x, y (1 ≤ x, y ≤ 106), where x and y are the cell numbers on the left and the right side of the board.
The third line contains a single integer w (1 ≤ w ≤ 106) — the number of cards in Vasya's opponent's hand. The fourth line contains w integers x1, y1 (1 ≤ x1, y1 ≤ 106), where x1 and y1 are the cell numbers on the top and the bottom of the board.
<|output_specification|>
Print "YES", if Vasya's opponent can play any cards from the opponent's hand. Otherwise, print "NO".


The most "solvable" problems:

<|title|>
A. Palindrome
<|time-limit|>
2 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
You are given a string $t_1, t_2, \dots, t_n$, consisting of lowercase Latin letters.
A substring of some string $s$ is called a palindrome if it reads the same from left to right and from right to left.
For example, the strings "asdf" and "klm" are palindromes, while the strings "abb" and "iq" are not.
If $t_i = t_{i+1}$ and $r_i = t_{i+2}$ then the string $s$ is a palindrome, but the string $t_j = q_{i+1}$ is not a palindrome.
For example, the strings "aaa", "arctg", "arudg" are not palindromes, while the strings "abacaba", "jjw". and "xzy" are.
Your task is to calculate the number of non-empty substrings of $t_i$ that are palindromes.
<|input-specification|>
The first line contains a single integer $n$ ($1 \le n \le 500$) — the length of the string $t_i$.
The second line contains the string $t_i$ itself, consisting of $n$ lowercase Latin letters.
<|output_specification|>
Print a single integer — the number of non-empty substrings of $t_i$ that are palindromes.


==============

<|title|>
E. Primes and Multiplication
<|time-limit|>
2 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
Seyyed an integer sequence s1, s2, ..., sn of length n and m queries on it. Each query is represented by two integers li, ri (1 ≤ li ≤ ri ≤ n) and a integer x (0 ≤ x ≤ 1018).
After each query you need to calculate the maximum value of an expression which can be found in the sequence s. In this problem expression means the remainder of division of number x by number s.
<|input-specification|>
The first line of the input contains integer n (1 ≤ n ≤ 105) — the length of the sequence s.
The second line contains n integers s1, s2, ..., sn (0 ≤ si ≤ 1018).
<|output_specification|>
Print m lines. For each query, print the maximum value of an expression that can be found in the sequence s after the corresponding query.


==============

<|title|>
A. Three Friends
<|time-limit|>
2 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
Three friends, Alan, Bob and Carol are good friends. That's why, if someone is not nice to Bob, he likes it. If someone is not nice to Carol, she hates it. And if someone is not nice to Alan, she hates it.
You are given a list of the preferences of each friend. Determine if Bob is going to be upset by the news. If he is going to be upset, find the number of those friends who are going to be upset. Bob is going to be upset if only these friends are nice to him. Otherwise, no one is upset.
<|input-specification|>
The first line contains a single integer n (3 ≤ n ≤ 5·105) — the number of friends.
<|output_specification|>
Print the list of friends who are going to be upset by the news. If Bob is going to be upset, print -1.


==============

<|title|>
C. Number representation
<|time-limit|>
4 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
You are given a sequence of integers a1, a2, ..., an.
Your task is to perform the following operation k times: take any two different subsequences (of unequal length) in the given order and swap their contents. After each operation, you need to calculate the total number of times the sequence is modified.
<|input-specification|>
The first line contains one integer n (1 ≤ n ≤ 105) — the length of the sequence. The second line contains n integers a1, a2, ..., an (|ai| ≤ 109).
<|output_specification|>
Print n numbers — the modified sequence after k swaps.


We hope you enjoyed. If you run out of problem ideas and need to write a contest, I suggest you use this method of generating problems.

• +250

 » 22 months ago, # |   +33 That last problem is actually really good. Given a sequence of integers, you can perform a bunch of queries where each query is swapping two non-intersecting ranges (not necessarily of the same size), and you want to count how many strings you have seen after each query.So for example if your string was 'abacaba' and you wanted to swap range [1, 2] with [4], afterwards you would have string 'caababa'. You want to know, after you get each new string, whether you have seen it before. Queries are cumulative; the second query for the example above would be swapping characters of 'caababa', not of 'abacaba'.I have a (Q+N)*log(n) solution, left as an exercise to the reader to discover.
•  » » 22 months ago, # ^ |   +3 Spoilertreap + hashing?
•  » » » 22 months ago, # ^ |   +8 Exactly what I was thinking
 » 22 months ago, # | ← Rev. 3 →   +3 <|title|> B. Batch Sort <|time-limit|> 1 second <|memory-limit|> 256 megabytes <|problem-text|> Mikhail and Peter are good friends. They always have a problem to discuss. Masha asked Peter for a graph as a birthday present. Peter gave her the graph. Then he suddenly died. Masha has been trying to construct a graph since, well, he died. She wants to construct a graph like Peter. Masha has a sequenceRIP task, Peter, Masha.I am just curious how many days will it take to generate perfect results?