Overview of the Challenges
Problem |
Difficulty |
Pre-Requisite |
Time Taken |
No. Of Submissions |
---|---|---|---|---|
A |
Easy |
8 mins |
1 |
|
B |
Easy |
30 mins |
1 |
|
C |
Medium |
prefix and suffix properties |
1hr 5 mins |
1 |
D1 |
Medium |
Trees and nodes |
1 hr(after contest) |
1(after contest) |
D2 |
Medium |
same |
1 hr 15min(after contest) |
2(after contest) |
E |
Hard |
N.A. |
N.A. |
Experience
Problem A: LuoTianyi and the Palindrome String
Solution: The simple logic in this case was that there were two possibilities.
- CASE 1: If the substring of s from the second character to the last, or s2s3⋯sn is not palindrome then answer will be n-1 where n is the size of the string.
- CASE 2: If the above condition is not satisfied i.e s2=sn, s3=sn-1 etc . Since s is palindrome this means s1=sn, s2=sn-1. In this situation, every subsequence of s will be a palindrome , so the answer should be −1.
Problem B: LuoTianyi and the Grid
Solution: My first approach was greedy approach it means that the maximum possible a appears as the maximum value of as many subtables as possible, meanwhile, the minimum possible a appears as the minimum value of as many subtables as possible. This meant making the upper-left square minimum.
Problem C: LuoTianyi and the Show
Solution: Firstly i pointed out that if someone has a specific favorite seat (not -1 or -2), and their seat is taken by either a -1 or -2 occupant, it’s more sensible to prioritize the person with the favourite seat and allow them to go first, followed by the -1 or -2 occupant. After the people with favourite seat are seated, we place -1 and -2 . We find answer greedily for each division point.
Problem D1 and D2: LuoTianyi and the Floating Islands
Solution: A node is special if a person is present at it. I thought of a general approach for checking all nodes but the time complexity for that approach would give TLE(time limit exceeded) for the constraints so I checked for the patterns and on careful analysation , I realized if k is odd then there was only one node satisfying the condition. I tried to prove this theoretically after contest.
For its second part i only had to change the data types.
Problem E: LuoTianyi and XOR-Tree
Solution: I personally found this question a bit hard mainly because i was unable to optimize it. I couldn’t successfully implement it but the basic idea was to find the number of operations needed to make every path from a leaf inside the subtree of u to the root have the xor value of w. We could use a map for storing all these values and calculating the minimum one as answer.
Conclusion
All over the contest consisted if good problem in addition to the good test cases. I attempted from div 2 and solved the three questions. Anyone with enough practice could have easily solved the problems. My rating increased by +16 , if i had solved the questions earlier in less time then my rating would have increased more.
Contest Experiences | Codeforce Round: #872 (Div. 1 & 2)
Codeforces organized ‘Codeforces Round 872’ for Div 1 and Div 2 on 8th May, 2023. The round was rated for all participants. The pattern of the contest was that it had 5 problems, one of which was divided into two subtasks. Each division was given 2 hours of time to solve them. The contest had some rules like every other codeforces contest. The contest had all kinds of questions from easy to hard.
Prizes:
The contest was rated for all and there was an increase or decrease in the rating depending on the performance. Overall the score distribution for each problem was like this:
Div 1
PROBLEM |
SCORE |
---|---|
A |
500 |
B1 |
500 |
B2 |
750 |
C |
1750 |
D |
2250 |
E |
3000 |
Div 2
PROBLEM |
SCORE |
---|---|
A |
500 |
B |
1000 |
C |
1500 |
D1 |
1000 |
D2 |
1250 |
E |
2750 |
The contest also had penalty for wrong submissions.