Hello Codeforces!

On July 24, в 17:35 MSK rated Codeforces Round #425 (Div. 2) will be held. As always, participants from the first division can take part out of competition.

This is my first round. Many thanks to Nikolay Kalinin (KAN) and Alexey Ilyukhov (Livace) for help in preparations of the round, Ildar Gainullin (300iq), Daniil Nikolenko (qoo2p5) and AmirReza PoorAkhavan (Arpa) for testing problems and also to Mike Mirzayanov (MikeMirzayanov) for Codeforces and Polygon platforms.

You will be given 5 problems and 2 hours to solve them. Scoring will be announced before the round.

I hope you'll enjoy my round. I wish everyone good luck and high rating!

**UPD1:** The scoring for this round is: **500 — 1000 — 1750 — 2000 — 2500.**

**UPD2:** Congratulations to the winners! Editorial here.

Div.2 :

Div.1 :

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 ?

5

is it rated?

When asked "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

is it rated :p

Fuck off man -_- -_-

The guy was obviously kidding. Just downvote him if you don't like his post. No reason to swear.

Seriously? I'm getting downvoted for trying to keep the level of discussion decent? Nice! :)

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

ratedCodeforces Round #425 (Div. 2) will be held. :DQwQ...Thx.

:(

deleted

+1. Good luck!

thanks

KAN 'THE GOD'of testing problems _/_

7000+ registrations wow!!

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 .

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..!

if that's true than life's weird .

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(n^{2}),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,

stringof bad lowercase Englishletters"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!

I don't want to write string simulation with c++ any more……

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 5

^{n - b}wherebis 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

v_{1},v_{2},v_{3}, ... ,v_{n - b}be the non-basis vectors , letx=c_{1}v_{1}+c_{2}v_{2}+ ... +c_{n - b}v_{n - b}, and let the query vector bey, since bothx,ycan be spanned by the basis ,y-xcan 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 5^{n - b}thx

Codes by cheaters of today's round:

1) 28850800 by code_hard123

2) 28846680 by parseltongue4052

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.228847526What 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.

Hope Unrated :D Site was down for 20 minutes >:(

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

where's the new rating's ??

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.