Hello Codeforces! Because in April I have a lot of free time and I want to improve my CP skills, I will try doing a virtual every day for a month. I don't know if it's the best practice method but I'll still give it a shot. To keep myself motivated I'll update this blog once a week(?). Feel free to join along!
Starting Rating 758 Ending Rating: ?
Day 1: I did ARC 158 where I only solved A
Day 2: CF862 solved A,B quite fast. Unable to solve C with binary search on set(lowerbound). Performance : 1193
Day 3: CF861 (virtual) Solved A,B fast (trey were standard) but got 3WA. I tried C with backtracking but I realized it is too slow. Performance : 1315
Update 1:
Day 4: Today I did CF863 div 3. Like someone mentioned this contest felt like a div 2.25 (at least for me). I managed to solve A,B,C quickly (but still they were a bit tricky) and spent like 1:30 trying for D,E but with no progress. Performance : 1318, Almost reached pupil
Day 5: No contest today :(. I solved 1805C from 862_DIV2 (DAY 2). In the contest I was close : I proved that (b — k) ^ 2 should be < 0. But I didn't realized that we can use upper_bound to look for k since a,b,c are fixed. I enjoyed this problem, it has a nice solution.
Day 6: I tried D from same contest, but I needed to learn All longest path from CPH (competitive programmer handbook). I did that but still got TLE on 8 and I don't know the reason why. My solution seems O(N).
Day 7: I started solving problems for this blog :https://codeforces.me/blog/entry/114789
Solved:
1519D (1600) I didn't come up with the solution, but when I checked the editorial is was a trivial N^2 dp. Maybe if I spent more time before checking the editorial I could have solved it. Nevertheless a good problem for a beginner with dp.
1324D (1400): Solved using segment tree, probably a huge overkill and the code is not clean (but that is the first solution that came to my mind). I also got lots of WA because I didn't make the segment tree big enough (size).
1808C (1900): (C from Day 3) This problem was surprisingly unintuitive. I'll briefly explain my solution:
1) Eliminate the common prefix.
2) Iterate over the next 2 digits and set the rest of them equal with dg1 and after = dg2
3) Update the best answer that satisfies the constrains
This works because for each pair of digits we only care about the best answer. Since the first digit of a and b now is different we know which is true: either our number is surely < b or surely > a (we discard the other options) so now we can set the rest greedily equal with the max digit (that we set) if we know that x < b or the min digit otherwise.
Conclusion after a week: Don't expect big improvement after working only for a week.
