Contest Experience: GeeksforGeeks Weekly Contest 113
About the Contest: This contest was organized on July 30th at w3wiki, it consisted of 3 questions and the time given to solve them was 1 hour and 30 minutes.
Link of the Contest: w3wiki Weekly Contest 113
Overview of the questions:
Problem Name |
Difficulty |
Pre-requisite |
Approx. time to solve |
number of submissions by me |
---|---|---|---|---|
Maximum Number |
Easy |
2-3 minutes |
1 |
|
Two Swaps |
Easy-Medium |
5-10 minutes |
3 (2 WA) |
|
Total Pairs |
Medium |
10-15 minutes |
2 (1 TLE) |
Experience:
Problem 1: Maximum Number
This question was very straightforward and easy, We could just simply pick the first occurrence of ‘7’ from left hand side and replace it with a ‘9’. This would result in the largest number possible using the given operation.
Problem 2: Two Swaps
Though This question was kind of easy but it required many case works which made me do 2 wrong submissions.
- Reason for 1st WA: I assumed that if array A has 4 indices that were not in there respective sorted place then the answer will always be TRUE. This assumption was wrong for example: arr=[4 3 1 2] here answer should be false.
- Reason for 2nd WA: I assumed that if the size of array A is 2 then the answer will always be TRUE because I read the question wrong where it was written “exactly” two operations, I misunderstood it to “at most” two operations.
- Accepted Solution (N*logN): This question was purely observation-based and needed some case work. We just need the count of indices that are not in their required sorted place, i.e.
- if count=0 or count=3 return true
- if count=4 and a pair of indices store each other’s required values, return true.
- return false in all other case
Problem 3: Total Pairs
This problem was quite interesting and better than above two problems, basic knowledge of binary search was sufficient to solve this question in N*logN complexity. Still I made a TLE submission.
- Reason for 1 TLE: I did not know that N^2 solution was too slow when N=10^4, hence I wrote a brute force two loops solution to calculate the answer for every subarray and add them together.
- Accepted Solution : Firstly we sort the array to apply binary search. Now for each nums[i] we can calculate the start and end index of the subarray whose values when multiplied by nums[i] will range between x and y.
- start index = index of ceil(x/nums[i]) (use binary search to calculate)
- end index = index of (y/nums[i]) (use binary search to calculate)
Conclusion: I would place this contest on the easier side as I was able to solve all 3 problems within 30 minutes.
Contact Us