MrNull's blog

By MrNull, history, 9 years ago, In English

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!

Famile Door

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: результаты

Congrats to the div2 Winners:

1. rakhashov.maksat

2. DarthMaul

3. TakeTheAegisIDontNeedIt

4. ykaya

5. abcdef6199

Also congrats to the div1 Winners:

1. Um_nik

2. anta

3. Nerevar

4. kmjp

5. vintage_Vlad_Makeev

Best of luck to everyone!

  • Vote: I like it
  • +257
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

A contest by my friends !

Will be interesting ...

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

cool!!!

»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

happy birthday Mr. FamileDoor in advance...

»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

famile door :D :))))

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

»
9 years ago, # |
  Vote: I like it +35 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +88 Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
Rev. 5   Vote: I like it -18 Vote: I do not like it

//

»
9 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Cool !
An Iranian contest after months.
Come on PrinceOfPersia !

»
9 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
9 years ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    It's actually dar manand, by which he means: like a door.

    UPD: Although dar manand literally means they will not succeed.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      oh yeah,you are right ;) but i should say :" sir dagh.. :P"

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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 :(

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like 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!

»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Thanks to authors! Famile Door :)^D

»
9 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 :)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Iranian Contest style and statements are always funny.

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I Love he 's son :))

»
9 years ago, # |
  Vote: I like it -49 Vote: I do not like it

Oh

Another awful Iranian contest

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 !

»
9 years ago, # |
  Vote: I like it +61 Vote: I do not like it

This guy looks creepy af :D

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I forgot to register LOL

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

I liked problem C.

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

A<=B<D<C<E

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem D LIS?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I used segment tree.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it -7 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it +18 Vote: I do not like it

              I thought we are aeroplane makers.

            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it +13 Vote: I do not like it

              What you say is a really bad way of learning.

              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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 up but I say bro, BIT is really cool to use because the code is short, even if you find it confusing, you can still use it

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes. LIS but on the volumes. Solution 1. Use Binary Search Solution 2. Use Segment Tree.

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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 ?)

»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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 :)

»
9 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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:

Solution verdict:
OK

Checker:
ok found '3141592653590.0000000', expected '3141592653590.0000000', error '0.0000000'

Input:
1
10000 10000

Output:
3141592653590.0000000

Answer:
3141592653590.000061512

Time:
0

Memory:
901120

And the hack was Unsuccessful. . .

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          Ok, I understood. Thanks :)

          Lesson learned — Never hack about precision errors.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Codeforces servers were pretty good today :)

»
9 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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

Basically just calculate r2h for each cylinder, use this, and multiply the answer by Pi.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I googled that and I didn't find anything...

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    your first submission gets skipped

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Really nice contest! :)

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

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    maybe someone need process the hack data.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ().....}

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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 :)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

16242198 = 16242896 cheaters?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I've seen problem D before : problem.

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

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I wonder what is this test.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "strictly greater"

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oooooooh. Man I never learn :(

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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 :(

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How do you check for "strictly greater"?

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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

»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

When can I see the changed rating?

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

ret += 1.0 * countLengthSum[b] / countNodes[b];
if(lca != a)
    ret += 1.0 * countLengthSum[b] / countNodes[b];  // <-- It should be a instead of b

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:

  • lca(a,b) will be a or b: so we will not run the code with bug
  • both a, b are leaves: so countLengthSum[b] = countLengthSum[a] = 0.

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

So is this intended?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thank for contest problems is good :D

»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Edit

Why does both submission give AC?

Correct

Wrong

Test case 100

Every element of this matrix is C.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Iranian contests are unlucky for me :(

But now no claims to the authors

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problemset! (specially C)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider this test case:

    4
    M 1 4
    M 1 4
    F 1 2
    F 3 4
    

    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.