Всем привет!
В понедельник 24 июля в 17:35 MSK состоится рейтинговый Codeforces Round #425 для участников из второго дивизиона. Как всегда, участники из первого дивизиона могут принять участие вне конкурса.
Это мой первый раунд. Хотелось бы сказать большое спасибо Николаю Калинину (KAN) и Алексею Илюхову (Livace) за помощь в подготовке задач, Ильдару Гайнуллину (300iq), Даниилу Николенко (qoo2p5) и AmirReza PoorAkhavan (Arpa) за прорешивание задач, а также Михаилу Мирзаянову (MikeMirzayanov) за системы Codeforces и Polygon.
Участникам будет предложено пять задач и 2 часа на их решение. Разбалловка будет объявлена ближе к началу раунда.
Всем удачи и высокого рейтинга!
UPD1: Разбалловка для этого раунда: 500 — 1000 — 1750 — 2000 — 2500.
UPD2: Поздравляем победителей! Разбор тут.
Div.2 :
Div.1 :
Автокомментарий: текст был обновлен пользователем Loud_Scream (предыдущая версия, новая версия, сравнить).
Is it just me wondering about that "a." at the end. :P EDIT: Its removed, it must have been a typo. :)
How to solve E?
I didn't test below algorithm but I think it works :
fist solve then code :D
Solved it 2 minutes after the contest.
It's a well known problem. Google it.
Well, I coded the n^4 dp, and then found the generating function in OEIS
Haa hmm ok
5 problems or 6 ?
is it rated?
I am curious about the process of choosing the author of the contest. does anyone have any information?
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 contest
Check this
Who is the hero of round?
I hope no one, so we can get short statements.
By no one, do you mean the faceless god? (Get it?) :P
I think everyone GoT it :P
Khaleesi approves
Its my first contest here, any suggestions!!
don't get hacked
What exactly do you mean?
@shubhammanhas579
http://codeforces.com/blog/entry/6249
https://www.quora.com/What-is-meant-by-hacks-in-Codeforces-What-do-they-do
Thanks, got it...
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 :)
Thank you so much for such an honest advice #potaters
Is it rated?
On July 24, в 17:35 MSK rated Codeforces Round #425 (Div. 2) will be held. :D
QwQ...Thx.
deleted
+1. Good luck!
thanks
KAN 'THE GOD'of testing problems _/_
7000+ registrations wow!!
unable to register
unable to register
Same here, I pressed the "register" button, "entered" the contest, and it won't let me submit anything?
Hope to become green.
You have only 2000 pts for D?
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.
But my D sol is monstrous :(
I didn't noticed that the round has already started. :P"
For me D felt easier than B(I am not sure about correctness though).
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!!!
Don't ask for idea or clue about the contest problems, during running contest. :)
tnx.
anyone else facing a long queue?
My first Div 1 contest .
My first Div. 1 contest .
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..!
damn only noticed that now
Actually this type of statement appears in many problems in the previous rounds too. Better be careful next time.
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...
That is why you can ask questions in the contest. I asked it and got the answer straightaway.
Too much lag make it unrated :D
You won't believe how I tried to solve D :v
LGTwins — Legendary Grandmaster Twins?? :DD
Never try to hack out of bounds for cpp solutions. Lesson learned :/
Oh, that funny task about a bomb...
EDIT: Never mind
Intended solution for D isn't bruteforces O(n2),right?
O(n^2) is too much. 10^10 operations would definitely take more than 2 seconds.
Yeah,I know-I'm just surprised with 500+ acc on D.
I using Segment tree + LCA to solve this problem.
I did LCA with sparse table except it timed out because I managed to build the sparse table N^3 times...
Sparse table could not update quickly :). Btw, I also using permutation to try all the possible ways.
No need to update it, you can calcucate all the queries by picking an arbitrary root for the tree.
Hmm, it really interesting :D. Btw, you also use HLD to find LCA ?
Isn't using DFS + LCA enough ?
I think it would be TLE, because it could be maximum n nodes for each shortest path.
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)
No I mean in pre-processing phase, I used dfs to calculate the distance f[u] from u to root (which is 1).
4k1502 I don't think so, because sometimes you don't need to travel to root to find the shortest path.
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?
I also got WA on pretest 6. I think I failed in solving some corner case.
Oh, you need to try all the possible permutaion.
Nevermind. I committed an error.
Yes, LCA is enough, just check my submission to prove it.
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
I think we will use LCA and take care some cases
Didn't take care about cases and my solution works fine
but did you use data structures?
I used just binary lifting to find lca
You can check editoral to see my algo.
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.)
I think it is solvable by cht trick
here is the accepted code using convex hull trick
Why ternary search doesn't work in task C?
F
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 :(
Seriously waiting in anticipating for the hidden testcases to show their magic.Too many accepted for D problem.
What is the fourth test for problem B?
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.
I've envisaged it UPD: Not :) Thanks
Corner cases for D please?
what's wrong with this code: http://ideone.com/zDWlW5 for problem B
"*" can be replaced by 0 or >1 bad character(s) (not only 1)
Could anyone give me some tests on B.I WA on the test 12 so many times
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.
I got it.I really appreciate it
Is D main algorithm LCA?
Yes
yeah! LCA + some cases will be enough to solve it!
Maybe C is harder than D ?
Problem E is pretty elegant.
Thanks to author.
Some hints please.
consider those strings as a vector space in field Z5.
So what? This was obvious, but how to solve the problem?
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.
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)).
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?
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
thx
Codes by cheaters of today's round:
1) 28850800 by code_hard123
2) 28846680 by destinydrifter
How did you find it?
Both of them are my friends in my real account
and actual code is here http://ideone.com/Frk5fc
I think that they just used the same hld template.
Is it just me, or did anyone else find the wording of some of the problems confusing?
It took me some time to completely understand question B.
It costs me 3 submissions to get AC B. I think that '*' could only replace by a single letter.
System tests massacre on problem B!
When participating for 2 hours and only solved A :) EDIT: to solve B i needed to change '<' into '=' :(
:(
But.. but your ranking is 1897!
Its pretty low, wanted to get into div1 :D
How to solve C ??? It was a nice question.Thanks to the author
It can be solved by CHT trick.
Here is accepted code using cht trick
Sorry for my ignorance but wath is CHT trick?
Is It really the level of Div2 C problem ??? I still need to study a lot for solving Div2 Cs
I saw some other solutions there was no cht in it. Maybe I took an overkill of the problem
What is the CHT? btw...
Convex Hull trick
Some HLD with Fast IO Passed D, While my one got TLE with scanf printf :(
What's the meaning of life :( :( :'(
So far, I've heard LCT, HLD, any my own sol(centroid decomposition) :V
But it was a simple lca problem lol!
Same friend, I got TLE too.
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??
It is specificity of Codeforces. The text is the same.
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. :'(
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.
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.
What's wrong with my code? Problem B div.2 28847526
What is testcase 23 for problem B?
go and check out any accepted solution, you can see the test cases now.
Testcases are trimmed.
Made such a stupid mistake in Problem B.
I had to just move str.find("*") c++ function outside the testCases loop :(
Hope it won't be unrated for some reason
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)
Such an elegant binary search problem,thank you for your contest:)
Me trying to put the bomb in C
When the ratings will be updated?
1.28854301
2.28854337
Why submission-1 gets WA ?
I think this stp.length()-(ptr.length()-pos) is unsigned int, so when it is < 0 it becames about 4 * 10^9.
I solved problem D in 1980ms,and now I can't solve it another time.
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
Setting testy=0 within the loop gives you a couple more testcases.
Link
Oh, thank you very much!:) Now I have a full solution.
D should be rejudged ... Almost all HLD solutions will fail -_- Even submitting some AC solutions is giving TLE -_- Some solutions passed in 1965~1980ms -_-
What is the difference between these 2 submissions for D? -
28842403 — AC in 1965ms (In Contest)
28854711 — TLE on test 70 (In Practice) -_-
It is called Law of conservation of rp in China.
Why aren't ratings updated yet?
I think, they're banning cheaters now. At the end of the contest it was 5108 participants, now it's 5087.
I know its too much to expect & I should be patient. But tired of refreshing,please update ratings fast.
Use predictor, bro
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.
it's implies
28845399
last permutation should be (c,b,a) am I right ?
I think it is correct because (c, b, a) = (b, c, a)
Can somebody tell me why this TLEd for problem B. Code
i got TLE to and then i used break ... i think you should try it
But why so, this should do fine for the constraints.
i think so but using break helped me here TLE solu : 28854042 to Ac solu : 28854162
and that to reduces to 62ms :p
Thats ok, I want to know why this TLEd.
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.
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
Wow, the one who took second place in Div2 writes such beautiful codes!
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).
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.