Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### rng_58's blog

By rng_58, history, 5 weeks ago, ,

We will hold Keyence Programming Contest 2020.

The point values will be 100 — 200 — 400 — 700 — 900 — 1100.

We are looking forward to your participation!

• +68

 » 5 weeks ago, # |   -13 I keep wanting to participate in these unrated (for me) contests, but I always oversleep or play a few too many AOEII games or just forget. Surely this time...
•  » » 5 weeks ago, # ^ |   +76 Forgot again?
•  » » » 4 weeks ago, # ^ |   +4 Kinda — I checked out F when the contest was already running, realised that the only difficult part is going to be tiebreaking in a scheme "remove monochrome rows/columns while possible", since the number of possibilities is given just by the number of used rows/columns, and decided that I don't want to spend the remaining time in the contest on this.
•  » » 5 weeks ago, # ^ |   +8 Atcoder supports virtual contest now.
 » 5 weeks ago, # |   +3 Is this contest at Div.2 difficulty?
•  » » 5 weeks ago, # ^ |   +46 This is an "except for red" contest, so it's more like Div 1.5.
•  » » » 5 weeks ago, # ^ |   0 I solved the first two D:) sometimes, its worth giving a try..
•  » » 5 weeks ago, # ^ |   0 I think it is more difficult than Div1. I only solve 1 problem in the last contest...
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +2 I don't think a candidate master even can't solve a 200-point task in atcoder. Let's wait and see :D Anyway,I think it's going to be an excellent contest!
•  » » » » 5 weeks ago, # ^ |   -13 Wish me good luck this time!
 » 5 weeks ago, # |   -83 How To solve B?
•  » » 5 weeks ago, # ^ |   -8 i think contest is not over
 » 5 weeks ago, # |   -12 is D bitmask DP??if yes, where my solution is going wrong
•  » » 5 weeks ago, # ^ |   +4 Your cost is wrong.
•  » » » 5 weeks ago, # ^ |   0 thanks i got it
 » 5 weeks ago, # |   0 how to solve 2nd ans 4th question??In second question, i tried to store count of overlap for each i ,and later sort and remove maximum overlapped element ,but got WA.
•  » » 5 weeks ago, # ^ |   0 Represent each robot as an interval [X-L, X+L], then use dp + binary search to find largest subset of intervals of intervals whose intersection is empty
•  » » » 5 weeks ago, # ^ |   +11 Bit of an overkill actually, just pick the Segment with smallest end point and then remove all intersection ones, keep doing and keep a count.
 » 5 weeks ago, # |   0 how to solve question 2??
•  » » 5 weeks ago, # ^ |   0 Solved it just like the Interval Scheduling problem. Found the minimum number of intervals which are overlapping should be removed (using the standard greedy approach) and then the maximum robots we can keep is Total — minimum removed. https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/
•  » » » 4 weeks ago, # ^ |   0 Thank you :)
 » 5 weeks ago, # |   +11 AC on F 3 minutes after the contest QAQGreat round as always! I particularly liked D and F.
•  » » 5 weeks ago, # ^ |   0 Can you please explain D?
•  » » » 5 weeks ago, # ^ |   +17 When we reorder the elements, if the card that was initially at position $i$ is at position $j$, then it is red face up if $i \equiv j\ (\text{mod}\ 2)$, and otherwise blue face up. So we only care about the final order the cards end up in, not the sequence of swaps.The optimal way to get to a particular final order is to first make swaps to move the card that should be in the first position to the first position, then do the same for the second and so on.Therefore, we can do DP with states indicating the elements we have already used and the value the current sequence ends in. From any particular DP state, loop all cards not yet used. The $d$th not yet used card costs $d$ to use as the next element in the sequence, and we know which way up it would be, so we know whether it is larger than the previous one, and what value the new sequence would end in.After calculating the DP, just output the minimum DP value where all cards are used and the sequence ends in an arbitrary value. code#include #include #include using namespace std; using ll = long long; const ll INF = (int)1e9; const int N = 18; const int V = 50; int dp[1 << N][V+1]; int as[N]; int bs[N]; int off[N][N]; void cap(int& v, int off) { if (v > off) v = off; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 0; i < n; ++i) cin >> as[i]; for (int i = 0; i < n; ++i) cin >> bs[i]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { off[i][j] = (i % 2 == j % 2) ? as[j] : bs[j]; } } int h = 1 << n; for (int m = 0; m < h; ++m) { for (int j = 0; j <= V; ++j) dp[m][j] = INF; } dp[0][0] = 0; for (int m = 0; m < h; ++m) { int i = __builtin_popcount(m); for (int v = 0; v <= V; ++v) { int d = 0; for (int j = 0; j < n; ++j) { if (m & (1 << j)) continue; if (off[i][j] >= v) cap(dp[m | (1 << j)][off[i][j]], dp[m][v] + d); ++d; } } } int res = INF; for (int v = 0; v <= V; ++v) res = min(res, dp[h-1][v]); cout << (res >= INF ? -1 : res) << '\n'; } 
•  » » » » 5 weeks ago, # ^ |   +1 There is also Greedy solution without DP.
•  » » » » » 5 weeks ago, # ^ |   +1 Can you please explain!
•  » » » » 5 weeks ago, # ^ | ← Rev. 4 →   0 i have used bottom down approach as explained by mango_lassi.but getting wa for some caseshttps://atcoder.jp/contests/keyence2020/submissions/9587008Can someone check it?Ps-Figured it out
•  » » » 5 weeks ago, # ^ |   +6 I just use easy implement.My code is easy to understand. https://atcoder.jp/contests/keyence2020/submissions/9573589
•  » » » » 5 weeks ago, # ^ |   0 its so cool
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +6 My solution slightly differs from the ones present here. It doesn't use DP.After all the swaps, there will some cards with the red face up, others with the blue face. Iterate through all possible $2^{n}$ combinations. A particular combination is valid if we get an increasing sequence after a sequence of swaps. Cards with the red face up have to move an even distance to their final position while ones with the blue face move an odd distance. Iterate the cards from the left and greedily assign them the lowest available final position. If its not possible to do so, the combination is invalid. To calculate the minimum number of swaps to make this final sequence, simply calculate the number of inversions of the final sequence w.r.t the original sequence. Repeat the above procedure for all possible $2^n$ combinations. The minimum of all of them is the answer.
 » 5 weeks ago, # |   0 Do you have a solution？
 » 5 weeks ago, # |   0 Can someone give me the data of problem E 01-02. I've been WA for so long and I can't find what's wrong.
•  » » 5 weeks ago, # ^ |   0 I find that even the data of keyence 2019 haven't been put into dropbox....
•  » » » 5 weeks ago, # ^ |   0 What is "dropbox"?
•  » » » » 5 weeks ago, # ^ |   +3 Atcoder testcases are uploaded here: https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0
 » 5 weeks ago, # |   -9 Why was Task C so much easier than B even though its 400 points ?
•  » » 4 weeks ago, # ^ |   -10 I think that B's coding difficulty is much higher than C. But I think these two problem's difficulty in thinking is almost the same. (Which one is more solvable depend on yourself.)
 » 5 weeks ago, # |   +6 Testcases are uploaded. Please wait a bit for editorials.
 » 5 weeks ago, # |   +1 I think I misinterpreted Problem B, for test case 2 1 5 10 5, shouldn't the answer be 2 as we had to exclude the end points? Can someone tell me why its 1, as we had to exclude the end points, the ranges come out to be [-3,5] and [6,14] and they aren't intersecting.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I also misunderstood "excluding the endpoints". During the contest, I think the movable range of arms of robot i is [xi − li + 1, xi + li − 1], not [xi − li, xi + li − 1]
•  » » » 5 weeks ago, # ^ |   0 Excluding endpoints mean, that robot can reach any point(not necessary discrete) in interval (xi — li, xi + li), but cannot reach xi — li and xi + li.
•  » » » » 5 weeks ago, # ^ |   0 Ok...I see. Thanks.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 2 1 5 10 5 Why is the answer for this case 1 and not 2 by your logic? Robot 1 can reach (-4, 6) and Robot 2 can reach (5, 15) without intersecting.
•  » » » » » 5 weeks ago, # ^ |   0 They intersect on interval (5, 6)
•  » » » » » » 5 weeks ago, # ^ |   0 I think I do get your point, the question actually wants to say that hands can touch thats why (5,6) isn't allowed, (5,5) is because that just means that they are touching and not actually intersecting. Thanks for clearing it.
•  » » » » 5 weeks ago, # ^ |   0 despair Can you please see what am I doing wrong?? code
•  » » » » » 5 weeks ago, # ^ |   0 The only thing wrong with your code is the way you are sorting, you have to sort the given ranges with respect to their right end. Here's the AC code with just the sorting changed — Code
•  » » » » » » 4 weeks ago, # ^ |   0 Thank you abhi2402 I understood my mistake.
 » 5 weeks ago, # |   +11 Could someone share their approach for E?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 Main ideas: If two adjacent vertices $u$ and $v$ have $D_u = D_v$, it's possible to satisfy both by putting weight $D_u$ on the edge between them and giving the vertices opposite colors. If two adjacent vertices $u$ and $v$ have $D_u < D_v$, it's possible to satisfy $v$ by putting weight $D_v - D_u$ on the edge between them and giving the vertices the same color. If a vertex $v$ has no neighbor $u$ with $D_u \leq D_v$, it's not possible to satisfy $v$. If no vertex violates (3), it's always possible to construct a valid coloring and weight assignment using (1) and (2). Implementation is straightforward if vertices are processed in non-decreasing order of $D$. Unused edges can be assigned a weight of $10^9$.
 » 5 weeks ago, # |   0 Can anyone explain the approach for B-Robot Arms?
•  » » 5 weeks ago, # ^ |   0 You have to order the intervals by the right part, i.e.: if interval is (l,r) sort by r. Now, you are going to construct the set of the intervals. To do so, in order, insert each interval only if it doesn't intersects the others in the sets. To check that, is enough to check if it doesnt intersect the last one inserted. The answer is the size of this set.
•  » » » 5 weeks ago, # ^ |   0 Thanks, got it
 » 5 weeks ago, # | ← Rev. 2 →   0 In case anyone is interested, I'll post here my solution to problem D which isn't a dynamic programming one. What I do is generate every valid permutation of the cards and then count the numbers of flips needed to get to it. And I get the minimum of all of those.To see if a permutation is valid, we have to see if it is non-decreasing taking into account if the final card is in blue state or red state. To know the state, is only needed to know the parity of (i-j), where i is it actual position, and j its first position. If it is even, then is red, else is blue.Implementing simply this is quite inefficiente and some improvements are needed. My improvements are the following: 1.- Don't generate the rest of the permutation if you already make more inversions than the best solution so far. The number of inversions represent the number of flips needed to get to the permutation. 2.- If there aren't enough great numbers to put after this card, then don't put the card.Hope you like it, is a backtracking solution that I find more intuitive. The code is here: https://atcoder.jp/contests/keyence2020/submissions/9585908
 » 5 weeks ago, # |   0 In problem B, why do we have to sort according to x+l and not x-l?
•  » » 5 weeks ago, # ^ |   0 I sort by x-l,but implement strategy need some change.Sort by x+l I always see in some textbook. https://atcoder.jp/contests/keyence2020/submissions/9573530
 » 5 weeks ago, # |   +35 How to solve F?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +8 We can reduce the problem to the following: Suppose that the board is initially uncolored. If exactly $i$ rows and $j$ columns are never chosen, then how many possible ways are there to color the grid? Either $i=j=0$ or $i,j>0.$A way to color the grid is valid if we can repeatedly remove rows or columns in which all of the squares are the same color until only uncolored squares are left. Call rows and columns that may be removed uniform. To count each such grid exactly once, we should specify an order in which uniform rows and columns should be removed. Step 1: Remove all uniform columns. Step 2: Remove all uniform rows. Step 3: Remove all uniform columns created by the removal of the rows in step 2. ... and so on. Let $d$ be the number of distinct colors among the uniform rows or columns removed in the $i$-th step. It can be shown that $d$ is non-increasing over time (ignoring step 1). Furthermore, the number of ways to remove rows/columns on the $i+1$-st step depends only on $d$ after the $i$-th step and the number of rows/columns remaining. For example, if only black rows were removed during step 2 ($d=1$), then no black columns can be removed during step 3, because they were already removed during step 1. This means that $d$ will still equal one for step 3 (unless no columns are removed at all). Note that when $x=y=0$, $d$ is equal to two after every step (again, ignoring step 1).Code
•  » » » 5 days ago, # ^ | ← Rev. 2 →   0 .
 » 4 weeks ago, # |   0 Is there the tutorial in English?