Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Eva's blog

By Eva, 11 months ago, ,

Hello! Codeforces Round #581 (Div. 2) will start on Aug/20/2019 17:35 (Moscow time). The round is rated for everyone whose rating isn't greater than 2099.

The problems were invented and prepared for you by danilz1806, baumanec and sorry_marymarine. Thanks to Anton arsijo Tsypko for the coordinating the round. Thanks to the testers for testing and giving advice:

You will be given 5 problems and 2 hours to solve them. The score distribution will be announced later is 500-750-1250-(1500+750)-2500.

The round is over! Congratulations to the winners:
1. 79brue
2. sinus_070
3. baluteshih
4. xpporzwzl
5. shahaliali1382

• +352

 » 11 months ago, # |   +89 you forgot Numb
•  » » 11 months ago, # ^ |   +7 to you he is mister master
•  » » » 11 months ago, # ^ |   +23 for uno i'm not
•  » » » » 11 months ago, # ^ |   +1 Mr orange, I was your alt for half a year, and you didn't asked me to test your contest?
•  » » » » » 11 months ago, # ^ |   +30 Yes because why should i ask myself for testing my round dude
•  » » » » » » 11 months ago, # ^ |   +11 since you didn't liked Twice we disbanded, so you are not my alt anymore!
 » 11 months ago, # |   -56 Yout better say thanks to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon if you want your round to be rated)))
•  » » 11 months ago, # ^ | ← Rev. 2 →   +152 thanks to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon
•  » » » 11 months ago, # ^ |   0 15 peoples are tester for contest. <3 I thinks this round don't need hacking. I'm afraid =))))))
•  » » 11 months ago, # ^ | ← Rev. 2 →   +72 The great Mr. Master Numb has already predicted this.
•  » » » 11 months ago, # ^ |   -10 it's not hard to predict this
 » 11 months ago, # |   +3 All the best for your 1st contest :)
 » 11 months ago, # | ← Rev. 2 →   +11 Bencil Sharpeniro orz
 » 11 months ago, # |   +200 That army of 15 testers...
•  » » 11 months ago, # ^ |   +166
•  » » » 11 months ago, # ^ |   +3 The blue dude Ziein is Spiderman XD
•  » » 11 months ago, # ^ |   -42 .
•  » » 11 months ago, # ^ |   +11 Problem A: The first line contains a single binary number s ( 0 ≤ s < 2^100) without leading zeroes.Okay guys. Well played (^_^)Me: -5, Testers: 1e5
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 string contains only a '0' isn't counted as one with leading zeros .. a leading zeros string is the one with length more than 1 and contains leading zeros
•  » » » » 11 months ago, # ^ |   0 Actually string 01 also has leading zero:)
•  » » » » » 11 months ago, # ^ |   0 sorry, fixed it
 » 11 months ago, # |   -65 Thank you all for your efforts. We wish we had an extra lifesaver 10 minutes as in #580 :)
•  » » 11 months ago, # ^ |   -7 Get ready to become newbie
•  » » » 11 months ago, # ^ |   0 Thank you for your support :)
 » 11 months ago, # | ← Rev. 3 →   +1 hello sorry_marymarine,i am predicting this to be great contest,, because i know for facts that BencilSharpeniro is a very good problem testing man,last time he giving me the problems, i felt like it was a good problems, so i having the faith in this contest and qualities of this contest,,,..,,..good luck and high rating mr master, rajeshwar~~
•  » » 11 months ago, # ^ | ← Rev. 2 →   +18 Of course. I can assure you that the grammar for problem A is on point. I ran it through Grammarly just for you bentaji <3.
•  » » » 11 months ago, # ^ |   +16 So, grammarly servers has the problems in its logs. Any grammarly devs here?
 » 11 months ago, # | ← Rev. 2 →   0 Hope the statement will be short and easy to understand. Thanks :)
 » 11 months ago, # |   +9 Good luck and high rating to all :)
 » 11 months ago, # |   -15 I am so psyched.
 » 11 months ago, # |   +3 Desire for becoming Candidate Master tonight!! :)
•  » » 11 months ago, # ^ |   +20 Good luck! Hoping to get master
•  » » » 11 months ago, # ^ |   -55 You won't
•  » » » » 11 months ago, # ^ |   +15 thanks mr master
•  » » » » 11 months ago, # ^ |   0 orz you can tell the future
•  » » 11 months ago, # ^ |   -6 Me too!!! :)
 » 11 months ago, # |   +9 Thank you, "spsk spsk"
 » 11 months ago, # |   0 there is a problem with account link ? "The problems were invented and prepared for you by danilz1806, baumanec " both link to ur account
•  » » 11 months ago, # ^ |   +15 He owns half of the master accounts on Codeforces
•  » » » 11 months ago, # ^ |   +9 Are you him?
•  » » » » 11 months ago, # ^ |   +7 I refuse to give information to the penguin intelligence agency.
•  » » » 11 months ago, # ^ |   +19 but they share the same link with the same profile i mean when u press on "danilz1806" its gonna open "sorry_marymarine" profilesorry for bad english :|
•  » » » » 11 months ago, # ^ |   +22 When you change handle, your old handle links to your account iirc.
 » 11 months ago, # |   0 Nice idea to overcome downvotes u got b4.
 » 11 months ago, # |   +6 Please fix long testing queue for pretests during contests. It's really annoying to wait for results during contest . Thanks
 » 11 months ago, # |   -13 Questions made are excellent but I would suggest to improve the testing queues during submissions. I can understand it is a complex job to do given that many submissions are made in a single instant but if this fault is cleared, then people will be more motivated to take part in such thrilling contests. :)
•  » » 11 months ago, # ^ |   +12 Please read previous comments before writing one.
 » 11 months ago, # |   0 I don't know how to tell you, because I'm only a pupil.
•  » » 11 months ago, # ^ |   +15 Tiat is so cute! (Tiat is the girl in the picture)
 » 11 months ago, # |   -8 I will become expert after the contest :))
•  » » 11 months ago, # ^ |   0 woooo！You are so great that you will become expert！
 » 11 months ago, # |   0 Is it rated guys??Coz, I know Nothing.
•  » » 11 months ago, # ^ |   +93 It is only rated for women
•  » » » 11 months ago, # ^ |   +12 Can you PLEASE share your algorithm to identify female coders?
 » 11 months ago, # |   0 With such army of tester, I expect super strong pretest.
•  » » 11 months ago, # ^ |   +13 quantity =/=> qualityalthough, it's good to be optimistic.
•  » » 11 months ago, # ^ |   0 When I finished 2 Ds, I felt scary. But when I saw my comment here, no more fear.
 » 11 months ago, # |   +2 Hoping to get the last point to be a Candidate Master!! :)
 » 11 months ago, # |   +29 About 20 people trying to make a contest for us. How lucky we are. :D
 » 11 months ago, # | ← Rev. 2 →   0 The Final Testing'll be directly After The Contest or After 12 hours of Contest end :) ?
 » 11 months ago, # |   +2 15 peoples are tester for contest. <3 I thinks this round don't need hacking. I'm afraid =))))))
•  » » 11 months ago, # ^ |   +1 I just solved some problems and gave some advice to make statements better, I didn't try to submit wrong or tricky solutions. Most of other testers too, I think.
•  » » » 11 months ago, # ^ |   0 <3
 » 11 months ago, # |   +1 For me you are Mr Master.
 » 11 months ago, # | ← Rev. 2 →   +6 clashes with Mineski VS Na'Vi :(
 » 11 months ago, # |   0 why I can't get registered
•  » » 11 months ago, # ^ |   0 over time
•  » » » 11 months ago, # ^ |   0 what it mean
 » 11 months ago, # |   0 Where is the link to ask a question? I think I rember that on every problem page there was such a link, but can not find it. :/ Is it gone? (Maybe caused by to much stupid questions ;)
•  » » 11 months ago, # ^ |   0 In the problems page.
 » 11 months ago, # |   +12 BINARYFORCES!!!
 » 11 months ago, # |   +18 The word "subsequnce" appears 7 times in the problem statement of D1 and D2
•  » » 11 months ago, # ^ |   0 haha
•  » » 11 months ago, # ^ |   +8 How many time subsequence appear as a subsequence in the problem statement?
 » 11 months ago, # | ← Rev. 2 →   0 maybe I got it. my bad
•  » » 11 months ago, # ^ |   +4 Ask a question
•  » » 11 months ago, # ^ |   +10 Better dont discuss problems while the contest is still running.
 » 11 months ago, # |   +10 Uh, why does solving D2 not auto solve D1? RIP penalty. ;_;
•  » » 11 months ago, # ^ |   +5 When did it ever do that
•  » » » 11 months ago, # ^ |   +8 In my dreams and imaginations -- Pretty much what happens after one engages to work in the industry and cares about user experience. Kappa
 » 11 months ago, # |   0 What is test case 13 for C?
 » 11 months ago, # |   +125 My score has plunged to 532Calc Pro XD
•  » » 11 months ago, # ^ |   +15 You gotta be kidding me :(
•  » » 11 months ago, # ^ |   0 How did that happen? What is the logic behind it?
•  » » » 11 months ago, # ^ |   +6 He made a lot of wrong hacks.
 » 11 months ago, # |   +75 I hope this is the first and last time i ever see 998244853 in a contest.
•  » » 11 months ago, # ^ |   +4 What is the problem with 998244853?
•  » » » 11 months ago, # ^ |   +27 It's not 998244353.
•  » » » 11 months ago, # ^ |   +2 The algorithm NTT often modulo 998244353,and 998344853 looks like 998244353
•  » » » » 11 months ago, # ^ |   0 I apologize for that eyes are not needed in coding competitions but Ctrl-C+V. I have thought the number was just that number.
•  » » 11 months ago, # ^ |   +10 Agreed, I prefer 993244853 instead.
 » 11 months ago, # |   0 Does anyone know why I TLE on pretest 13 of prob. C. I'm pretty sure my algorithm runs in O(n^3 + m) worst case which should fit in the bounds.
 » 11 months ago, # |   0 Nice task E, thanks)
•  » » 11 months ago, # ^ |   0 What was the solution for E?
•  » » » 11 months ago, # ^ |   +15 dp or mathematical derivation
 » 11 months ago, # |   +11 How to solve C ??
•  » » 11 months ago, # ^ | ← Rev. 3 →   +5 I tried greedy, but I got WA on 5th. Never mind, I had a bug. It is a greed algorithm. O(n^3) (Floyd–Warshall) + O(m) linear search get we erase b in this scenario (a — b — c). If dist[a][c] == dist[a][b] + dist[b][c] then we can erase b, otherwise he stays in array.
•  » » » 11 months ago, # ^ |   0 I was trying to figure out the condition which can be used to remove element from p(i). But found nothing. :(
•  » » » » 11 months ago, # ^ |   0 Condition to erase p[i] :There is a j and a k such that j
•  » » 11 months ago, # ^ | ← Rev. 7 →   +11 You can apply Greedy algorithm. For each triplet, ( left, current, right ), if you can go from left --> current and from current --> right ,but you can't directly go from left to right, then we can remove current. This ensures that the shortest path from left to right includes current. Hence, it retains the original sequence.You can use a stack to process every triplet.The time complexity is O(m + n*n).Code
•  » » 11 months ago, # ^ |   +6 You can make a Floyd-Warshall to calculate the APSP,then you just need to search the sequence (starting with the first number) the number that is farther away and that the difference in positions is the minimum path between those two, then you keep it and go to that one and repeat it until you reach the end,O(N*M)
 » 11 months ago, # |   0 I submited D1 without any testing or even compiling in last 30s an it passed, tests are probablu awful for this one.
 » 11 months ago, # |   0 Bonus for E. Solve it in $O(n)$
•  » » 11 months ago, # ^ |   0 I think problem E would be much easier if the constraints are set to fit $O(n)$, e.g. $n \leq 100000$, because one need not consider an $O(n^2)$ approach instead, which could simplify thinking.
 » 11 months ago, # | ← Rev. 4 →   0 Upd: Ignore, got it.In div2E, did we have to use the fact that number of sequences whose maximal prefix sum is k is equal to product of catalan numbers($C_{x_{i}}$) such that sum of $x_{i}$ is n-k)?
 » 11 months ago, # | ← Rev. 2 →   +3 E can be solved in O(n+m) 59161848to solve this you need to calculate C(n, r) in O(n) preprocess and O(1) query
 » 11 months ago, # |   +9 Maybe I should call this round...UnsuccessfulSubmissionForces.Problem A and C are really tricky.
 » 11 months ago, # |   0 Anybody want to explain D? The last example does not make sense to me.0111001100111011101000Answer should start with 000100... but the example says 001100...Why? Which condition would not be satisfied if the answer starts with 000100...?
•  » » 11 months ago, # ^ |   +5 Any subsequences, not only consecutive.
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 Consider subsequence in [3,6]. The longest non-decreasing in input is 2, but your example is 3.
•  » » 11 months ago, # ^ |   +2 In 001100 the longest non-decreasing subsequence is 4 In 000100 the longest non-decreasing subsequence is 5But in input string the longest non-decreasing subsequence s[1:6] = 4, not 5!
•  » » 11 months ago, # ^ |   0 You're considering sub-string(s) . For 't' we have to consider sub-sequences.
 » 11 months ago, # | ← Rev. 2 →   +29 If you know Catalan number's formula's proof, you could solve E with complexity O(n)
•  » » 11 months ago, # ^ |   0 Can you explain it more clearly ? Thank you !
•  » » » 11 months ago, # ^ | ← Rev. 6 →   0 You can read this and use the trick which is presented in proof. You can calculate : Number of array that has max-prefix greater or equal to x
•  » » 11 months ago, # ^ |   -8 Do you have any other problems that use the same technique? :)
•  » » » 10 months ago, # ^ |   0 https://codeforces.com/contest/26/problem/DThis is basically the same though.
 » 11 months ago, # |   +3 Nice problem D
•  » » 11 months ago, # ^ |   0 how to solve?
•  » » » 11 months ago, # ^ |   0 We turn the array over, then we consider zeros and ones at each step and say, if zeros are less  or  equal then ones, then we put zero in a new line
•  » » » » 11 months ago, # ^ |   0 why would that work?
•  » » » » » 11 months ago, # ^ | ← Rev. 3 →   +5 because if the number of zero is smaller than the number of one than you turn this number(1) into 0 can effect the number of zero ,it adds 1.but the number of one doesn't change. UPD:and you didn't change the biggest
•  » » » » » » 11 months ago, # ^ |   0 Good idea!
•  » » » » » » 11 months ago, # ^ |   0 how you know it won't change the LIS for all the substrings?
 » 11 months ago, # |   0 What is the trick in p.A?
 » 11 months ago, # |   0 I am a new to hacking. Is hacking allowed only during the contest?
•  » » 11 months ago, # ^ |   +5 In normal rounds yes, but in the extended ICPC rules you get 12 hours of open hacking after the contest ended.
 » 11 months ago, # |   +4 Feels really great when you finish debugging C 40s after the contest ended :(
 » 11 months ago, # | ← Rev. 2 →   +2 What about problem C? Is it Floyd–Warshall algorithm?
•  » » 11 months ago, # ^ |   +1 BFS for each vertex works well too.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 You can apply Greedy to solve it in O(m + n*n ).Explanation
 » 11 months ago, # |   +10 I don't understand problem C.What " and p is one of the shortest paths passing through the vertexes v1, …, vk in that order." means?
•  » » 11 months ago, # ^ | ← Rev. 6 →   0 It means, that there is no strictly shorter path than p passing through all vertexes v1, ..., vk in that order.
•  » » » 11 months ago, # ^ |   0 And i should find the shortest sequence of vertices that this path 'P' pass through?Whether yes or no, Could you explain more about what should the output be?
•  » » » » 11 months ago, # ^ |   +3 Yes.Since $v$ is a subsequence of $p$, I will define another sequence, $a$, such that for all $i$ in range $[1, k]$ $p_{a_i} = v_i$ and $a$ is ascending. You should output a sequence $v_1, v_2, \ldots , v_k$ such that: $v$ is of course a subsequence of $p$ $v_1 = p_1$, $v_k = p_m$ for all $i$ from $1$ to $k-1$ the length of shortest path between $v_i$ and $v_{i+1}$ is equal to $a_{i+1}-a_i$ there is no subsequence of length strictly lesser than $k$, for which above three conditions are all true For example in test 4 0110 0010 0001 1000 4 1 2 3 4 The proper answer is 3 1 2 4 because: it is a subsequence of $(1, 2, 3, 4)$ the first and the last elements of both sequences are equal for all $i$ from $1$ to $k-1$ the length of shortest path between $v_i$ and $v_{i+1}$ is equal to $a_{i+1}-a_i$: shortest possible path from $1$ to $2$ has length 1 shortest possible path from $2$ to $4$ has length 2 there is no subsequence of length $1$ or $2$ that satisfies all these three conditions
•  » » » » » 11 months ago, # ^ |   +3 I got it, thank you very much.
 » 11 months ago, # |   0 B was very interesting but had nice proof
 » 11 months ago, # |   0 First competition so I have a few questions. - When do we get our rating? - How do you read the score distribution? I'd be grateful if anyone could answer.
•  » » 11 months ago, # ^ |   0 The ratings need like an hour or so, sometimes more.Score distribution? There is a link to "Standings".
 » 11 months ago, # | ← Rev. 3 →   +3 Actually, the first problem was the hardest
•  » » 11 months ago, # ^ |   +3 I would not say the hardest, although clearly harder than B for me
•  » » » 11 months ago, # ^ |   +6 I suppose the first two problems' placement could be swapped
 » 11 months ago, # | ← Rev. 2 →   +1 who can tell me the thinking process about Pro.C,never solve the pro.c since came here
•  » » 11 months ago, # ^ |   0 And the meaning of "The main characters have been omitted to be short."
•  » » » 11 months ago, # ^ |   +12 That means "Let's skip the little useless story and go straight to the problem"
 » 11 months ago, # |   0 What's wrong with this solution? Problem A 1- Read the user input as a decimal value in a variable s 2- Output the round up value of log4(s) for exemple 100000000 is 256 in base 10 and log4(256) is 4 because power(4,4) = 256 and 101 is 5 and the round up of log4(5) is 2 and so on ...
•  » » 11 months ago, # ^ |   0 With numbers up to 2^256 I think using that might be not precise enough.
•  » » » 11 months ago, # ^ |   0 I think the logic is okay the problem is in my implementation I'm using C++ and I used a variable s as uint64_t so I can only store 64 bits so when the user input is more than 64 bits I got problems so I have to use a type where I can store 100 bits if someone know a type in C++ where I can store more than 100 bits please help
•  » » » » 11 months ago, # ^ |   +3 string *_*
•  » » » » » 11 months ago, # ^ |   +5 I can't use string in log fonction xD
•  » » » » » » 11 months ago, # ^ |   +5 you can... If you think about it the length of the string is very closely tied with the log2 value
•  » » » » » » 11 months ago, # ^ | ← Rev. 2 →   0 I don't think you need a log function here, it would work on smaller bits(when you are converting to decimal) but for 200 bits its not possible to convert it into decimal, that's why string is used, with some check(even/odd) for the indices, you can get the answer.check this solution : 581 DIV 2 A
•  » » » » 11 months ago, # ^ |   0 typedef __int128 lll;
•  » » » » » 11 months ago, # ^ |   0 Compilation error! program.cpp:8:5: error: '__uint128_t' was not declared in this scope I can't use __uint128_t in codeforces even it's works nice on my computer
•  » » 11 months ago, # ^ |   0 I tried the same solution using string and it didn't work for me https://codeforces.com/contest/1204/submission/59172843
 » 11 months ago, # |   0 Could someone help me figure out what is wrong in my logic in question C. 59182371
•  » » 11 months ago, # ^ |   0 Even I am facing same problems. Would appreciate if someone could explain it.
•  » » 11 months ago, # ^ |   0 I mean, they don't need to be adjacent to have a shortest path that goes around the 'inter' in your code.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +5 After experimenting with various test cases, I finally came up with one that your code fails on. I hope this will help you better in understanding where you went wrong4010100100001000041 2 3 4 The expected answer is of length 3 , but your code outputs a sequence of length 2.Hint : Suppose we have a sequence (a,b,c,d). We take a into our path. We cannot reach c from a, hence we neglect b. Now, we cannot reach d from c, hence we also neglect c. This is where you went wrong. Since we've already deleted b, we should check the condition on the triplet (a,c,d).
 » 11 months ago, # |   +28 15 testers and even the basic test cases are not covered for problem C. A simple path graph of length 5 is enough to hack a guy. Why were all the basic cases not covered?http://codeforces.com/contest/1204/submission/59167944
•  » » 11 months ago, # ^ | ← Rev. 5 →   +8 When testing, testers mostly gave feedback on the problems, not the tests. Also, all testers who solved C did so without running into this test case.And just because a single case wasn't covered doesn't mean all basic cases weren't covered. A lot of edge cases were covered, for example: 2 0100 2 1 2 System tests and hacks are a part of Codeforces, it's really hard to avoid and check every single case. Please be considerate of the authors for taking the time to put the round together and writing the problems. It's a shame this happened to many participants. Best of luck in the future.
•  » » 11 months ago, # ^ |   +9 dude, the humans' idiotism, retardness and stupidity don't have limits.
•  » » » 11 months ago, # ^ |   +3 I can understand people posting weird-ass solutions which could pass sometimes, but there should have been a path graph test case in there somewhere.
•  » » 11 months ago, # ^ |   0 See the glass as half full: you have the opportunity to hack someone.
 » 11 months ago, # |   +3 Will you provide the table of most hacks?
 » 11 months ago, # |   0 it's quite strange, but i couldn't open cf on time when todays contest has started. after one hour of useless attempts to open cf i tried to change my wifi connect to another one. and suddenly it opened. wifi connect which couldn't open cf, opened any other website except cf. what's the matter?
 » 11 months ago, # |   0 What was the intended solution for D?
 » 11 months ago, # |   0 what is the problem with s.size() and (ll)s.size()? s.size() gives wrong answer but (ll)s.size() gives correct answer.With (ll)s.size() https://codeforces.com/contest/1204/submission/59182674
•  » » 11 months ago, # ^ |   0 s.size() returns size_t type integer, where size_t is an unsigned integral data type. So, it can't be negative.
•  » » 11 months ago, # ^ |   0 s.size() has type size_t, if say size is 1 and you subtract 2 from it, it won't go to -1, it wraps around, see this : size_t in reverse for loopusing ll ensures proper conversion. :)
•  » » » 11 months ago, # ^ |   0 I face this problem many times in codeforces only. I don't face this problem in any other sites like codechef etc.
 » 11 months ago, # |   0 Why 1e8 operations doesn't fit to 2 sec in C, when 1e9 fit to 1 sec in Codeforces? Even when I make 1e7 for get WA I get TLE can anyone explain?
•  » » 11 months ago, # ^ |   +13 shit I wrote for (int j = i - 1; j >= max(1, j - 100); j--) { instead for (int j = i - 1; j >= max(1, i - 100); j--) { get AC in 0.6 s
 » 11 months ago, # | ← Rev. 3 →   +1 Test case 2 in problem C. I don't understand why not true??? May be Im wrong??? Help me. Thanks you so much <3
•  » » 11 months ago, # ^ |   +2 there is an arc from 3 to 1
•  » » » 11 months ago, # ^ |   0 sorry :< i thought 4 cases is the same
 » 11 months ago, # |   +5 I am a newbie now. I want tips how to become a legendary grand newbie. Help is highly appreciated
•  » » 11 months ago, # ^ | ← Rev. 2 →   +16 "legendary grand newbie" ??I'm confused!!!
 » 11 months ago, # |   0 I am confused in test case 3 of problem C. Why the solution of test case 3 in Problem C can't be 6 1 2 3 3 2 1. Even if 1 is deleted from the sequence , shortest path from 3 to 3 is of distance 2 only.
•  » » 11 months ago, # ^ |   +11 In the problem statement it is clearly mentioned that — "Any two consecutive numbers should be distinct"
•  » » 11 months ago, # ^ |   +3 Miss that adjacent elements on the array v must be different
 » 11 months ago, # |   +3 That's rally quite strage, that this army of testers didn't crash my solution in D2 (I did it after the end of the contest), in the worst sitation I have O(n^2), but on max systemtest my solution got only 30 ms. Sorry, for my poor englishhttps://codeforces.com/contest/1204/submission/59180412
•  » » 11 months ago, # ^ |   -23 dude, the humans' idiotism, retardness and stupidity don't have limits. i can't foresee which bad solutions can you invent
•  » » » 11 months ago, # ^ |   0 But you must
•  » » » » 11 months ago, # ^ |   0 but i can't.
•  » » » 11 months ago, # ^ |   +14 **But I thing this test is rather simple max_test (10000*("110")+20000*("10")+10000*("100")) or many others where there arу many non-decreasing sub-segments in a minimal partition, that's not soo hard to constract this test
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 If I were the author of the solution, I would be really offended by your comment.
•  » » 11 months ago, # ^ |   0 Most people in "army of testers" (at least me) just wanted to solve the round beforehand and didn't work on wrong solutions.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +12 I thought that one of the most important thing is to try to build good maxtest. It's not quastion for you, it's a quastion for organisator of testers' work. And there are some hacks of task C with really simple tests too(n=4 and m=4)!
 » 11 months ago, # |   0 what a smooth contest!No announcement and also fast testing.
 » 11 months ago, # |   +11 every thing about this contest is really good, but the best thing is sorry_marymarine'comments on this post lol
 » 11 months ago, # |   0 I solved problem C in O(m) without using Floyd-Warshall and without computing shortest paths. Here is my code: 59178907
•  » » 11 months ago, # ^ |   +5 I also applied a similar logic. Although it cleared all the test cases (still does), but there is a big flaw in the logic. After dry running it a couple of times, I came up with this test case which fails with your code.4010000100001000041 2 3 4 This is a linear chain. The answer should be of length 2. But your code produces an answer of length 3. The test cases for this question are too weak.
 » 11 months ago, # | ← Rev. 2 →   0 Test #4 in problem D1 Why isn't 0001000100001000101000 the answer? Maybe I didn't get the problem right, but I don't see values of l and r which can fail the test.I've even cheched it for every [l;r] in program. //before for(short int l=0;l=s[i-1]) loc++; else { if(loc>max) max=loc; loc=1; } i++; } if(loc>max) max=loc; before[l][r]=max; } //changing the string short int i=0; while(s[i]!='\0'){ if(s[i+1]!='0' && s[i]=='1') s[i]='0'; i++; } //after for(short int l=0;l=s[i-1]) loc++; else { if(loc>max) max=loc; loc=1; } i++; } if(loc>max) max=loc; if(before[l][r]!=max) printf("\n%hi %hi",l,r); else printf("\nok"); } 
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 First 6 characters "011100" has a good subsequence of size at most 4 while "000100" has size 5
•  » » » 11 months ago, # ^ |   0 Why is the size of second good subsequence is 5? How does it look? Isn't it "0001" for "000100"?
•  » » » » 11 months ago, # ^ |   +2 "00000"it's a subsequence not a substring.
•  » » » » » 11 months ago, # ^ |   0 I got it now, thanks!
 » 11 months ago, # | ← Rev. 2 →   +12 solution for problem D2. So fun =))
 » 11 months ago, # |   +5 +262 good contest
•  » » 11 months ago, # ^ |   +3 +8 rating next contest =)) good luck
 » 11 months ago, # |   +2 Finally reached blue :)
 » 11 months ago, # | ← Rev. 2 →   +23 E can be visualised as a path counting problem in an $n$ by $m$ grid. Where going up is +1 and right is -1. And can be solved in $O(n+m)$.Let $F(i)$ be the number of paths from $(0, 0)$ to $(n, m)$ that satisfy each point $(x, y)$ in the path satisfies $x - y \leq i$.Answer is summation of $(i . (F(i)-F(i-1)))$ for $i$ in $1$ to $n$.$F(i)$ can be found by counting all the bad paths for $i$ and subract it from total paths $(C(m+n,m))$. A bad path is a path where there exists atleast one vertex that is of the form $(y+i, y)$, in other words, the path meets the line $x-y=i$. It can be seen that the bad paths, given $i$ have a bijection with paths from $(0,0)$ to $(m+i+1, n-i-1)$. (If we swap the number of up and right moves from the first point of intersection with $x-y=i$). Number of bad paths is $C(n+m, m+i+1)$.So $F(i)$ is just $max(C(n+m,m)-C(n+m,m+i+1), 0)$Also, feels good to be on the blog for the first time :)
»
11 months ago, # |
Rev. 2   +17

C can't be solved without using Floyd Warshall (equivalently, BFS from all vertices)

Going through the solutions of problem C, I have observed a lot of people (including me), solve the question without using Floyd Warshall and deleting vertices in a greedy manner. Although the solution passes all the system test cases, I believe it is wrong.

People have used 2 approaches for greedily deleting the vertices.

Approach 1 :: Checking every window of size 3 without modifying the array.

This approach fails for this test case.

4
0101
0010
0001
0000
4
1 2 3 4

Expected 1 3 4
Output 1 4

Approach 2 :: Checking every window of size 3 (while actually deleting elements using stack).

This approach fails for this test case. 4
0100
0010
0001
0000
4
1 2 3 4

Expected 1 4
Output 1 2 4

sorry_marymarine Can you add these test cases to the problem ?

•  » » 11 months ago, # ^ |   0 I fail in C because my bfs counts only one way from u to v (if v has other way) Today morning I fix it and get AC. I think that my solution also greedy.
•  » » » 11 months ago, # ^ |   +1 As I said, BFS from each vertex is essentially the same as Floyd Warshall. The time complexity of your code is O(n*m + n*n*n). My point is that you cannot lower that O(n^3) factor to O(n^2).
 » 11 months ago, # | ← Rev. 2 →   +4 finally expert :)
 » 11 months ago, # |   +27 When you want to troll ~12k contestant with 998244853 but almost no one got tricked Spoileradmittion
•  » » 11 months ago, # ^ |   0 I believe that nobody reads the number!! just copy-paste it!!
•  » » 11 months ago, # ^ |   +5 I spent 30 minutes on this module number. I have wrote the code of E for 3 times. At first I use the math formula. It's right and the complexity is $O(n)$. At last I use $O(n^2)$ dp. I won't believe the module number any more. 555...
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +13 Me too.And even worse,I spent 2h on this number without finding out it. Perhaps I am a fool:(I learnt a lesson,and it taught me a lot
 » 11 months ago, # |   +13 Does anynoe use modulo 998244353 on problem E like me...
•  » » 11 months ago, # ^ |   +5 I think you can't pass the fifth sample if you use 998244353... XD
•  » » » 11 months ago, # ^ |   0 Yes.And I thought my solution is wrong until I found it.
•  » » » » 11 months ago, # ^ |   0 Your previous submissions don't even have modulo hardcoded. Did you type ...353 by memory? It is one of the things you should never do on contests. If something is written in the statement, copy it from there.
•  » » » » » 11 months ago, # ^ |   0 Yes.Now I learned a lesson.
 » 11 months ago, # | ← Rev. 2 →   +13
 » 11 months ago, # |   0 I am solving the problem c in o(n3 + m) time complexity still getting a tle Here is a link to my solution , can somebody please help me https://codeforces.com/contest/1204/submission/59177220
 » 11 months ago, # | ← Rev. 4 →   0 Please help me with this test case. ( Problem C) 4 0110 0001 0001 0000 3 1 2 4The answer according to accepted code is2-> 1 4But if you draw the graph you can see that there is another road to go from '1' to '4' which is 1--3--4.So why the answer is 2-> 1 4.I think it may be 3-> 1 2 4.Help me with proper logic of this test case.Thanks in advance
•  » » 11 months ago, # ^ | ← Rev. 4 →   0 Important only that way from 1 to 4 shortest (not important how many ways exist).I think it means that you can't restore original way from correct solution and it not necessary.
•  » » 11 months ago, # ^ |   0 To prove, that this is correct answer for this problem, suppose, that there exists a correct answer of strictly lesser length than 2 (in this case we are only considering a subsequence of length 1).Of course a path of length 1 is incorrect for this test case, because (from the statement) the first and the last elements of path $p$ and its subsequence $v$ must be equal, so if path of length 1 would be correct, we would have $1 = p_1 = v_1 = v_k = p_m = 4$, so there is no correct answer of length strictly lesser than 2.We proved that the answer's length is at least 2, so now we can prove, that $v = (1, 4)$ is a correct answer: $v$ is a subsequence of $p$ $v_1 = p_1 = 1$, $v_k = p_m = 4$ the shortest path between vertexes $v_1 = 1$ and $v_2 = 4$ has length 2 As you can see $v = (1,4)$ satisfies all needed conditions, so it is a correct answer.
•  » » » 11 months ago, # ^ |   +3 Thank You
 » 11 months ago, # |   0 Why problem d was two parts? I think E Should be two parts
 » 11 months ago, # |   0 The system test of Problem C is too weakI hacked about 15 solutions after the contest!
•  » » 11 months ago, # ^ |   +4 sorry for this. i am rather unexperienced problemsetter and i can't foresee all the wrong solutions to invent the countertests
 » 10 months ago, # |   0 Hello! I think that the output for the fourth input of this problem D1 has mistake.Because the longest non decreasing subsequence of output is 13, but the input is 12. If i made a mistake help me understand.Sorry for my poor english.
•  » » 10 months ago, # ^ |   0 both have the same length of the longest nondecreasing subsequence. please don't say "the output is wrong" 2 weeks after a contest. it was carefully prepared, tested and then a lot of participants solved that problem.
 » 8 months ago, # |   -10 Your round is one of the best rounds I have participated in. Thanks a lot