Codeforces Round #712 Div2 Solution

Ugh. Really weak. Problem E actually still has "expected possibilities" to solve it, but I given up.


E. Travelling Salesman Problem

Solution

Codeforces Round #712 Div.2(A ~ F) 超高质量题解(每日训练 Day.15 )_繁凡さん的博客-CSDN博客
Codeforces Round #712 Div.2(A~F) 题解A. Déjà VuProblem给你一个字符串。问能否在该字符串里插入一个字母 a,使得它不是回文字符串。Solution显然不想让他变成回文字符串,那就破坏它成为回文字符串的条件,我们只能插入字符 a ,所以我们直接算一下该字符串前缀、后缀里各有有几个 a ,把我们能插入的 a 放到 a 多的地方即可。Code// Problem: A. Déjà Vu// Contest: Codeforces - Codefor

Not solve this problem by myself. Looked the solution above.

Code

Submission #112084741 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. 3-Coloring

Interactive problem is interesting. It's a game problem but more like a construction problem. Not very hard. But my solution is a little hard to implementation. Not sure if there is other solutions.

Codeforces Round #712 3-Coloring - Game & Implementation
Fixed two colors cross-painted until one of the colors fills the half of the map. After that, the remaining half can be filled with one of the remaining two colors base on the input.
Click this for more detail solution

C. Balance the Bits

Solution

Classic bracket pairing problem. Calculate prefix sum from left to right. So if found '(' then +1, otherwise -1. Of course in the whole process, the total sum should be zero and non of prefix less than 0.

Now think about $s_i=0$. That means in $a$ and $b$, one of them +1 another one -1. We just +1 for the one which prefix sum is less than another.

Then think about $s_i=1$. This one will affect the prefix sum for both $a$ and $b$. Because $s_i=0$ will need -1. Also because two 0 in $s$ will not impact the prefix sum. So for more safety, first half of $1$, we always chose '('. And other half always ')'.

Code

Get WA once because of a small mistake. I forgot check if anything left after scanned $s$.

Submission #112003295 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Flip the Bits

Solution

Do the operation from back to the front. Just a implementation problem.

Code

Submission #112001224 - Codeforces
Codeforces. Programming competitions and contests, programming community

A. Déjà Vu

Solution

Implementation. Try insert to the start and end position. If both of them are palindrome, then return no. Otherwise, print the one which is not palindrome.

Code

Submission #112000245 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge