Hello, Codeforces!

I have the pleasure to invite you to the round #343 which is going to take place on Saturday! This round is consisted of 5 problems and you have 2 hours (as usual) to solve them.

The problemsetters are Mohammad Amin Vahedinia (Me) (MrNull), Daneshvar Amrollahi (dkjsfkhg) and Alireza Tofighi (ATofighi). We would also like to thank Alireza Tofighi (ATofighi) and Ali Asadi (aliasadiiii) for testing this round and Ali Bahjati (LiTi) for helping us preparing this round.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements into Russian, and, of course, MikeMirzayanov for unique Codeforces and Polygon platforms.

This contest's Hero is Famile Door and his friends who are preparing his birthday party!

**UPDATE 1: Scoring Distribution is 500 — 1000 — 1750 — 2000 — 2500**

**UPDATE 2: Editorial is ready HERE**

**UPDATE 3: System Testing is finished** you can see the standings here: standings

Congrats to the div2 Winners:

**2. DarthMaul**

**4. ykaya**

**5. abcdef6199**

Also congrats to the div1 Winners:

**1. Um_nik**

**2. anta**

**3. Nerevar**

**4. kmjp**

Best of luck to everyone!

A contest by my friends !

Will be interesting ...

GL & HFcool!!!

happy birthday Mr. FamileDoor in advance...

famile door :D :))))

contest in the third consecutive day, it is mid-night at my time zone, however, I will try my best like all of you here and get advanced to div.1, wish all having good result!

let's hope something realistic and not for exemple N invited (N<=1000000000000) or K candles on the bithday cake where (k<=1e50) !!

Indeed, nothing is realistic in Famile Door’s world :D

I just hope Famile Door can explain his birthday party wishes in a short and direct way :D

For who doesn't know about Famile door, I have to say Famile door is a character in Kolah qermezi TV series (iranian TV for sure).

https://en.wikipedia.org/wiki/Famil-e_Door

The last codeforces before the end of my holiday. better !!

Its recently that I have become purple, so I still like giving DIV 2 :D :P

//

LOL

Cool !

An Iranian contest after months.

Come on PrinceOfPersia !

Can anyone explain how the ratings go up and down for each coder?

http://codeforces.com/blog/entry/102

OMG! The hero of the contest is my favorite character! And also the authors are Iranians :) best contest ever!

The flag of Iran and Famile dooor(I Love him) is up :) Famile dooor always say:"agar darbande dar manand,dar manand...":D ty all guys who prepare this contest <3

It's actually

dar manand, by which he means:like a door.UPD: Although

dar manandliterally meansthey will not succeed.oh yeah,you are right ;) but i should say :" sir dagh.. :P"

:D

How is this relevant to the discussion at hand? Sorry I don't read/speak Persian, so I can't really understand what's written over here :(

The last phrase of the poem is Famil Door's signature. I can't remember a single episode without him saying it.

You are not alone.

Most of the Iranians also don't understand it (like me).

It is a poet of Hafez (a great poetry).

Only the last line is important which is Famil Door's signature.

UPD: And means if you have a problem and God don't help you, you won't be able to solve it...

UPD 2: But I'm not sure about it!

Thanks to authors! Famile Door :)^D

I have to mention that Famil is a door-keeper and he is from a city called Door. I am sure we will see problems about opening and closing some doors :D

I remember preparing a practice contest for my friends, in which I used Famil (and also his wife, Dooreh) for the contest character too! I was about to prepare a CF round, also about Famil. I wish I knew the authors of this round before they announce the contest! Maybe I can help them next time preparing some of easy problems :)

I used to think he is a relative of "aghaye mojri"(a far one :|)

Iranian Contest style and statements are always funny.

iranians are alyways happy and kindly

so lately :( in my time.

I Love he 's son :))

Oh

Another awful Iranian contest

1- you don't have to practice on this contest.

2- when codeforces is going to run this contest , it means codeforces has considered that this contest has the least quality to be the contest of codeforces !

This guy looks creepy af :D

Looks can be deceiving my friend ! He's one of the loveliest puppet characters I can think of.

An attractive hero. So, let's hope an attractive contest :)

I forgot to register LOL

wierd contest !!!

Very good contest!!! Thanks for the round...

I liked problem C.

A<=B<D<C<E

Problem D LIS?

I used segment tree.

D can be solved using seg tree + coordinate compression . Didn't get the time to implement it :(

No need for coordinate compression. D is easy this time.

For such problems, using fenwick tree is better since it takes much less time to implement. It is also easier to learn than segment tree, though not as universally applicable.

I find BIT harder to understand, things are more intuitive when working with segment tree :)

Do you need to know how an aeroplane is made just to take a flight? Sometimes we must use the concept of blackboxing in life.

I thought we are aeroplane makers.

What you say is a

reallybad way of learning.LOL. So, you won't fly in an aeroplane unless you know how to make one in your backyard? Does Google maps show you every district, every house on every country on earth, or does does it blackbox most of it untill and unless you zoom in?

I don't say

bro, learning algorithms is bs, just mug them upbut I saybro, BIT is really cool to use because the code is short, even if you find it confusing, you can still use itYes. LIS but on the volumes. Solution 1. Use Binary Search Solution 2. Use Segment Tree.

what is the LIS?

Largest Increasing Subsequence

Longest increasing subsequence

And how this helped to solve problem? The longet do not mean the subsequence with the biggest sum...

No, but try to maximize the volume with the concept of LIS.

Longest Increasing Subsequence.

Is it possible to get the LIS in nlogk , the best LIS? What modification do I need to do to get the LIS with max volume?

Wasted alot of time in problem C trying to find out Catalan Numbers and bunch of nCr's. It ought to be DP. (Why the hell is DP so hard ?)

I feel very happy because yesterday I was learned how to find LIS on good time with indexing tree and now I was solved problem D for my first time :)

I tried hacking on D, with the fact that if PI has < than 17 digits after the decimal point the error will change. Example:

1 10000 10000

real answer = 3141592653589.793238401 (with PI's digits equal to 50)

advitiyabrijesh 's output = 3141592653590.0000000 (with PI's digits = 12)

System verdict:

And the hack was Unsuccessful. . .

"Your answer will be considered correct if its absolute or relative error does not exceed 1e-6."

here the relative error is less than 1e-6.

But the authors solution gives wrong answer. The error is actually 0.206761599 which is larger than 1e-6.

Absolute yes, but relative error is less than 1e-12

Ok, I understood. Thanks :)

Lesson learned — Never hack about precision errors.

The error 10^-6 is relative, not absolute. Therefore, in this case is aproximately 3141593.0 difference allowed.

I was too slow :D

Codeforces servers were pretty good today :)

Problem D : https://e2718281828459045.wordpress.com/2013/09/06/maximum-sum-increasing-subsequence/

Basically just calculate

r^{2}hfor each cylinder, use this, and multiply the answer by Pi.I googled that and I didn't find anything...

Any ideas why O(n log n) give TLE on pretest 6 in problem D ? My implementation : http://codeforces.com/contest/629/submission/16246075

It didn't feel like a Div.2 contest.

lol what did it feel like?

I problem B , due to my bad internet connection , my code was submitted twice , so I got -50 coz of resubmission How did the judge accept the 2 submissions however they're similar (i.e. why there was no warning for the second submission )? submissions links : 16236771 16236745

your first submission gets skipped

Sure but when I submit the same code twice ,the system should send me a warning (as usual) , this didn't happen in the contest :)

same thing happened with me! mine was worse because i got three consecutive wrong answers! :(

Really nice contest! :)

I liked problem C very much, although I couldn't get all the pretests pass on time... next time, maybe!

there might be a hack on c which s is like ")))))(((((" but i am not sure and i didn't solve the problem anyway.

I always wonder why the System Test doesn't start immediately after the contests ends.

maybe someone need process the hack data.

I have no clue why my code to D does not work on pretest 6, can someone drop a hint? :D http://www.codeforces.com/contest/629/submission/16246045

Problem C has nice hacking testcase (exceeded of memory) :)

I used fixed memory. should I worry about MLE? :)

You got RTE, I saw my mistake 20 seconds before end and I couldn't change it :(

Just needed to make a simple check

`diff>=MX`

to discard the access of the memory outside its limits. I fell from top 200 to top 500. a huge gap. :(AC : 16247743

Why? 2.4*10^8 bytes in bss are allowed. Could you please explain what you mean by memory limit exceed? If you mean negative indexing, then a simple shift by N is enough

No, he defined matrix d[2000][2000] and it should be at least d[2000][10^5+2000].

No, it shouldn't. I got it AC with d[2000][2000]. just used a simple shift trick.

Why on earth do problem setters make C harder than D!!!!

I think it's about opinions because I was learned LIS yesterday and it looks hardly to me but C is dp. There is easy problem that asks how many sequences of given length are correct and it is the same dp but we need extra flag so it's no so hardly :)

I spent 1 hr 30 minutes on C and din't find the recurrence relation. What was the recurrence relation for p? I used

dp[len][reqirement]=dp[len-1][requirement-1]{for an open parenthesis (.....}+ dp[len-2][requirement]{for ().....}

Look, my English is not very good but I will be trying to explain it in best way. The usual dp is dp[position][sum] and we try to move to next position with sum+1 and sum-1. Here we do the same dp[position][sum] but we need to know if we are being on left or right of S (I want to say if we are in P or Q) so flag F will show 0 if we are on left and 1 if we are on right. Each time we have some state(Pos,Sum,F) we try move to state(Pos+1,Sum+1,F) and state(Pos+1,Sum-1,F). And additional, if F is false, means we are on the left we try to move to the right but on same position with state(Pos,Sum+SumOfS,true). Only if we do it we need to know that Sum+MinSumOfS is not negative. Try to check my code, sorry for English :)

Could you give me a pastebin or ideone link to your code?

Yes, I give you — http://pastebin.com/aBHAG8k9

Thanks! And your English isn't as bad as you think(although I should first check whether your explanation matches your code :) )

No problem, I am hoping you understand it!

great explaination .... now it looks very easy for me :) thank you

The difficulty of a problem varies from person to another person. Because we don't train on some topic with the same intensity. So it differs ! e.g. for me C was easier than D.

So you demand the impossible from the problem setter when you say sort them by the difficulty equally for everyone.

Direct implementation of LIS is not even at D's level. Its a B or C.

16242198 = 16242896 cheaters?

Look my blog entry, I one time was reported two cheaters but nobody care unfortunately.

The solution verdict for the unrated user of the two says "Skipped". What does that mean? Did the CF servers somehow discover that the two were identical solutions? :D

I've seen problem D before : problem.

The same solution will work for it just add a few lines of code .

Why this behaving in odd manner on [codeforces] ?(http://codeforces.com/contest/629/submission/16247940)

so many WAs on test case 37 for problem D! i wish some1 had hacked my solution

I wonder what is this test.

"strictly greater"

Oooooooh. Man I never learn :(

I think it is round off error. Instead of using double for calculation, one should use long ie r^2*h. Then just before printing answer multiple by acos(-1).

That way precision is maintained. I can't believe I made the mistake. Was supposed to be expert today :(

This one might be too.

But I know some who used long long everywhere, but failed because of missing the word "strictly greater".

How do you check for "strictly greater"?

See my solution. I compress all areas (so they are less than N) and just take maximum in prefix (1...new_value[i] — 1). Here, -1 is for counting only strictly less numbers.

You can index every r^2 * h from the given test in increasing order (sorted first), then check the elements with lower index, this way you will never use a cake with the same volume

My accepted solution for problem C (practice) should give RE:

100000 98000 (98000 open brackets)

I corrected this problem in contest (incorrectly) and I got WA :'( while the original code received Accepted

Kill me please

When can I see the changed rating?

I hope soon!!

Can you congratulate top 10, not top 5, please :(

Top 10 is too much. Top 9? XD

So it turns out this code could pass all pretest in last task:

Why? It is because in all tests, if we choose 1 as the root then in each query(a,b) one of them is true:

If we root the tree at 2 or 3 or a random one then pretest will catch this bug.

So is this intended?

Worst feeling in the world: being 2 rating points lower than purple.

1 point here :'(

I know that feel bro :'(

can any body explain problem C elaborately. I was not able to understand tutorials

Can someone help me find bug in my solution to C? I cant find it.

http://codeforces.com/contest/629/submission/16248986

i was comparing it to the um_nik's code and i cant see any difference

http://codeforces.com/contest/629/submission/16235943

Could someone tell me what's wrong with my code? Please! I can't understand the bugs with only one for loop. :( 16249539

thank for contest problems is good :D

Edit

Why does both submission give AC?

Correct

Wrong

Test case 100

Every element of this matrix is C.

The other one gives verdict as Skipped not AC

Edited

Iranian contests are unlucky for me :(

But now no claims to the authors

can any body explain problem C elaborately. I was not able to understand tutorials

we count dp[length][balance] = number_of_correct_bracket_sequences_with_balance=balance like dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]. dp[0][0] = 1

then consider length_of_prefix = i (i=0..n-m), it means length_of_suffix = n-m-i. then iterate over balance of prefix (it must be not lower than (minimum prefix balance of string) * -1), so ans += dp[i][current_balance] * dp[n-m-i][current_balance + balance_of_string] (need to process RE).

Can someone explain the solution B? looks to be greedy, sort by start or end, and doing a linear traversal on both male and female intervals does not work? looks to be a standard problem, can someone help please?

First Notice that number of females and males have to be same.So answer is always a' multiple of two. I did it as follow- Make an array of 366 days for male and female separately. take start and end . Increment the array b/w start and end for each gender separately. Then traverse both the array and take max of min of both arrays and multiply by two. Since days are only 366 This method works easily

629C - Famil Door and Brackets

:16243295 16244309 cheaters629D - Babaei and Birthday Cake

:16246407 16254007They will never give up :)

Good problemset! (specially C)

Hello codeforces, I am having struggle with problem B and i want to solve it alone before looking at editorial but i am really having difficulties with it.Can someone help me out or atleast give me a hint what is wrong with my code?Cheers CODE

Consider this test case:

Your code will answer 4, while the correct answer is 2. You don't consider the fact that the friends who have available time in common with a specific person, might not be available together at all. Try to think of it from a different angle.