Contest Experiences | Codeforces Round: #869 (Div.1, Div.2) Editorial

About The Contest:

The Contest was organized on 29 April 2023 on Codeforces. The Contest consisted of 6 problems for Div. 1 and Div. 2 participants and had a duration of 2 hours. The contest had around 18k registrations combining both divisions. The scoring for various questions was as follows:

Contest Link: https://codeforces.com/contest/1818

My Experience:

I participated in the contest as a Div. 2 participant and was able to solve 4 problems out of 6 in the given time.

LET’S DISCUSS THE PROBLEM:

Problem A: Politics

In this problem, we had to determine the maximum number of persons that stay in a meeting after discussion on k opinions, where after each discussion minority people leave the meeting. The group also has one leader who must stay in the meeting. Thus, we need to determine the maximum number of people who have same opinion as that of the leader all the times and remove the people who disagree with leader for each opinion.

Problem B: Indivisible

In this problem, we needed to find such a permutation for a given integer n, in which sum of any of it’s subarray is not divisible by it’s length. And, if the permutation doesn’t exist, we just return -1. So, the catch here was to know that sum of all elements in case of a odd length permuation would always be divisible by n as sum is n*(n+1)/2. For even sized permutation, we can swap the adjacent elements in the simple permuation, i.e. 1,2,3,4,. . ., n-1, n. Then the desired permutation would be 2,1,4,3,. . .,n, n-1. I got this intuition for the solution by observation. According to the problem statement, the answer for n being 1 would be 1, so this case was handled separately.

Problem C: Almost Increasing Subsequences

This problem statement defines a almost increasing subsequence as a sequence which does not contain three consecutive elements x, y, z such that x ≥ y ≥ z. For a given array, there were several queries asking for the length of longest Almost Increasing Subsequence for a given range of elements. I was able to implement a O(n*q) solution for this problem but it gave me TLE, so using precomputation by prefix sums, I implemented an O(n+q) solution which got accepted.

Problem D: Fish Graph

In this problem, we needed to determine whether a graph contains a cycle and a special node such that the node is connected to 2 other edges which are not connected to any other node in the cycle. If such a subgraph exists in the given graph, we need to print “Yes” and that subgraph otherwise we just need to return “No”. By reading this problem, I came to know that the necessary condition for such a subgraph to exist is that there should be a node in the given graph which has a degree of at least 4 and that node is part of a cycle. So, I found the nodes having degree greater than or equal to 4, then checked whether we get a cycle or not from that node by DFS, and then checked the 2 other edges condition for printing the obtained subgraph as answer.

Conclusion:

I solved 4 out of 6 problems during the contest. The remaining two problems involved some specific set of algorithms and I couldn’t think for the solution during the contest. I tried to upsolve those problems after the contest. You should also start giving contest regularly on various coding platforms to test and improve your problem solving skills. And, you must upsolve the problems you weren’t able to solve during the contest to learn new concepts.