Replay of AUSTPIC Presents Intra AUST

Programming Contest - Spring 2025

Problem Set
A. Water Supply Network
Time: 1 s
Memory: 128 MB

An agricultural zone has n water treatment plants. Due to a rigid pipe infrastructure, each plant is
connected to exactly two other plants via one-way pipes. The regional board wants to ensure maximum
resilience: if any plant faces a shortage, water should be able to flow to it from any other plant in the zone.
This requires reconfiguring the network. The network infrastructure is built as a single large loop connecting
all plants, though some of the one-way pipes may currently point in different directions. Changing the flow
direction of a pipe costs a specific amount of budget. What is the minimum cost to adjust the network so
that a valid path exists between every pair of plants?

Input

The first line contains an integer n — the number of water plants. Each of the next n lines contains three
integers
ai , bi , and ci , representing a one-way pipe from plant ai to plant bi with a redirection cost of ci .

Constraint
3 ≤ n ≤ 100
1 ≤ ai , bi ≤ n

ai ≠ bi

1 ≤ ci ≤ 100

Output
Output a single integer representing the minimum cost to redirect the pipes, ensuring full connectivity
between all plants.

Examples
Input Output
6 39
154
538
2 4 15
1 6 16
2 3 23
4 6 42

Input Output
4 0
128
237
346
414

Notes
To clarify, 'redirecting' means reversing the flow direction of a one-way pipe.
B. Maximum Valid Score
Time: 1.5 s
Memory: 512 MB

You are given N strings S1 , S2 , … , SN , each with an associated integer value A 1 , A 2 , … , A N , where
A i represent the score of Si .

A valid subsequence of a sequence of strings is defined as a non-empty subsequence† chosen from

the sequence such that if the chosen strings are concatenated in order, the resulting string forms a
palindrome††.

You have to determine if you can select a valid subsequence from the given strings. If so, you need to find
the maximum sum of scores from all valid subsequences.

Formally, you have to choose k indices i1 < i2 < ⋯ < ik such that Si
1
+ Si
2
+ ⋯ + Si
k
forms a
k
palindrome and ∑j=1 A j is maximized; or report that the selection is not possible.

† A sequence a is a subsequence of a sequence b if a can be obtained from b by the deletion of several

(possibly, zero or all) elements from arbitrary positions.

†† A palindrome is a sequence of characters that reads the same forward and backward, such as "racecar"
or "madam".

Input
The first line of the input contains a single integer T (1 ≤ T ≤ 100) , denoting the number of test cases.
Each test case starts with one integer N (1 ≤ N ≤ 100), the number of strings. Then N lines follow.
5 5
The ith line contains a string Si (1 ≤ |Si | ≤ 10) and an integer A i (−10 ≤ A i ≤ 10 ) serparated by
a space.
Si contains only lowercase Latin letters.

Output
For each test case, print the output on a new line.
If there is no valid subsequence, print "impossible" (without quotes).
Otherwise, print the maximum score you can obtain from all valid subsequences.

Examples
Input Output
3 4
3 impossible
ma 1 -60
dam 2
am 3
3
jibone 6
hexa 6
dekha 6
5
abcd -10
dc -20
xy -40
 Input Output
ba -30
yx -60

Notes
First case:
There are two valid subsequences:

1. Strings 1, 2 forming madam with score 1 + 2 = 3

2. Strings 1, 3 forming madam with score 1 + 3 = 4 .

Among them, 4 is the maximum.

Second case:
It can be shown that it is not possible to choose a valid subsequence.

Third case:
There are two valid subsequences:

1. Strings 1, 2, 4 forming abcddcba with score (-10)(−10) + (−20) + (−30) .

= −60

2. String 3, 5 forming xyyx with score (−40) + (−60) = −100 .

Among them, −60 is the maximum.

C. Greedy Impholi
Time: 1 s
Memory: 128 MB

You are given a positive integer N . Your task is to construct an array of positive integers that satisfies the
following conditions:

The sum of all elements in the array is exactly N .

All elements are distinct and strictly positive.
The length of the array is maximized.

If multiple arrays achieve the maximum possible length, output the lexicographically largest one.

[Note: An array X is lexicographically larger than an array Y of the same length if, at the first position
where they differ, the element in X is greater than the corresponding element in Y .]

Input

The only line of input contains a single integer N .

Constraint
10
1 ≤ N ≤ 10

Output
Output two lines:
On the first line, print a single integer K representing the maximum possible length of the array.
On the second line, print K space-separated integers representing the elements of the lexicographically
largest valid array.

Examples
Input Output
2 1
2

Notes

Explanation: The maximum number of distinct positive integers that sum to 2 is 1. We cannot use an array
of length 2 like [1, 1] because the elements must be distinct. Therefore, the maximum length is 1, and the
array is just [2].
D. Sorting Game (Easy Version)
Time: 2 s
Memory: 128 MB

[This is the easy version of the problem. The difference between the versions is that in this version, the
board is fixed (no modifications allowed), you only need to answer queries, and the number of queries can
be higher.]

Alice and Bob are playing a small board game. Alice writes all integers from 1 to 1000000 on the board,
and Bob wants to sort them using a strange rule based on divisors to make the game interesting.

For any integer x , let d(x) be the number of positive divisor of x . For example 12 has divisors
1, 2, 3, 4, 6, 12. Bob sorts the numbers from 1 to 1000000 using the following rule:

A number x comes before y if:

1. d(x) < d(y), or

2. d(x) = d(y) and x > y (if two numbers have the same number of divisors, the larger number
comes first).

After Bob finishes sorting the list once, Alice asks q queries. For each query, Alice gives a number n ,
and Bob must tell the nth number in this sorted order.

Input
The first line contains an integer q (1 ≤ q ≤ 10
5
), the number of queries.
Each of the next q lines contains an integer n (1
6
≤ n ≤ 10 ).

Output
For each query, print a single integer, the nth number in the sorted order.

Examples
Input Output
3 1
1 999983
2 720720
1000000
E. Sorting Game (Hard Version)
Time: 8 s
Memory: 512 MB

[This is the hard version of the problem. The difference between the versions is that in this version, the
board can be modified dynamically with add and remove operations, and the number of operations is
limited.]

Alice and Bob are playing a small board game. Alice writes all integers from 1 to N on the board, and Bob
wants to sort them using a strange rule based on divisors to make the game interesting.

For any integer x , let d(x) be the number of positive divisor of x . For example 12 has divisors
1, 2, 3, 4, 6, 12 so d(12) = 6. Bob sorts the numbers from 1 to N using the following rule:

A number x comes before y if:

1. d(x) < d(y), or

2. d(x) = d(y) and x > y (if two numbers have the same number of divisors, the larger number
comes first).

However, during the game, Alice can modify the board. She can remove numbers or add any number
(within range), and after each modification, Bob must re-sort the remaining numbers according to the same
rule.
Alice performs Q operations of three types:

Type 1 : Remove a number from the board

Type 2 : Add any number to the board (can add duplicates or numbers not currently present)
Type 3 : Query the nth number in the current sorted order.

Input

The first line contains two integers N and Q (1 ≤ N ≤ 10 , 1 ≤ Q ≤ 10 ) :

6 5

N : the valid range of numbers ( 1 to N )

Q : the number of operations

The next Q lines contain operations in one of three formats:

1 x : Remove one occurrence of number x from the board (1 ≤ x ≤ N ) . If x is not on the board, do
nothing.
2 x : Add number x to the board (1 ≤ x ≤ N ) - can create duplicates

3n : Query the nth number in the current sorted order (1 ≤ n ≤ current board size).

Output
For each Type 3 query, print a single integer: the nth number in the current sorted order.

Examples
Input Output
55 1
31 5
24 5
32
13
32
F. Félix's Dominance
Time: 2 s
Memory: 256 MB

In the late 1980s, The Gentlemen of Cali—Gilberto Rodríguez, Miguel Rodríguez, Pacho Herrera, and José
Santacruz met with Félix Gallardo and Amado Carrillo in Guadalajara, Mexico, to coordinate their business
operations.

Félix Gallardo planned to monopolize Cali’s entire business through centralized control. The Gentlemen of
Cali, however, presented Félix with a challenge to test his tactical mind. Each of the four Cali members
gave Félix a string consisting of lowercase Latin letters. Let these strings be
S1 , S2 , S3 and S4 .

.
Félix will perform the following sequence of operations:

1. From each string Si , he can choose a subsequence (by removing zero or more characters while
preserving the relative order of the remaining characters). A subsequence can also be completely
empty.
2. He then concatenates these four subsequences in any order of his choosing to form a single merged
string T ,

Félix wants to assert his dominance by finding the maximum-length distinct string T
that is lexicographically smallest. Help Félix find this optimal string.

[Note: A string A is lexicographically smaller than a string B if at the first position where they differ, the
character in A comes earlier in the alphabet than the character in B
A string S is called a subsequence of a string T , if S can be obtained from T by deleting zero or more
characters without changing the order of the remaining characters.]

Input
The input consists of exactly four lines.

The ith line (1 ≤ i ≤ 4) contains a non-empty string Si consisting only of lowercase Latin letters.

The length of each string satisfies (1 ≤ |S i| ≤ 1000). .

Output

Print a single line containing the lexicographically smallest distinct string T that Félix can form.

Examples
Input Output
acb abcd
abc
cba
abd

Input Output
pab aresclopb
lo
 Input Output
esco
bar

Input Output
b brzsup
rz
s
up

Notes
In the first example, the maximum possible length is 4, using all distinct available characters {'a', 'b', 'c', 'd'}.
Félix can obtain the string "abcd" by selecting the subsequence "abc" from S2 and the subsequence "d"
from S4 , while leaving S1 and S3 empty. Concatenating the selected subsequences in the order
S2 + S4 produces "abcd", which is the lexicographically smallest valid distinct string of maximum length.

In the second example, the maximum possible length is 9, using all distinct available characters {'a', 'b', 'c',
'e', 'l', 'o', 'p', 'r', 's'}. To achieve this length while preserving the relative order of characters within each
source string, Félix selects the subsequence "pb" from S1 , "lo" from S2 , "esc" from S3 , and "ar" from S4 .
Concatenating these subsequences in the order S4 + S3 + S2 + S1 yields "ar" + "esc" + "lo" + "pb" =
"aresclopb", which is the lexicographically smallest valid distinct string of maximum length 9.
G. Four Glorious Years
Time: 1 s
Memory: 64 MB

On Spring 2021, a group of passionate students at Ahsanullah University of Science and Technology sat
together in a small room and wrote three words on a whiteboard that would change everything:

Learn(); Code(); Conquer();

Those three words grew into something bigger. A community. A legacy. A club. Today, IAPC Spring 2025 is
being held in grand celebration of that very founding moment 4 glorious years later.

To mark the occasion, Rakib the proud president lights candles on the anniversary cake, one for each year.
As each candle is lit, everyone in the room chants the club's full name aloud.

Your job? Join the celebration and say the chant with [Link] name written on the very first page of
the club's founding document reads: "We, the founding members, hereby establish the AUST
Programming and Informatics Club, dedicated to the growth of programming in our university and
beyond."

Input
The universe already knows what tonight is. No input is needed, the occasion speaks for itself.

Output
Let the hall echo. Print the chant of the night as many times as the candles burn bright. Not one chant
more. Not one chant less. Print each chant on a new line, separating the words with a single space. You
may use any combination of uppercase or lowercase letters.
H. Rag korla?
Time: 2 s
Memory: 128 MB

8
Hamza has an array a1 , a2 , … , an of n integers, where 2 ≤ ai ≤ 10 .

He will give you q queries. Each one gives a segment [l, r] , and Hamza wants the smallest integer
x ≥ 2 that meets both of the following conditions:

gcd(x, ai ) = 1 for every i with l ≤ i ≤ r, and

gcd(x, aj ) > 1 for at least one j with 1 ≤ j < l or r < j ≤ n .

For each query, print this smallest x . If no such value exists, then print "rag korla?"(without quotation)

Input
The first line contains n and q (1 ≤ n ≤ 10 , 1 ≤ q
5
≤ 100). The second line contains a1 … an . Each
of the next q lines contains two integers l and r(1 ≤ l ≤ r ≤ n).

Output
Print q lines, the answer to each query.

Examples
Input Output
53 7
6 10 15 7 22 3
13 rag korla?
45
15
I. The Magical Bitwise Quest
Time: 2 s
Memory: 128 MB

In the kingdom of Bitland, there exist three magical runes in an ancient scroll: P , Q, and R. These runes
hold the secret to awakening the legendary Bitwise Guardians: X, Y , and Z .
Your mission is to uncover whether there exist three non-negative integers and such that:

1. The magical bond between X and Y equals P (X&Y = P ).

2. The mystical link between Y and Z equals Q (Y &Z = Q).
3. The hidden connection between X and Z equals R (X&Z = R) .

Here, the & symbol represents the Bitwise AN D operation, a powerful force that combines numbers at
the level of their binary digits.
If such numbers exist, you must find any valid triple (X, Y , Z ) that satisfies all three magical conditions. If
no such numbers exist, the scroll whispers a single secret: −1.
[Note: The Bitwise AN D operator (&) compares two numbers bit by bit. For each bit position, it outputs
1 only if both corresponding input bits are 1. If either bit (or both) is 0, the output is 0. For example,
510 & 410 = 1012 & 1002 = 1002 = 410 ( here,A 10 and A 2 denote the decimal and binary
representation of the integer A , respectively).]

Input
The first line contains a single integer t - the number of test cases (1
6
≤ t ≤ 10 ) .
Each of the next lines three non-negative integers and
9
t P , Q, R (0 ≤ P , Q, R ≤ 10 ) - three magical
runes.

Output
For each test case, output exactly one line:
If there exist non-negative integers X, Y , Z then print any valid triple (X, Y , Z ) (three integers
31
separated by spaces). The printed values must satisfy the range constraint: 0 ≤ X, Y , Z < 2 .
If multiple valid triples exist, you may print any one of them. Otherwise, if no such triple exists, print a single
line containing −1.

Examples
Input Output
2 111
111 -1
4 8 12
J. Friends of Friends
Time: 1 s
Memory: 256 MB

Sajid, a student of AUST, knows recently about a popular social media platform called Beta. He is an active
user of that platform. The students of AUST have been using Beta recently. Every student at the university
uses that platform. Beta has different options for sharing posts with specific audiences, such as Public,
Friends, Custom, and Friends of Friends.

Though all users of Beta are not treated equally. Users are rated based on their engagement on the
platform. Each user has a certain number of rating points internally. On Beta, 'Friends of Friends' includes
everyone connected to a user either directly or through several connections (i.e., if User A , is friends with
User B , B is friends with User C , and so on, then User A is connected to User C ).

Sajid is the best user of Beta platform for 3 months and that’s why the platform owner wants to give him a
gift. He gets a Beta log that records direct friendship relationships, showing who is friends with whom, and
also the internal rating points of each user. He will get the gift, if he can answer the question platform owner
asks.

The owner wants to know the total rating points of each user's Friends-of-Friends on the Beta platform.
Sajid is dumb at calculating things. Help him!

Input
The first line contains two integers N and M (2 ≤ N ≤ 10 , 1 ≤ M ≤ 10 ) where N denotes the
5 5

number of users on the Beta platform and M denotes the number of friendship relationship.
The second line contains N integers a1 , a2 , … , an (0 ≤ ai ≤ 10 )− denoting a friendship between
9

pi
th
and qi th user.

Output
Output n space-separated integers, where each integer represents the total rating points of Friends of
Friends for each user.

Examples
Input Output
53 54354
12345
12
13
45
K. The Front Face
Time: 2 s
Memory: 256 MB

As the front face of his club, Fatin carries the event on his shoulders, and right now the event needs
money. Sponsorships. He's decided it's his utmost duty to walk into every office in town, shake every hand,
and bring back enough funding to make this the club's proudest moment.

The problem? His team is tiny. A handful of people, a stack of business cards, and a calendar that's filling
up fast.

Fatin runs his club's sponsorship drive. He has found n sponsors, numbered 1 … n. Sponsor i is willing to
donate ai taka but the representative is only in town through month bi . Fatin must meet sponsor i in some
month t with 1 ≤ t ≤ bi , otherwise that donation is lost forever.

Fatin's team is small: in any single month they can hold at most y meetings. Each sponsor is met at most
once.

The club also runs a loyalty program. If Fatin closes exactly K sponsors over the whole drive, the program
adjusts his total by a fixed amount BK (a bonus if positive, an administrative cost if negative). The values
B 0 , B 1 , … , B n are given.

Fatin wants to maximize (total donations from the sponsors he meets) + BK , where K is the number of
sponsors he meets.

Input
The first line contains an integer n.
The second line contains n integers a1 , a2 , … , an (the donation amounts).
The third line contains n integers b1 , b2 , … , bn (the last month each sponsor is available).
The fourth line contains an integer y (the maximum number of meetings per month).
The fifth line contains n + 1 integers B0 , B1 , … , Bn (the loyalty adjustment for closing exactly K
sponsors).

Constraint
5
1 ≤ n ≤ 3 × 10
9
0 ≤ ai ≤ 10

1 ≤ b ≤ n
4
0 ≤ y ≤ 10
5 15
−10 ≤ B K ≤ 10 for every K from 0 to n.

Output
Print a single integer: the maximum achievable value of (donations of the sponsors Fatin meets) + BK .
The answer may be negative; meeting nobody is allowed and gives B0 .

Examples
 Input Output
5 120
10 20 30 40 20
12341
5
000000

Input Output
5 1090
10 20 30 40 20
12341
5
0 0 0 1000 -1000 -1000

Notes
Example 1.
With y = 5 the team can hold up to 5 meetings per month, so every sponsor can be met. All loyalty
adjustments are 0, so Fatin collects everyone: 10 + 20 + 30 + 40 + 20 = 120

Example 2. y = 5 again, so all sponsors are schedulable. The best money from closing exactly
K sponsors is S0 … S5 = 0, 40, 70, 90, 110, 120. . With the loyalty adjustments, K = 3 gives
90 + 1000 = 1090, which beats K = 5 's 120 − 1000 = −880 and every other K . So Fatin

deliberately closes only his 3 most valuable sponsors (40, 30, 20).
L. FIFA World Cup 2026 Ticket Distribution
Time: 2 s
Memory: 128 MB

The FIFA World Cup final 2026 is approaching, and millions of fans have registered for tickets. To reward
loyal supporters, FIFA has introduced a special VIP rewards program.

Each registered fan has accumulated a certain number of loyalty points based on their attendance at
previous matches, participation in fan events, and engagement with FIFA activities. The loyalty points of the
fans are given as an array a of n integers, where ai represents the loyalty of the ith fan.

To organize a special VIP event, FIFA decides to introduce a VIP cutoff score H . Any fan whose loyalty
points exceed H will contribute their excess points to a shared VIP reward pool.
Specifically, for each fan i :

If ai > H , they contribute (ai − H ) points to the pool.

If ai ≤ H , they contribute 0 points.

FIFA needs to collect exactly K VIP reward points to unlock the special event. Your task is to determine the
non-negative smallest VIP cutoff score H such that the total contributed points are exactly equal to K . If it
is impossible to collect exactly K points, output −1.

Input
The first line contains a single integer t(1 ≤ t ≤ 10) the number of test cases.
12
The first line of each test case contains two integers n and K (1 ≤ n ≤ 10 ; 0 ≤ K ≤ 10 ) the
5

number of fans and the exact number of VIP reward points required, respectively.
The second line of each test case contains n integers a1 , a2 , … , an (0 ≤ ai ≤ 10 ) the loyalty points of
9

each fan.

Output
For each test case, output a single integer, the non-negative smallest integer VIP cutoff score H that
results in exactly K contributed points. If no such integer cutoff score exists, output −1.

Examples
Input Output
2 3
54 -1
23624
45
1234
M. Grand Archive of Algora
Time: 2 s
Memory: 256 MB

After the historic layout mix-up in the Kingdom of Algora, the Grand Mage Council decided to simplify the
magic categorization rules. Instead of a complex, branching Category Tree, they have instituted a linear
hierarchy of Security Clearance Levels ranging from 0 to M − 1 where 0 is the lowest public access level
and M − 1 is the highest restricted level.

The apprentice archivist, Bob, was tasked with assigning a security level to each of the N interconnected
rooms in the Grand Archive. The archive is built as a tree structure of rooms, rooted at the main entrance
Room 0.

The Validation Rule: To prevent lower-level students from accidentally wandering into restricted areas, the
Council enforces a strict security gradient: For any room U that is the immediate parent of room V , the
security level of room U must be less than or equal to the security level of room :

Level(U ) ≤ Level(V )

Predictably, Bob has completely botched the assignments. Rooms deep in the archive have been given
public access codes, while the entrance room has been locked down with high-level security clearances. To
fix a room's security level, Bob must expend 1 unit of mana to rewrite the magical door runes. He
can change a room's initial level to any integer level between 1 to M − 1 .

Help Bob find the minimum total units of mana . required to alter the room levels such that the entire Grand
Archive satisfies the validation rule.

Input
The first line contains two integers N and M (1 ≤ N ≤ 105 , 1 ≤ M ≤ 500) — the number of rooms in
the archive and the total number of available security levels, respectively.

Each of the next N − 1 lines contains two integers U and V , indicating that room U is the immediate
parent of room V . Room 0 is always the root.

The final line contains N integers a0 , a1 , … , an−1 (0 ≤ ai ≤ m − 1) where ai represents the intial
security level Bob assigned to room i .

Output
Print a single integer representing the minimum units of mana required to make the tree valid.

Examples
Input Output
33 1
01
02
200

Input Output
54 2
01
02
13
Input Output
14
31202