Contest Experiences | AtCoder: Regular Contest 153
AtCoder conducts regular contests for competitive programming enthusiasts to showcase and practice their skills. It consist of 6 problems which have to be solved in a duration of 120 minutes.
AtCoder regular contest 153 had a similar pattern. There were no prizes for this contest rather it was a rated contest in the rated range of 0-2799.
The score associated with each task was as follows:-
- TASK A: 300
- TASK B: 500
- TASK C: 600
- TASK D: 800
- TASK E: 800
- TASK F: 1000
The total score was calculated by considering both the total scores and the penalties. The penalties are computed as (the time you spend to get your current score) + (5 minutes) * (the number of incorrect attempts).
CONTEST LINK: https://atcoder.jp/contests/arc153
Overview of the Challenge:
TASK |
Difficulty Level |
Topic |
Approx Time Spent |
Number Of Attempts |
---|---|---|---|---|
A |
Easy |
Maths and tuple |
5 -6 mins |
1 |
B |
Medium |
array and sequences |
20-25 mins |
1 |
C |
Medium-Hard |
observation and summation properties |
30 -40 mins |
1 |
D |
Hard |
1 hr |
1 (after contest ended) |
|
E |
Hard |
1 hr |
2(after contest ended) |
|
F |
Hard |
biconnected components and block-cut trees |
NA |
couldn’t solve |
My Experiencewith each question:
Task A: AABCDDEFE
- Objective: Find a 9-digit beautiful number AABCDDEFE using the digits A, B, C, D, E, and F, with the condition that A is not 0.
- Key observation: The integer AABCDDEFE corresponds to a 6-tuple (A, B, C, D, E, F) in lexicographical order.
- Limited count of 6-tuples satisfied the conditions.
- Calculated the nth tuple.
- Given constraints facilitated listing all tuples and finding the nth tuple.
Task B: Grid Rotations
- Key observation: For each operation (x, y), the indices are independently flipped for height and width.
- This observation was verified with given sample cases.
- Objective: Calculate arrays for both height and width to determine the result using these indices.
- Operation ‘x’ flipping involved:
- Reversing the entire array.
- Rotating the index array to the right by len – x, where len is either the height or width.
- When two consecutive operations were performed, the reversals canceled each other out.
- Performing ‘x‘ followed by ‘y‘ was equivalent to rotating elements right by ‘x‘ and then by ‘len – y‘.
- This strategy allowed simulating an even number of operations, and if ‘Q‘ was odd, the final step could be replicated directly.
Task C: Increasing Sequence
- Initially faced challenges understanding the problem and developing a solution.
- Derived an approach that was eventually accepted.
- Special case handling: If A[0] = -1, flipped the sign of A[i] to ensure A[0] was always positive.
- Introduced variables: S for the sum of x[i] with A[i] positive and R for the sum of x[i] with A[i] negative.
- The goal was to find unique x[i] values such that S = R.
- Started with the initialization of x[i] as i, based on an observation.
- Two cases:
- If S > R, subtracted (S-R) from x[i].
- If S < R, iterated from i = n-1 to 0, adding (R-S) to x[i].
- The iteration ensured that S and R would become equal at some point, indicating success.
- If S still didn’t equal R in the end, checked if the sum of A[i] was 0 to confirm no solution.
- Reset x[i] = i and, from i = 0 to n-1, subtracted (R-S) from x[i] to stop when S = R.
Task D: Sum of Digits
- Initially unable to solve the problem during the contest.
- Realized a key insight after the contest ended, leading to a late solution.
- The solution involved calculating an additional number in the format 10x+1.
- Implemented a recursive approach to compute the value of the function for smaller values of x.
- When max(A) = 1, the function F(A) equals the sum of
- Applied dynamic programming to recursively calculate states using dp[k][n], where dp[k][n] represented F(A(k,n)), computed in descending order of k.
- Introduced Fr(A) as the minimum value of the above function for x such that x ≡ r (mod 10).
Task E: Deque Minimization
- Initially, a greedy approach was adopted for the problem.
- The approach involved initializing an empty string S and performing operations for each digit of the number X.
- For each operation, if the decimal notation of the current character was greater than the first character of S, it was inserted at the end of S; otherwise, it was inserted at the beginning.
- This process generated a positive integer Y that represented S.
- Dynamic programming (dp) was employed to solve the problem with O(n^2) complexity.
- Specifically, dp[L][R] was defined as the number of integers X that yielded the Lth through Rth characters of Y.
- An initial incorrect submission occurred due to the oversight of the case when L < R.
- In the subsequent submission, dp[L][R] was calculated using dp[L+1][R] and dp[L][R−1].
Task F: Tri-Coloured Paths
- Though i could understand the logic and how it worked but i had no idea about the implementation of data structures used for implementing the solution.
- A colouring is bad when edges in every colour exist and the condition in question is not satisfied. That is, any simple path contains edges in two or fewer colours.
- So we had to count the bad colouring which could be implemented using bi-connected components and Block-cut tree.
Conclusion:
The problem-set was challenging with a mix of math, dynamic programming, and data structures. Although I couldn’t complete all the questions, it was a valuable experience.