Codeforces Round #378 Div. 2 review

Link Codeforces Round #378 Div. 2 (Contest 733) A. Grasshopper And the String Link: Problem Category: Implementation Even this is a first problem, I get wrong answer for first time submission. It is necessary to consider a corner case at the “end of the text”. Some other solution is inserting extra ‘A’ at the end of text so that you can handle it in the same way. (ex. latte0119’s solution)  

B. Parade Link: Problem Category: math Below implementation is a little bit optimized solution for not to use memory of \(O(N)\), but use \( O(1) \). But in the contest, it is better to consider solve it as fast as possible rather […]

Continue reading →

Codeforces Round #377 Div. 2 review

Link Codeforces Round #377 Div. 2 (Contest 732) A. Buy a Shovel Problem It can be paid without change if the change is 0 or \(r\).

B. Cormen — The Best Friend Of a Man Problem At day \(i\), dog need to walk \( k-a[i-1] \) times.

C. Sanatorium Problem Basic idea to the solution is not difficult, just check all the popssibility of what time start eating (enter room) and what time end eating (exit room). But the corner case handling makes this problem difficult and I cannot answer correctly in one time. Rather than below, more elegant/ short code solution can be found at pekempey’s solution.

D. Exams […]

Continue reading →

Codeforces Round #374 Div. 2 review

Link Codeforces Round #374 Div. 2 (Contest 721) Editorial A. One-dimensional Japanese Crossword Problem Just count consecutive ‘B’ in the sequence.

B. Passwords Problem This is also easy, just count the number for each string length. You even don’t need to process any string manipulation.

C. Journey Problem I felt it is difficult than problem D. During the contest, I tried to solve it by DFS but I got TLE.

To get answer, we can use DP (dynamic programming) to reduce computational complexity as \( O(mn) \).

D. Maxim and Array Problem Basic strategy to get minimum product is as follows, 1. If the product is positive, […]

Continue reading →

Codeforces Round #373 Div. 2 review

Link Codeforces Round #373 Div. 2 (Contest 719) A. Vitya in the Countryside Problem Basically, check last 2 character to determine its direction is “UP” or “DOWN”. Special case comes when the last number is 0 or 15, in that case the direction changes and you can determine the direction without looking second last character.

B. Anatoly and Cockroaches Problem We can consider 2 patterns for final alignment. Pattern 0 is to align “rbrbrb…” and pattern 1 is to align “brbrbr…”. We will compare the original alignment and final alignment. For each position i, we need to change the color to… Case A: r to b Case B: b to r If […]

Continue reading →

Codeforces Round #368 Div. 2 review

Link Codeforces Round #368 Div. 2 (Contest 707)   A. Brain’s Photos Problem Just need to check if color (Cyan, Magenta or Yellow) exists or not in the photo.

  B. Bakery Problem The problem sentence looks long, but after summarize, you just need to find the path between flour storage city and non flour storage city with minimum distance. But to find out these city path, I was using vector which is not fast enough and I got TLE during contest.

  We can make search fast, in constant time by using Array to set a type of city.

  C. Pythagorean Triples Problem Consider some cases to […]

Continue reading →