### KAN's blog

By KAN, 3 years ago, translation,

Hi all!

This weekend, at Oct/21/2018 11:10 (Moscow time) we will hold Codeforces Round 517. It is based on problems of Technocup 2019 Elimination Round 2 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2019 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The round authors are Kostroma, Golovanov399, komendart, Denisson and Dashk0.

Have fun!

The round is over, congratulations to the winners!

Technocup 2019 - Elimination Round 2

Codeforces Round #517 (Div. 1, based on Technocup 2019 Elimination Round 2)

Codeforces Round #517 (Div. 2, based on Technocup 2019 Elimination Round 2)

The editorial is published.

• +115

 » 3 years ago, # |   +67 CF rounds on weekends are the most fun.
•  » » 3 years ago, # ^ |   +6 I feel the same
 » 3 years ago, # |   +39 Perfect time for Chinese users!
 » 3 years ago, # | ← Rev. 2 →   +12 ..
 » 3 years ago, # |   +4 This weekend, It's not a weekend in most Arabic countries XD
•  » » 3 years ago, # ^ | ← Rev. 2 →   +27 it's not weekend in Iran too .
 » 3 years ago, # |   +46 How many problems? When do we know the score distribution?PD: Just a joke: Where is thanks to Mike and Polygon and ITMO??
 » 3 years ago, # |   +2 Elimination round(not CF) will be rated or no?
•  » » 3 years ago, # ^ |   +56 Rated
 » 3 years ago, # |   +12 very less participation :(
•  » » 3 years ago, # ^ |   +1 All who qualifies for the elimination round are not here.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 now the round is delayed because of you
•  » » 3 years ago, # ^ |   +5 Sad :(
 » 3 years ago, # |   +1 Delayed by 5min!
•  » » 3 years ago, # ^ |   0 Before the contest 00:01 remainingMe: Let's bring it on!Before the contest 04:59 remainingMe: Oh f**k.
•  » » 3 years ago, # ^ |   +10 At least 5 min
•  » » 3 years ago, # ^ |   +8 Thanks, I afraid something went wrong with my connection
 » 3 years ago, # |   -14 delay :(
 » 3 years ago, # |   +3 Score distribution?
 » 3 years ago, # |   +10 I love contests at 3 am :)
 » 3 years ago, # |   0 I am not able to submit code, getting error "you have submitted exactly the same code before". Please someone look into this matter. I have not done any submission in that problem.
•  » » 3 years ago, # ^ |   0 Please, check PMs
 » 3 years ago, # |   +1 div2D was dp or bfs?
•  » » 3 years ago, # ^ |   +18 Both of them :)
•  » » 3 years ago, # ^ |   +11 I spent so much time on this problem and didn't manage to do it in the end, is there a way to compute for each i, j the lexicographically smallest path from i, j to n, n?
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +1 I did it with dynamic programming. For each field you just need to know if you want to go right or down. So create a table int dp[2001][2001] with 3 possible values: 0 — go down; 1 — do right; 2 — it doesn't matter (both going down and right will produce same string). We fill entries of dp from n, n to 1, 1 (backward). how to fill this array? For boundary entries (i = n and j = n) it is obvious, for others dp[i][j] = fillDp(i + 1, j, i, j + 1); //(x, y) - pointer which is lower, (b, a) - pointer which is to the right int fillDp(int y, int x, int b, int a) { if (arr[y][x] < arr[b][a]) return 0; //you can only go down if (arr[y][x] > arr[b][a]) return 1; //only right if (b == y && a == x) return 2; //doesn't really matter which way //if letters are the same and we check different fields //we either move according to dp or (if dp == 2) we move pointers closer to each other if (dp[y][x] == 0) y++; else x++; if (dp[b][a] == 1) a++; else b++; return fillDp(y, x, b, a); Edit: arr = original array with lettersComputing path is just going with pointers in dp.I can't actually prove it works in O(nm) but I got accepted. Here is my solution — a little more verbose: 44647952
 » 3 years ago, # |   +13 What was pretest 15 in div2 C? :(
•  » » 3 years ago, # ^ |   +8 Something like 147694707 63714381The sum m + n in this case should be 20562.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 It works for me, and I got pretest 15 wrong. What's special about this test case?
•  » » » » 3 years ago, # ^ |   +1 I stress-tested my WA on pretest 15 with the solution that passed that test case to get that. I'm sorry that I don't see anything special about this test case :(.
•  » » 3 years ago, # ^ |   0 Got 6 WA in that. But, figured it out. It was because of not using long long int.
 » 3 years ago, # |   +55 300iq Becomes Legendary Grandmaster!!
•  » » 3 years ago, # ^ |   0 Хайпожор
•  » » » 3 years ago, # ^ |   0 Ага
•  » » 3 years ago, # ^ |   +4 He won't dye his hair pink for a week.
 » 3 years ago, # |   0 How do you solve div2B?
•  » » 3 years ago, # ^ |   +1 DP by O(16n) I'm not sure it's a correct algorithm.
•  » » » 3 years ago, # ^ |   0 I did it this way, and it seems to work
•  » » » 3 years ago, # ^ |   0 Could you elaborate, please?
•  » » 3 years ago, # ^ |   -6 DFS is enough.
•  » » » 3 years ago, # ^ |   0 Sorry! I find a hack data to hack DFS. It is: 100000 3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 ...(repeat) 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 ...(repeat) answer is: YES 1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 ...(repeat) I have hacked lots of codes using DFS to solve problem B. If we add this data for judging, a lot of codes will be hacked.The reason why it can hack DFS is when a = 3 and b = 0, t can be 0, 1, 2, 3.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!Because if ti has been determined, ti + 1 will have only one value to choose. Specially, if a = 3, b = 0, t can be 0, 1, 2, 3. But if ti has been determined, we should not worry about ti + 1.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 Brute force the value of tn. Given ai, bi, and ti + 1, it is easy to show that there can be at most one ti that satisfies the given constraints.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +8 Yes, and ti equals ai + bi - ti + 1. Because x&y + x|y = x + y.
•  » » » » 3 years ago, # ^ |   0 How did you get this relation?
•  » » » » » 3 years ago, # ^ |   +12 By Binary Numbers.x + y = x + y — x & y + x & y = x + (y — x & y) + x & yBecause any digit of x and that of (y — x & y) are different,So x + (y — x & y) = x | y So x + y = x | y + x & y
•  » » » » » » 3 years ago, # ^ |   0 Wow, thanks!
 » 3 years ago, # |   -6 Div2F / Div1D was bfs?
 » 3 years ago, # |   +8 I finished fixing div2.D and the contest is overNow, I hope my solution is not correct ...
•  » » 3 years ago, # ^ |   +1 Don't worry, it isn't.
•  » » » 3 years ago, # ^ |   0 Fine.Not correct....
 » 3 years ago, # |   +10 Lose to constructing.
 » 3 years ago, # |   0 I am closed
 » 3 years ago, # |   0 How to solve div2-C , i tried bin Search but i knew it's not working good ,, any hint ?
•  » » 3 years ago, # ^ |   +9 Let k be the largest integer such that 1 + 2 + ... + k <= a + b. Then it's always possible to construct an answer with n + m = k.
•  » » » 3 years ago, # ^ |   +13 thank you :D
•  » » » 3 years ago, # ^ |   0 Can you explain how?
•  » » » » 3 years ago, # ^ |   0 Like before, we have S = 1 + 2 + ... + k <= a + b. Just iterate over i = k...1 and greedily subtract from a whenever i <= a. If S < a, then we're done, otherwise it should be easy to see that we can always get a subset of elements that sum exactly to a, in the end, so the sum of remaining items is S - a <= b.
•  » » » 3 years ago, # ^ |   0 Then it's always possible to construct an answer with n + m = k Why is it so?
•  » » » » 3 years ago, # ^ |   0 It's explained in the editorial, perhaps more nicely than I can do here.
•  » » » » » 3 years ago, # ^ |   0 Ok thanks!
 » 3 years ago, # |   0 in B all a[i] and b[i] gives only two numbers except when a[i]=3 and b[i]=0 then t[i]=1 and t[i+1]=2 or t[i]=0 and t[i+1]=3 right?I couldnt submit my last solution because I did not understand my new stupid error while debugging which is we can't write cout<<1&3; that gives an error and Idk why
•  » » 3 years ago, # ^ |   0 when you type cout << 1&3 compiler reads << as bit shifting
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 man if my solution was right and i couldnt submit it because of that ... meh edit: it's wrong anyway:P
 » 3 years ago, # |   +2 I slept just 3 hours to take this CF, let's see how my C fares the system tests :Dd. Already had to resubmit once during the contest
•  » » 3 years ago, # ^ |   +3 How to solve it?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +5 I use bfs for n ≤ 12. If n is greater than 12, find the last 1 appearance and modify it to make sure that at most two steps would be used to set the last 6 positions 0.
•  » » » » 3 years ago, # ^ |   0 So did bfs on bitmask for n<=12 ?Also when is answer "No" ?
•  » » » » » 3 years ago, # ^ |   0 When n >  = 8, answer is always YES. So you can just brute and check if it's no for n < 8.
 » 3 years ago, # |   0 What was pretest 8 for div2D ?
 » 3 years ago, # | ← Rev. 2 →   +57 How I solve Div2-C/Div2-A: Write a greedy solution, get WA on test 15. View submission detail and realize the checker's answer is not the same as the sample answer. Analyze the pattern and write a new solution.
•  » » 3 years ago, # ^ |   0 anything matter?
 » 3 years ago, # |   0 wow, very weak pretests again
 » 3 years ago, # |   +16 Full Feedback contests are the best.
•  » » 3 years ago, # ^ |   0 But remember that in most rated Codeforces round, you don't receive full feedback, especially when the pretests are weak :D.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 I'm of the opinion that problems which are going to have very few solves anyway almost always ought to have virtually full feedback, i.e., the systests should not have anything special (new cases, etc) that the pretests don't have, especially considering that if you fail systest you get a score of 0.
 » 3 years ago, # | ← Rev. 3 →   +20 It seems that div2C/div1A system tests are weak. After the contest I found a bug in my code that makes it fail : for the test 7 1  it gives the following output : 3 2 3 4 1 1 which is obviously wrong. And still my solution got AC. (tmw when you think that the pretests are weak but after the systests it turns out the systests are weak too xd)
•  » » 3 years ago, # ^ |   +1 Solutions should be rejudged if that's the case.
 » 3 years ago, # |   +53 What is the answer to this case for C? LHiC's AC code gives NO. 7 1 0 0 0 0 0 0 
•  » » 3 years ago, # ^ |   +26 My AC code gives YES 3 3 5 7 3 4 5 1 4 7 
•  » » 3 years ago, # ^ | ← Rev. 2 →   +24 YES 3 5 6 7 1 4 7 4 5 6 Weak tests ¯\_(ツ)_/¯
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Similarly, I resubmitted because my first submit uses too many operations in the case 100000 0 1 0 1 0 ... 0 1 0 1 0 0 0 0 1 1 (line breaks added for clarity)But turns out my first submit would also have passed :/
 » 3 years ago, # |   0 Waiting for tutorial.
 » 3 years ago, # |   0 Waiting for my new rating... And of course waiting for tutorial....
 » 3 years ago, # |   +55 The tests for div1 C seem to be so weak that some wrong codes passed.44641451 The hack data is : 1 1 0 1 0 1 0 1 0 1 0 ...
•  » » 3 years ago, # ^ |   +18 Uhhhh that is the obvious "naive" solution that I didn't bother coding because surely it wouldn't pass right?.... but it does.And then I didn't find a good solution during the contest :/
•  » » 3 years ago, # ^ | ← Rev. 5 →   0 After more thinking I realise this solution is quite solid with a small tweak. If try it twice and take the best solution, once normally and once ignoring the first 1 (and do the first 1 manually later) then it is perhaps not possible to make a counter case.Anyway there are like dozens of solutions and I came up with zero of them during the contest.
 » 3 years ago, # |   0 can someone plz tell me whats wrong with my code for Div2D?? 44650538
 » 3 years ago, # |   0 As I see, the problems and the score distribution in the Technocup Round and in the Div 2 version were the same. However, the scores obtained in the Technocup Round were smaller compared to the Div 2 version. For example, score 2500 is in top 40 in the Technocup, whereas in the Div 2 version, someone with 2500 is on the 200th + position. So I guess that participation in the Technocup would have helped you increase your rating more than in the Div 2 version.
 » 3 years ago, # | ← Rev. 6 →   +6 Maybe the tests for Div1C are not strong enoughthese solutions were hacked by my data.446387104464145144641456data: 125 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 Update: Oh, after posting this review, I found that cuizhuyefei has already mentioned it
 » 3 years ago, # | ← Rev. 4 →   0 Well, after contest, I have found a hack data to hack DFS solution in Div2.B.We just use a form like: 100000 3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 ...(repeat) 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 ...(repeat) answer is: YES 1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 ...(repeat) If you use DFS to solve this, you will get Runtime Error.
•  » » 3 years ago, # ^ |   0 If possible, please add this data to hack someone who didn't solve the question well, including me :-) . Thanks.
•  » » 3 years ago, # ^ |   0 Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!
 » 3 years ago, # |   0 I faced problem in B when ai =3 and bi=0 then ti and ti+1 can take 0,1,2,3 .can anyone help?
•  » » 3 years ago, # ^ |   0 You can try to make first t( t1 ) be 0, 1, 2, 3. And the sequence will be constructed.We can think about this:If t1 has been determined, t2 will also be determined. Obviously, if ti has been determined, ti + 1 will be determined, too. For example, if ai = 3 and bi = 0, ti can take 0, 1, 2, 3. But don't forget that ti has been determined. ti will only has one value to choose, and it's easy to solve. Hope I can help you :-).
 » 3 years ago, # |   0 the rating changes is unfair. in official round if you solve just 3 problem you will get high rating changes but in Div2 round if you solve 3 problem your rating change is not as high as rating chane in official round.
 » 3 years ago, # |   0 What's wrong with my solution for Div2-C? 44699758TLE, though in my environment it takes only 0.012 s.
•  » » 3 years ago, # ^ |   0 Ok, "long" vs "long long" was the problem.
 » 3 years ago, # |   0 I noticed that the announcement and editorial are not linked to the problems, can some admin do this? Thanks
 » 3 years ago, # |   0 Does anyone know if there will be a parallel open round again for the upcoming Technocup Elimination Round 3 in a few days?