### Блог пользователя Loud_Scream

Автор Loud_Scream, 9 месяцев назад, ,

Всем привет!

В понедельник 24 июля в 17:35 MSK состоится рейтинговый Codeforces Round #425 для участников из второго дивизиона. Как всегда, участники из первого дивизиона могут принять участие вне конкурса.

Это мой первый раунд. Хотелось бы сказать большое спасибо Николаю Калинину (KAN) и Алексею Илюхову (Livace) за помощь в подготовке задач, Ильдару Гайнуллину (gainullin.ildar), Даниилу Николенко (qoo2p5) и AmirReza PoorAkhavan (Arpa) за прорешивание задач, а также Михаилу Мирзаянову (MikeMirzayanov) за системы Codeforces и Polygon.

Участникам будет предложено пять задач и 2 часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

Всем удачи и высокого рейтинга!

UPD1: Разбалловка для этого раунда: 500 — 1000 — 1750 — 2000 — 2500.

UPD2: Поздравляем победителей! Разбор тут.

Div.2 :

Div.1 :

•
• +123
•

 » 9 месяцев назад, # |   -16 Автокомментарий: текст был обновлен пользователем Loud_Scream (предыдущая версия, новая версия, сравнить).
 » 9 месяцев назад, # | ← Rev. 2 →   +31 Is it just me wondering about that "a." at the end. :P EDIT: Its removed, it must have been a typo. :)
 » 9 месяцев назад, # |   +43 How to solve E?
•  » » 9 месяцев назад, # ^ |   +96
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   +23 I didn't test below algorithm but I think it works :fist solve then code :D
•  » » » 9 месяцев назад, # ^ |   +6 Solved it 2 minutes after the contest.
•  » » 9 месяцев назад, # ^ |   +46 It's a well known problem. Google it.
•  » » » 9 месяцев назад, # ^ |   +34 Well, I coded the n^4 dp, and then found the generating function in OEIS
•  » » » » 9 месяцев назад, # ^ |   0 Haa hmm ok
 » 9 месяцев назад, # |   0 5 problems or 6 ?
•  » » 9 месяцев назад, # ^ |   0 5
 » 9 месяцев назад, # |   -59 is it rated?
•  » » 9 месяцев назад, # ^ |   +59
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   -45 When asked "is it rated"
 » 9 месяцев назад, # |   +2 I am curious about the process of choosing the author of the contest. does anyone have any information?
•  » » 9 месяцев назад, # ^ | ← Rev. 3 →   +17 I think when you offer contest, you get in queue, then coordinator checks problems and if they're good enough, contest is held.Btw, you have to have rating 1600+ to offer contestCheck this
 » 9 месяцев назад, # |   0 Who is the hero of round?
•  » » 9 месяцев назад, # ^ |   +120 I hope no one, so we can get short statements.
•  » » » 9 месяцев назад, # ^ |   +7 By no one, do you mean the faceless god? (Get it?) :P
•  » » » » 9 месяцев назад, # ^ |   +31 I think everyone GoT it :P
•  » » » » 9 месяцев назад, # ^ |   -11 Khaleesi approves
 » 9 месяцев назад, # |   -61 is it rated :p
•  » » 9 месяцев назад, # ^ |   -36 Fuck off man -_- -_-
•  » » » 9 месяцев назад, # ^ |   -44 The guy was obviously kidding. Just downvote him if you don't like his post. No reason to swear.
•  » » » » 9 месяцев назад, # ^ |   -37 Seriously? I'm getting downvoted for trying to keep the level of discussion decent? Nice! :)
 » 9 месяцев назад, # |   0 Its my first contest here, any suggestions!!
•  » » 9 месяцев назад, # ^ |   +16 don't get hacked
•  » » » 9 месяцев назад, # ^ |   0 What exactly do you mean?
•  » » » » 9 месяцев назад, # ^ |   +1
•  » » » » » 9 месяцев назад, # ^ |   0 Thanks, got it...
•  » » 9 месяцев назад, # ^ |   +8 Relax and have fun. Spend time learning what you did not know after you're done (read the editorials, and try to solve the problems again).Repeat this for every contest :)
•  » » » 9 месяцев назад, # ^ |   0 Thank you so much for such an honest advice #potaters
 » 9 месяцев назад, # |   -40 Is it rated?
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   +4 On July 24, в 17:35 MSK rated Codeforces Round #425 (Div. 2) will be held. :D
•  » » » 9 месяцев назад, # ^ |   +1 QwQ...Thx.
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   -8 :(
 » 9 месяцев назад, # | ← Rev. 3 →   -7 deleted
•  » » 9 месяцев назад, # ^ |   +4 +1. Good luck!
•  » » » 9 месяцев назад, # ^ |   0 thanks
 » 9 месяцев назад, # |   0 Хде разбалловка?
 » 9 месяцев назад, # | ← Rev. 2 →   -8 KAN 'THE GOD'of testing problems _/_
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   +5 7000+ registrations wow!!
 » 9 месяцев назад, # |   0 unable to register
 » 9 месяцев назад, # |   +6 unable to register
•  » » 9 месяцев назад, # ^ |   +5 Same here, I pressed the "register" button, "entered" the contest, and it won't let me submit anything?
 » 9 месяцев назад, # |   +8 Hope to become green.
 » 9 месяцев назад, # |   +1 You have only 2000 pts for D?
•  » » 9 месяцев назад, # ^ |   +1 Well we had a lot of rounds where people whine about having a sharp difficulty cut off between C and a 2500pt D, so .... yeah.
•  » » » 9 месяцев назад, # ^ |   0 But my D sol is monstrous :(
•  » » » » 9 месяцев назад, # ^ |   0 I didn't noticed that the round has already started. :P"
•  » » 9 месяцев назад, # ^ |   +16 For me D felt easier than B(I am not sure about correctness though).
 » 9 месяцев назад, # |   -60 does any body have any idea about code b,test 4? my code get wrong answer and i'm doing the same as it said!!!
•  » » 9 месяцев назад, # ^ |   0 Don't ask for idea or clue about the contest problems, during running contest. :)
•  » » » 9 месяцев назад, # ^ |   0 tnx.
 » 9 месяцев назад, # |   +2 anyone else facing a long queue?
 » 9 месяцев назад, # | ← Rev. 2 →   0 My first Div 1 contest .
 » 9 месяцев назад, # |   +67 My first Div. 1 contest .
 » 9 месяцев назад, # |   +3 It took me a lot of time to actually get that this statement in Problem B "It is guaranteed that the total length of all query strings is not greater than 10^5", means "Sum of length of all strings over all queries don't exceed 10^5"I guess the statement was not quite clear..!
•  » » 9 месяцев назад, # ^ |   0 if that's true than life's weird .
•  » » 9 месяцев назад, # ^ |   0 damn only noticed that now
•  » » 9 месяцев назад, # ^ |   0 Actually this type of statement appears in many problems in the previous rounds too. Better be careful next time.
•  » » 9 месяцев назад, # ^ |   +8 that shouldn't keep you from coding your O(n) solution since reading will always take O(n)... So if you had 10^5 string with size 10^5, the problemsetter would already have to set a high time limit just for reading, which would allow you to solve the problem in the expected O(n) way...
•  » » 9 месяцев назад, # ^ |   +1 That is why you can ask questions in the contest. I asked it and got the answer straightaway.
 » 9 месяцев назад, # |   -24 Too much lag make it unrated :D
 » 9 месяцев назад, # |   0 You won't believe how I tried to solve D :v
 » 9 месяцев назад, # |   +45 LGTwins — Legendary Grandmaster Twins?? :DD
 » 9 месяцев назад, # |   +8 Never try to hack out of bounds for cpp solutions. Lesson learned :/
 » 9 месяцев назад, # |   +11 Oh, that funny task about a bomb...
 » 9 месяцев назад, # | ← Rev. 3 →   0 EDIT: Never mind
 » 9 месяцев назад, # |   -9 Intended solution for D isn't bruteforces O(n2),right?
•  » » 9 месяцев назад, # ^ |   0 O(n^2) is too much. 10^10 operations would definitely take more than 2 seconds.
•  » » » 9 месяцев назад, # ^ |   0 Yeah,I know-I'm just surprised with 500+ acc on D.
•  » » 9 месяцев назад, # ^ |   0 I using Segment tree + LCA to solve this problem.
•  » » » 9 месяцев назад, # ^ |   +3 I did LCA with sparse table except it timed out because I managed to build the sparse table N^3 times...
•  » » » » 9 месяцев назад, # ^ |   0 Sparse table could not update quickly :). Btw, I also using permutation to try all the possible ways.
•  » » » » » 9 месяцев назад, # ^ |   0 No need to update it, you can calcucate all the queries by picking an arbitrary root for the tree.
•  » » » » » » 9 месяцев назад, # ^ |   0 Hmm, it really interesting :D. Btw, you also use HLD to find LCA ?
•  » » » 9 месяцев назад, # ^ |   +9 Isn't using DFS + LCA enough ?
•  » » » » 9 месяцев назад, # ^ |   0 I think it would be TLE, because it could be maximum n nodes for each shortest path.
•  » » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   +4 TrueLove You don't need to pass through every node on the path to the LCA, you can precalculate with a dp and find it in O(log n)
•  » » » » » 9 месяцев назад, # ^ |   +3 No I mean in pre-processing phase, I used dfs to calculate the distance f[u] from u to root (which is 1).
•  » » » » » » 9 месяцев назад, # ^ |   0 4k1502 I don't think so, because sometimes you don't need to travel to root to find the shortest path.
•  » » » » 9 месяцев назад, # ^ |   +3 yeah I thought about LCA but my solution was giving WA in pretest 6... I can't see why it wouldn't work -- fix a station A, get the LCA between B and C (call it L). If L equals A, the answer is 1. If L is either B or C, the answer is the minimum distance (A, B) or (A, C). Otherwise, the answer is the distance (A, L). I even permuted A, B, and C to get all possible combinations since the LCA runs fast. Why is that incorrect?
•  » » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 I also got WA on pretest 6. I think I failed in solving some corner case.
•  » » » » » 9 месяцев назад, # ^ |   0 Oh, you need to try all the possible permutaion.
•  » » » » » 9 месяцев назад, # ^ | ← Rev. 3 →   0 Nevermind. I committed an error.
•  » » » » 9 месяцев назад, # ^ |   +3 Yes, LCA is enough, just check my submission to prove it.
•  » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 I think that vertex which is common to all paths between a,b,c is one of the lca(a,b), lca(b,c), lca(a,c).When you find this common vetex x you can print the max length of xa,xb,xc.28845144
•  » » 9 месяцев назад, # ^ |   0 I think we will use LCA and take care some cases
•  » » » 9 месяцев назад, # ^ |   0 Didn't take care about cases and my solution works fine
•  » » » » 9 месяцев назад, # ^ |   0 but did you use data structures?
•  » » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 I used just binary lifting to find lcaYou can check editoral to see my algo.
 » 9 месяцев назад, # | ← Rev. 2 →   +13 Problem C reminds me of my junior high PhO times... I have a few nested fractions but have no idea about the whole problem (though there's a feeling that it's about convexity). (Nvm, I was off the track.)
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   +23 I think it is solvable by cht trickhere is the accepted code using convex hull trick
 » 9 месяцев назад, # |   +9 Why ternary search doesn't work in task C?
•  » » 9 месяцев назад, # ^ |   0 F
•  » » 9 месяцев назад, # ^ |   +3 Did you consider the situation when the people who goes to right are all in the left side of your mid point? However if you move the bumb into the nearest person the time may get less.I realized that after the contest is finished :(
 » 9 месяцев назад, # |   0 Seriously waiting in anticipating for the hidden testcases to show their magic.Too many accepted for D problem.
 » 9 месяцев назад, # |   0 What is the fourth test for problem B?
 » 9 месяцев назад, # | ← Rev. 2 →   0 Here is why your B is wrong:"and the character "*" (if there is one) with any, including empty, string of bad lowercase English letters "A whole string of bad English letters, not just a character.
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 I've envisaged it UPD: Not :) Thanks
 » 9 месяцев назад, # |   0 Corner cases for D please?
 » 9 месяцев назад, # |   0 somebody tell me what's wrong with this code for problem B: http://ideone.com/zDWlW5
 » 9 месяцев назад, # |   0 what's wrong with this code: http://ideone.com/zDWlW5 for problem B
•  » » 9 месяцев назад, # ^ |   0 "*" can be replaced by 0 or >1 bad character(s) (not only 1)
 » 9 месяцев назад, # |   +1 Could anyone give me some tests on B.I WA on the test 12 so many times
•  » » 9 месяцев назад, # ^ |   0 In B testcase 12 in my opinion checks,when * comes are you skipping all the bad characters of a query or skipping till length remaining of strings are equal. ex ab *dddd 1 dddddddddd Check this testcase answer should be YES.
•  » » » 9 месяцев назад, # ^ |   0 I got it.I really appreciate it
 » 9 месяцев назад, # | ← Rev. 2 →   0 Is D main algorithm LCA?
•  » » 9 месяцев назад, # ^ |   +1 Yes
•  » » 9 месяцев назад, # ^ |   +2 yeah! LCA + some cases will be enough to solve it!
 » 9 месяцев назад, # |   0 I don't want to write string simulation with c++ any more……
 » 9 месяцев назад, # |   0 Maybe C is harder than D ?
 » 9 месяцев назад, # |   +20 Problem E is pretty elegant. Thanks to author.
•  » » 9 месяцев назад, # ^ |   0 Some hints please.
•  » » » 9 месяцев назад, # ^ |   +19 consider those strings as a vector space in field Z5.
•  » » » » 9 месяцев назад, # ^ |   -18 So what? This was obvious, but how to solve the problem?
•  » » » » » 9 месяцев назад, # ^ |   +25 get the basis for those given vectors , if the query vector can be spanned by the basis , answer is 5n - b where b is size of basis , otherwise answer is obviously 0.
•  » » » » » » 9 месяцев назад, # ^ | ← Rev. 3 →   +3 Can you explain your solution (to be precise how do you implement Gaussian Elimination and whats the running time)?I am familiar with author's variant of Gaussian Elimination which works in O(n × m × min(n, m + q)).
•  » » » » » » 9 месяцев назад, # ^ |   0 Why the answer is 5^(n-b)? 5^n — number of all possibilities. 5^b — number of all vectors in vector space. Why when one vector has k representations then every other must have k?
•  » » » » » » » 9 месяцев назад, # ^ |   +6 consider any vector which can be spanned by the basis , there is exactly one way to represent that vector as a linear combination of basis vectors. Let v1, v2, v3, ... , vn - b be the non-basis vectors , let x = c1v1 + c2v2 + ... + cn - bvn - b , and let the query vector be y , since both x, y can be spanned by the basis , y - x can be spanned by the basis as well and in exactly one way , so the answer is number of linear combinations of non-basis vectors which is 5n - b
•  » » » » » » » » 9 месяцев назад, # ^ |   0 thx
 » 9 месяцев назад, # |   +47 Codes by cheaters of today's round:
•  » » 9 месяцев назад, # ^ |   +2 How did you find it?
•  » » » 9 месяцев назад, # ^ |   +10 Both of them are my friends in my real account
•  » » 9 месяцев назад, # ^ |   +8 and actual code is here http://ideone.com/Frk5fc
•  » » 9 месяцев назад, # ^ |   +2 I think that they just used the same hld template.
 » 9 месяцев назад, # |   +9 Is it just me, or did anyone else find the wording of some of the problems confusing?
•  » » 9 месяцев назад, # ^ |   +1 It took me some time to completely understand question B.
•  » » 9 месяцев назад, # ^ |   0 It costs me 3 submissions to get AC B. I think that '*' could only replace by a single letter.
 » 9 месяцев назад, # |   +23 System tests massacre on problem B!
 » 9 месяцев назад, # | ← Rev. 2 →   +7 When participating for 2 hours and only solved A :) EDIT: to solve B i needed to change '<' into '=' :(
•  » » 9 месяцев назад, # ^ |   +1 :(
•  » » 9 месяцев назад, # ^ |   0 But.. but your ranking is 1897!
•  » » » 9 месяцев назад, # ^ |   0 Its pretty low, wanted to get into div1 :D
 » 9 месяцев назад, # |   0 How to solve C ??? It was a nice question.Thanks to the author
•  » » 9 месяцев назад, # ^ |   +1 It can be solved by CHT trick.Here is accepted code using cht trick
•  » » » 9 месяцев назад, # ^ |   0 Sorry for my ignorance but wath is CHT trick?
•  » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 Is It really the level of Div2 C problem ??? I still need to study a lot for solving Div2 Cs
•  » » » » 9 месяцев назад, # ^ |   +3 I saw some other solutions there was no cht in it. Maybe I took an overkill of the problem
•  » » » » » 9 месяцев назад, # ^ |   0 What is the CHT? btw...
•  » » » » » » 9 месяцев назад, # ^ |   +5 Convex Hull trick
 » 9 месяцев назад, # |   0 Some HLD with Fast IO Passed D, While my one got TLE with scanf printf :(What's the meaning of life :( :( :'(
•  » » 9 месяцев назад, # ^ |   0 So far, I've heard LCT, HLD, any my own sol(centroid decomposition) :VBut it was a simple lca problem lol!
•  » » 9 месяцев назад, # ^ |   0 Same friend, I got TLE too.
 » 9 месяцев назад, # | ← Rev. 3 →   +18 I clicked on problem C from today's contest and then the statement was downloaded as PDF file! But with letter A instead of C! So weird, isn't it!? Here is a screen shot of the file : loud_scream??
•  » » 9 месяцев назад, # ^ |   0 It is specificity of Codeforces. The text is the same.
 » 9 месяцев назад, # |   0 I really feel bad for getting wa in first just because of > instead of >=. I feel like crying, in order to submit it in less time i didn't noticed that. It is heartbreaking. :'(
•  » » 9 месяцев назад, # ^ |   0 dude, it's just matter of time until you get used to it. i have been through something worse than yours. close to win in local contest 2 times, when they picked top 5 and i got rank 6, and the second times when they pick top 3 and i got rank 4.
•  » » » 9 месяцев назад, # ^ |   0 Thanks for your reply. Though I feel really bad for this but now i will try to do as many questions of this contest as possible.
 » 9 месяцев назад, # |   0 What's wrong with my code? Problem B div.2 28847526
•  » » 9 месяцев назад, # ^ |   +6 Test : a b*bb 1 bbbbbb  Your Output : NO Expected Output : YES 
 » 9 месяцев назад, # |   +1 What is testcase 23 for problem B?
•  » » 9 месяцев назад, # ^ |   0 go and check out any accepted solution, you can see the test cases now.
•  » » » 9 месяцев назад, # ^ |   +1 Testcases are trimmed.
 » 9 месяцев назад, # |   +5 Made such a stupid mistake in Problem B. I had to just move str.find("*") c++ function outside the testCases loop :(
 » 9 месяцев назад, # |   +9 Hope it won't be unrated for some reason
 » 9 месяцев назад, # |   +35 how is it that so many times some unrated guy takes one of the first few places? Don't div 1 coders get tired of creating accounts? Or is it really that genius people are being born nowadays at such a high frequency :v (in which case perhaps we don't need to worry about getting conquered by robots)
 » 9 месяцев назад, # |   0 Such an elegant binary search problem,thank you for your contest:)
 » 9 месяцев назад, # |   +22 Me trying to put the bomb in C
 » 9 месяцев назад, # |   +9 When the ratings will be updated?
 » 9 месяцев назад, # |   0
 » 9 месяцев назад, # |   0 1.288543012.28854337Why submission-1 gets WA ?
•  » » 9 месяцев назад, # ^ |   +3 I think this stp.length()-(ptr.length()-pos) is unsigned int, so when it is < 0 it becames about 4 * 10^9.
 » 9 месяцев назад, # |   +3 I solved problem D in 1980ms,and now I can't solve it another time.
 » 9 месяцев назад, # |   -26 Hope Unrated :D Site was down for 20 minutes >:(
 » 9 месяцев назад, # | ← Rev. 2 →   0 I've got WA on test 57 in problem B:( Can someone help with my solution, please? Can't get where I have a mistake. TIA:) http://ideone.com/QluM6T
•  » » 9 месяцев назад, # ^ |   +1 Setting testy=0 within the loop gives you a couple more testcases.Link
•  » » » 9 месяцев назад, # ^ |   0 Oh, thank you very much!:) Now I have a full solution.
 » 9 месяцев назад, # |   +3 D should be rejudged ... Almost all HLD solutions will fail -_- Even submitting some AC solutions is giving TLE -_- Some solutions passed in 1965~1980ms -_-
 » 9 месяцев назад, # | ← Rev. 2 →   +3 What is the difference between these 2 submissions for D? -28842403 — AC in 1965ms (In Contest)28854711 — TLE on test 70 (In Practice) -_-
•  » » 9 месяцев назад, # ^ |   +1 It is called Law of conservation of rp in China.
 » 9 месяцев назад, # | ← Rev. 2 →   +3 Why aren't ratings updated yet?
•  » » 9 месяцев назад, # ^ |   0 I think, they're banning cheaters now. At the end of the contest it was 5108 participants, now it's 5087.
 » 9 месяцев назад, # |   +2 I know its too much to expect & I should be patient. But tired of refreshing,please update ratings fast.
•  » » 9 месяцев назад, # ^ |   +11 Use predictor, bro
 » 9 месяцев назад, # |   0 where's the new rating's ??
 » 9 месяцев назад, # | ← Rev. 3 →   0 Doesn't LCA(u, v) = u implies that u is an ancestor of v? I am not able to figure out any mistake in my submission. Can anyone tell what could be the mistake? Thanks.
•  » » 9 месяцев назад, # ^ |   0 it's implies
 » 9 месяцев назад, # |   +5 28845399last permutation should be (c,b,a) am I right ?
•  » » 9 месяцев назад, # ^ |   +5 I think it is correct because (c, b, a) = (b, c, a)
 » 9 месяцев назад, # | ← Rev. 2 →   0 Can somebody tell me why this TLEd for problem B. Code
•  » » 9 месяцев назад, # ^ |   0 i got TLE to and then i used break ... i think you should try it
•  » » » 9 месяцев назад, # ^ |   0 But why so, this should do fine for the constraints.
•  » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   0 i think so but using break helped me here TLE solu : 28854042 to Ac solu : 28854162and that to reduces to 62ms :p
•  » » » » » 9 месяцев назад, # ^ |   0 Thats ok, I want to know why this TLEd.
•  » » 9 месяцев назад, # ^ |   +4 even though you check for the bounds, you still search the whole string. Think of the case when the string is 10^5 characters long and starts with a '*'. And you have 10^5 queries of single character. For each query, you will run through the whole 10^5 string, because even though you check the sizes, you never break when you should. Thus, 10^5 x 10^5, TLE.
•  » » 9 месяцев назад, # ^ |   0 The first loop FOR(i,1,n) is O(n) and the second loop in else statement FOR(i,0,ind-1) is of order O(|s|) when star is at the end. Therefore net complexity = O(nq). Hence TLEd
 » 9 месяцев назад, # |   +18 Wow, the one who took second place in Div2 writes such beautiful codes!
 » 9 месяцев назад, # |   -6 ....
 » 9 месяцев назад, # |   +6 Problem B. One can write short solution with regular expressions in languages which support them. Only if language's regexes are fast enough to cope with time limits. I've found a solution in Ruby — Key_v2:28852992 (gsub -> global substitution), mine is similar but 3x slower (in Perl) — 28885266 (s///g -> same).
•  » » 9 месяцев назад, # ^ |   +1 libstdc++ regexp crashes on large examples, looks like it's the weakest implementation. Visual C++ regexp don't crash but seemingly fail at time limit, can't really test because VC++ is too old on CF. Maybe it's also worth it to test libc++, they don't crash but I doubt they will pass TL too.So basically C++ regexps fall short for this task.