IU Code Trap
D
Programming Contest Fall 2024
Editorial
Problem Setters & Judges:
usha Hasan
E
Mahfuzur Rahman Shanto
Md. Iffatul Islam Anon
Md. Abdul Alim
Arfan Arif
Piyash Basak
Saiful Islam Ramim
Abu Naeem
Ishrak Tawsif Nirob
Aumit Hasan Bappy
Jafrin Iqbal Chowdhury
Rifa Tasfia
Arpita Paul
Tahmina Meem
Mujahidul Islam
Abdul Hye Zebon
Mazbaur Rahid
Mohammad Azam Khan
Problem Name: “The Spirit of July: A Triumph of Student Unity”
Tag: Giveaway
Problem Setter : Saiful Islam Ramim
Tester: Ishrak Tawsif
Just print one line as instructed in the problem.
Problem Name: “Lost Mangos”
Tag: Arithmetic Operation
Problem Setter : Abu Naeem
Tester: Aumit Hasan
Subtract the stolen mangos from the collected mangos -
remaining_mangos=total_mangos−stolen_mangos
This solution runs in O(1) time complexity.
Code:
Problem Name: “Alphabet Battle”
Tag: Conditional
Problem Setter: Eusha Hasan
Tester: Aumit Hasan
his problem revolves around a basic comparison using if-else conditions. Two characters are
T
provided, and the task is to determine which character appears earlier in the English alphabet.
Then do basic if else operation according to the problem statement and print the specific
sentence with adding new line at the end of the line.
Code:
Time Complexity : O(1)
Space Complexity : O(1)
Problem Name: “The Color Allocation Challenge”
Tag: Array
Problem Setter: Zafrin Iqbal chowdhury
Tester: Ishrak Tawsif Nirob
earetaskedwithdeterminingtheminimumnumberofsectionsrequiredtopaintamuralsuch
W
thatnosectioncontainsmorethanonecolorofthesametype.Theproblemboilsdowntofinding
themaximumnumberofidenticalcolorpatchesinthemuralsincethisdeterminestheminimum
number of sections required.
Key Observations:
1. I facertaincoloriappearsA[i]times,atleastA[i]sectionsarerequiredtoensurenotwo
patches of this color overlap in the same section.
2. T he solution is determined bythemaximumvalueamongallA[i]valuesforthegiven
test case.
Code:
Problem Name: “Spiral Triangle”
Tag: Geometry
Problem Setter: Md. Abdul Alim
ester: Md. Iffatul Islam Anon, Mahfuzur Rahman Shanto, Ishrak Tawsif Nirob
T
ditorial:The hypotenuse of the first triangle willbe root 2, the hypotenuse of the second
E
triangle will be root 3.
This will give a pattern that the hypotenuse of the Nth triangle will be root (N + 1)
Problem Understanding
e are given a sequence of right-angled triangles, where the hypotenuse follows a pattern.
W
Specifically:
● The hypotenuse of thefirsttriangle is 2 .
● The hypotenuse of thesecondtriangle is 3 .
T
● he hypotenuse of thethirdtriangle is 4 .
● This pattern continues, and we need to determine a general formula for the hypotenuse
of theNthtriangle.
Observing the Pattern
From the given information, the hypotenuse of the Nth triangle follows the pattern:
Hypotenuse = 𝑁 + 1
Conclusion
y observing the pattern and applying the Pythagorean theorem, we have derived that the
B
hypotenuse of the Nth triangle is given by:
Hypotenuse = 𝑁 + 1
Code:
Problem Name: “PROJECT DEKHAW HACKATHON”
Tag: Math
Problem Setter: Mahfuzur Rahman Shanto
ester: Ishrak Tawsif Nirob, Abdul Alim, Md. Iffatul Islam Anon
T
In this problem participants are assigned to projects based on the Fibonacci sequence where
the number of participants in a project is the sum of the participants in the two preceding
projects. The first two projects in each category start with one participant each.
or example:
F
Project 1: 1 participant
Project 2: 1 participant (0 + 1)
Project 3: 2 participants (1 + 1)
Project 4: 3 participants (1 + 2)
Project 5: 5 participants (2 + 3)
and so on…
Total sum of the participants for all project slots in both categories is the final answer.
xplanation:
E
For, W = 7 and M = 6
Web Development (W = 7):
➢ Project slots: 1, 1, 2, 3, 5, 8, 13
➢ Total participants: 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33
Mobile App Development (M = 6):
➢ Project slots: 1, 1, 2, 3, 5, 8
➢ Total participants: 1 + 1 + 2 + 3 + 5 + 8 = 20
Total participants required: 33 (Web) + 20 (Mobile) = 53
Code:
Problem Name: “Rickception”
Tag: Binary Search
Problem Setter: Ishrak Tawsif Nirob
ester : Aumit Hasan, Saiful Islam Ramim,Piyash Basak
T
Let's break down the solution into three parts -
art 1: Calculating the Required Number of Transmissions
P
To calculate the number of transmissions required for a given packet size M
Transmission required for i th scan =𝑑𝑎𝑡𝑎[𝑖]/𝑀 + (𝑑𝑎𝑡𝑎[𝑖]%𝑀 > 0).
he first term represents the number of full packets required. The second term accounts for any
T
remaining bytes that need an additional packet. If we loop through the T-scanned data to
calculate the number of transmissions required for each scan and then add them all we will get
a total number of transmissions. Compare the total transmissions to the maximum allowed
transmission N. If the total is less than or equal to N, the value of M satisfies the condition.
art 2:Find the minimum value of M
P
If we run a loop to fix the value of M and then check if this M meets the requirement of a
maximum number of transmission limits (See part 1), then the first value that meets the
requirement is our answer.
If we think about the maximum number of M, Iterating through all possible values of M from 1 to
the largest size can take too long, making this approach impractical.
art 3: Using Binary Search
P
Binary search is suitable because:
● All M values greater than or equal to the minimum M satisfy the condition.
● All M values less than the minimum M do not satisfy the condition.
Using binary search select a value of M (mid-point), Use the method fromPart 1to determine if
this M satisfies the condition (total transmissions ≤ N). If it does, narrow the search to the lower
half to find a smaller M. If it doesn’t, narrow the search to the upper half to find a larger M.
ime Complexity:
T
Since we perform a binary search on the value of MMM, the time complexity for the binary
search isO(logM). For each possible MMM, we checkall T-scanned data. Therefore, the total
time complexity isO(T log M).
Code:
Problem Name: “Battle Of Archers”
Tag: Segment Tree
Problem Setter:Piyash Basak
ester: Mujahidul Islam, Saiful Islam Ramim, Anupam Islam Akib
T
The Archer King can issue two commands:
1. Boost Command: Amplify attack power starting at position P with an initial power X,
decaying linearly leftward.
2. Attack Command: Compute the total attack power of archers in a specified range [a, b].
The challenge is to handle these commands efficiently for large constraints (N , Q ≤ 200,000).
Approach:
1. Data Structure:
o Use a Segment Tree with Lazy Propagation to handle range updates and queries
efficiently.
2. Boost Command (Type 1):
o For a command 1 P X, apply a range update from P-X+1 to P:
▪ Uselazy_addfor the base boost.
▪ Uselazy_incrementfor the decay effect.
3. Attack Command (Type 2):
o For a command 2 a b, compute the sum of attack power in the range [a, b] using the
segment tree.
4. Lazy Propagation:
o Defer updates using lazy_add and lazy_increment to ensure updates are applied only
when necessary.
Complexity:
● Build:O(N).
● Update/Query:O(logN).
Code:
Problem Name: “Escape the Trap”
Tag: Number theory, Greedy
Problem Setter: Md. Abdul Alim
ester: Mahfuzur Rahman Shanto, Ishrak Tawsif Nirob, Piyash Basak
T
Editorial:
Problem Understanding
We need to compute the value of:
2
A = 2𝑥 + 11x
Usingmodular arithmetic, we simplify calculationsby reducing values modulo 7.
Theory Behind Modular Arithmetic
1. Modulo Properties:
( a+b) mod m = [( a mod m) + ( b mod m) ] mod m
○
○ (a×b) mod m = [(a mod m) × ( b mod m)] mod m
2. Handling Negative Modulo:
x = ( x mod 7 + 7 ) mod 7
Code Explanation
● Read x and normalize it to modulo 7.
2
C
● ompute ( 2𝑥 + 11x ) mod 7 efficiently.
● Output the result.
Code:
Problem Name: “Endurance of the Soul”
Tag: Number theory
Problem Setter: Rifa Tasnia, Arpita Paul, Tahmina Meem
Tester: Zafrin Iqbal, Aumit Hasan
Step 1: Identify prime numbers between 1 to N using sieve of eratosthenes.
tep 2: Run a loop from D to N and identify whether the current value is prime or not. If
S
the value is prime then check whether Tarita has crossed minimum X distance from the
last point she has drank water. If yes, then she will drink water and the last point of
drinking water will be the current position.
Sample:
Input: 10 2 5
Output: 1
Explanation:
arita has to run a total distance of 10 meters. The prime numbers less than or equal to
T
10 are 2, 3, 5, and 7, which represent potential hydration points. However, she can only
drink water if she has covered at least 5 meters since the last time she hydrated.
● A t 2 meters, Tarita encounters a hydration point, but since she has not covered
the required 5 meters yet, she cannot drink water.
● At 3 meters, another hydration point is encountered. Again, she cannot drink
water because she has not reached the 5-meter minimum.
● At 5 meters, Tarita encounters a hydration point and has now covered the
required minimum of 5 meters. She drinks water and continues running.
● At 7 meters, she finds another hydration point, but the distance covered since her
last hydration point is only 2 meters (from 5 to 7), which is less than the required
5 meters. Therefore, she does not drink water.
● No more hydration points are encountered up to 10 meters.
Thus, in this 10-meter marathon, Tarita gets a chance to hydrate only once.
Code:
Problem Name: “Pillow Passing”
Tag: Implementation, Math
Problem Setter: Md. Iffatul Islam Anon
Tester: Piyash Basak, Ishrak Tawsif Nirob
Initialization
a
● [] is an array that holds the players, numbered sequentially from 1 to n.
● The variable j = 0 represents the current position of the pillow holder at the start
of the game.
Game Simulation
● T he game is simulated over n-1 rounds since one player is eliminated in each
round.
● For each round:
○ The formula (j + b[i] - 1) % (n - i) is used to determine the index of the
player who gets eliminated:
■ j is the current index of the pillow holder.
■ b[i] is the number of seconds for which the pillow is passed in the
current round.
■ (n - i) represents the number of players still in the game.
○ After identifying the player to be eliminated, the remaining players in the
array are shifted to fill the gap left by the removed player, effectively
reducing the size of the circle.
Final Output
● A
fter all eliminations, the only player left in the array will be at index a[0]. This
player is declared the winner.
Time Complexity
● O(n²):
○ In each round, we shift the remaining players in the array, which takes
O(n) time in the worst case.
○ There are n-1 rounds, so the overall time complexity is O(n²).
Space Complexity
● O(n):
○ T he space complexity is dominated by the array a[], which stores the
players, resulting in O(n) space usage.
Code :
Problem Name: “Voldemort’s Forbidden Words”
Tag: String Processing
Problem Setter: Abdul Hai Jibon
Tester: Rifa Tasnia, Aumit Hasan, Mujahidul Islam
Problem Understanding:
he problem requires determining how many times each forbidden word can be fully formed
T
using the given message while consuming characters sequentially. Once a word is formed, its
characters are no longer available for subsequent words.
Key Idea:
Count letters in the message.
●
● Try forming each word using available message letters.
● Remove used letters from the message after forming a word.
● Move to the next word and repeat the process.
● If No forbidden words are detected! Hogwarts is safe from Voldemort’s curse!
pproach:
A
1. Count the Letters in the Message
○ First, we count how many times each letter appears in the given message using a
map.
○ This helps us track which letters are available to form words.
2. Process Each Forbidden Word One by One
○ For each forbidden word, we check how many times it can be made using the
available letters.
○ If we can form the word, we use those letters and update the available letter count.
Now, 'd' is completely used up, meaning "bad" cannot be formed again.
3. Move to the Next Forbidden Word
○ Now, we check if the next forbidden word can be formed with the remaining
letters.
Now, 'b' is also completely used up, so "cab" can no longer be formed again.
Final Output
This ensures we form wordssequentiallywhile properlyusing and updating letter counts.
Complexity Analysis
C
● ounting characters in a string:O(|S|)
● Checking formations for each word:O(N * |W|)
● Overall complexity:O(|S| + N * |W|), which is efficientgiven the constraints.
Implementation Details
c ountCharacters(): Stores character frequency in amap.
●
● countFormations(): Determines how many times a wordcan be formed while updating
available characters.
● Themain()function reads input, processes words sequentially,and prints the results.
Code:
Problem Name: “The MEX Chef's Secret Recipe”
Tag: Greedy
Problem Setter : Arfan Arif
Tester: Piyash Basak, Md. Iffatul Islam Anon
Key Insight
he primary observationisthatplacingall
T 1’satthebeginningofthearrayandall
2’satthe
endofthearrayhelpsinminimizingtheMEXchaos.Thisapproachleveragesthepropertiesof
the MEX function and its impact on subarrays.
Approach Explanation
1. Reordering strategy:
○ Byplacingall1’ satthebeginning,weensurethatthesmallestpositiveinteger1
is present in the initial segments but not in all segments.
○ Placingall
2’
sattheendensuresthattheMEXofsubarraysnotcontaining 1is
inimized,asthepresenceof
m 2inthelatersegmentshelpsinkeepingtheMEX
values low.
2. Why this works:
○ When 1’s are at the beginning, the subarrays containing
1will have a MEX
alue of
v 2or higher,butsince
2’ sareattheend,thesubarraysattheendwill
have the higher MEX value, but for now on most of the subarrays MEX value
reduced due to the absence of 2.
ThisarrangementensuresabalanceddistributionofMEXvalues,minimizingthe
○
overall MEX chaos.
Solution
o solve the problem efficiently, we use the contribution technique. Instead of calculating the
T
MEX for every possible subarray individually, we decompose the problem into distinct cases
based on the properties of the array's elements and their positions.
1. Subarrays starting with 1and ending with 2
○ Thenumberofsuchsubarraysistheproductofthenumberof
1’
sandthe
number of
2’
s with the contribution of the whole arrayMEX.
2. Subarrays starting with
1but not ending with 2
○ The number of such subarrays is the product of the number of
1’s and the
umber of elements that are neither
n 1nor
2with thecontribution of 2.
. Subarrays made up of only 1
3
○ The number of such subarrays can be calculated using the sum of natural
numbers formula (the number of
1’
s) with the contributionof 2.
4. Subarrays that do not contain any 1
○ Thisalsocanbecalculatedusingthesumofnaturalnumbersformula(allexcept
the number of
1’
s) with the contribution of 1.
y combining all these cases, we can compute the total MEX chaos by considering the
B
contribution of different types of subarrays, without explicitly iterating over all possible
subarrays.
Code:
