Competition Details

• Duration: 3 hours
• Start Time: 2026/1/30 8:00
• End Time: 2026/1/30 11:00
• Difficulty Level: High
• Final Score: 340
• Lost Points: 60

Problem Set

Problem 1: Element Removal Sum

Description

Given a sequence of integers A of length N and an integer M, determine if it's possible to remove exactly one element from A such that the sum of the remaining N-1 elements equals M.

Input Format

First line contains two integers N and M.
Second line contains N integers representing the sequence A.

Output Format

Output "Yes" if such a removal exists, otherwise output "No".

Sample Input 1

4 10
3 2 3 4

Sample Output 1

Yes

Sample Input 2

5 16
3 3 4 2 5

Sample Output 2

No

Constraints

• For 40% of data: A_i = 1
• For 100% of data: 2 ≤ N ≤ 100, 0 ≤ M ≤ 10000, 0 ≤ A_i ≤ 100

Solution

Calculate the total sum of the array. For each element, check if the sum minus that element equals M. The time complexity is O(n).

Problem 2: Language Identification

Description

Two languages, Fox and Rabbit, use different sets of characters. Fox language only uses characters from string S, while Rabbit language only uses characters from string T. Given Q words, classify each word as:

• Fox: all characters in the word are in S
• Rabbit: all characters in the word are in T
• Unknown: characters are found in both S and T

Input Format

First line contains two integers N and M (lengths of S and T).
Second line contains string S.
Third line contains string T.
Fourth line contains Q (number of queries).
Next Q lines contain words to classify.

Output Format

For each query, output "Fox", "Rabbit", or "Unknown".

Sample Input

6 5
ahikst
aikot
5
asahi
okita
kiai
hash
it

Sample Output

Fox
Rabbit
Unknown
Fox
Unknown

Constraints

• For 40% of data: N = M = 1
• For 100% of data: 1 ≤ N,M ≤ 26, 1 ≤ Q ≤ 100, word length 1-100

Solution

For each character in a query word, check if it exists in S and/or T. Classify based on the presence of characters in both strings.

Problem 3: Domino Cascade

Description

N dominoes are placed on a number line at positions 1 to N. Each domino at position i has height A_i. When domino i falls to the right, it causes all dominoes from i to i + A_i - 1 to fall. Determine how many dominoes fall when the first domino falls to the right.

Input Format

First line contains integer N.
Second line contains N integers representing the heights A_1 to A_N.

Output Format

Output the total number of dominoes that fall.

Sample Input 1

4
3 1 4 1

Sample Output 1

4

Sample Input 2

9
1 4 1 4 2 1 3 5 6

Sample Output 2

1

Constraints

• For 40% of data: 1 ≤ A_i ≤ 2
• For 100% of data: 1 ≤ A_i ≤ N ≤ 500,000

Solution

Use a greedy approach to track the rightmost falling domino. Initialize the current right boundary and update it as you iterate through the dominoes. The time complexity is O(n).

Problem 4: Dynamic Box Operations

Description

A box starts empty and undergoes Q operations of two types:

• Operation 1: Add a ball with integer x
• Operation 2: Remove a ball with integer x (guaranteed to exist)

After each operation, determine the number of ways to select balls that sum to K. Output the result modulo 998244353.

Input Format

First line contains two integers Q and K.
Next Q lines contain operations of the form "+ x" or "- x".

Output Format

Output Q integers, one after each operation, representing the number of ways to achieve sum K modulo 998244353.

Sample Input

15 10
+ 5
+ 2
+ 3
- 2
+ 5
+ 10
- 3
+ 1
+ 3
+ 3
- 5
+ 1
+ 7
+ 4
- 3

Sample Output

0
0
1
0
1
2
2
2
2
2
1
3
5
8
5

Constraints

• For 40% of data: No removal operations
• For 100% of data: 1 ≤ Q,K,x ≤ 5000

Solution

Use dynamic programming to track the number of ways to achieve each sum. For removal operations, process them in reverse order to maintain the correct state transitions. The time complexity is O(Q*K).