Announcing MemSQL Start[c]UP 2.0
By AlexSkidanov, 10 years ago, translation, In English

MemSQL is excited to announce Start[c]UP 2.0 – the second annual programming competition hosted by Codeforces with an onsite at MemSQL HQ in San Francisco, California.

Start[c]UP 2.0 consists of two rounds. Round 1 is online and takes place on July 27th at 10:00 AM PST. Round 1 follows regular Codeforces rules and consists of 5 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round. There are no eligibility restrictions to participate in the round. The round will be 2.5 hours long, and will be rated.

Round 2 takes place on August 10th at 10:00 AM PST, consists of 6 problems, and uses regular Codeforces rules. The complexity of the problems is higher than a regular Codeforces round, the round will be 3 hours long, and will be rated. Only people who finished in the top 500 in Round 1 can participate. The top 100 in round 2 will receive a Start[c]UP 2.0 T-shirt.

For Silicon Valley residents, MemSQL will be hosting up to 25 people on-site during the second round. The winner of the on-site round will be awarded a special prize.

UPDATE: first round will feature 6 problems, not five as it was announced earlier.

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

Comments Comments (269)
| Write comment?
»
10 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Note that July 26th is also the date of TCO round 3A — it'd be good to avoid collisions as early as possible.

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

    Yes, thank you for bringing it up. Round one will actually be on Sunday, July 27th. Original post had a wrong date.

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

    Thank you for reminding me, that today will be TCO. If it weren't for you, I would probably forget :P (not that TopCoder should do that...)

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

Round 1 follows regular Codeforces rules and consists of 5 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round.

Division 1 or 2?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -37 Vote: I do not like it

Deleted.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sorry if this seems like a stupid question, but what does the [c] in Start[c]UP signify?

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

    It would not be a "cUP" had it not been the "[c]".

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    This is rounded speed of light.

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

    if we remove "[c]", we have StartUP. I don't know if it is right or wrong.

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

      this is actually one of the things i wanted to know when i asked the question. :)

      → Reply
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

"**The top 100 in round 2 will receive a Start[c]UP 2.0 T-shirt.**" I like it :)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No unofficial participation in round 2 for those who didn't finish in top 500 in round 1?

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

    As far as I know Codeforces allows one to participate unofficially in any round (same as division one contestant can participate in division two rounds). We will not intentionally disable this functionality.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Why do you set such strange top-500 restriction for online version of second round? For example I can't participate in first round, so you force me skip both rounds. It is very easy to reach top-500, so it is only about could you participate in the round or not.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        It is very easy to reach top-500

        i think this is disrespectful to the people who won't make it to the top 500

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

          Sorry if I offended anyone. And I am sure they want officially participate in the second round too.

          P.S. I changed my flight, so I can participate, but still don't understand logic of organizers. It is not gcj with huge amount of participants, and it doesn't affect onsite at all.

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

          I'm sorry for whoever that stands in 501st place :/

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

            so sad for veecci and poopi. they missed out by just 4 and 6 points respectively. :(

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
              ← Rev. 3   Vote: I like it +32 Vote: I do not like it

              Oh, Thanks. I was very bad today, but really I prefer to be at 600th place or more instead of 502th :) It isn't nice but I'm hopeful that organizers find at least two cheater in places 1 to 501 :)

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

        I hope I will be able to say "It is very easy to reach top-500" in the future.

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

        I agree with the first statement of course. What's the point of the restriction of top 500? If the system can bear the load of 1st round then obviously it could bear the pressure if all are advanced so there is no point of top 500 thing from the point of system.

        But according to the 3rd sentence, if It is very easy to reach top-500, so it is only about could you participate in the round or not., then all the (1200 and counting) participants/registrants will reach top 500? Oh, but pigeonhole principle must disagree.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it -14 Vote: I do not like it

          then all the participants will reach top 500? Oh, but pigeonhole principle must disagree.

          what if 1000 participants all get same score, and all take the 500-th place? :D

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

          maybe two pig on one hole :/

          → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      I guess main point of question was about rated participation (not like unofficial participation for div1 contestants in div2 rounds). For example, Croc Champ 2013 — Round 2 was rated event both for guys who qualified from round 1 and for those who did not; moreover, there was also Croc Champ 2013 — Round 2 (Div. 2 Edition) — rated event for div2 users.

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

      What happens to ratings when one participates unofficially though?

      I seem to recall that when VK-cup was on CF, unofficial participants still factored into the ratings pool. Will that be the case here?

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

        Last year it was a regular CF round for all participants in terms of rating.

        → Reply
»
10 years ago, # |
  Vote: I like it -37 Vote: I do not like it

where can i get the competition

→ Reply
»
10 years ago, # |
  Vote: I like it -20 Vote: I do not like it

July 27th??!! That's the first day of NOI~~!!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated??

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

    Yes, both rounds will be rated. I updated the post with this information.

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It is said that both round will follow regular Codeforces rules, while first will last 2,5h and second 3h, I think you should mention this in an announcement.

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

    Updated the post, thanks for bringing this up.

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

      Note that with last two changes language versions became out of sync.

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

        And with the very last change they are in sync again :o)

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When is the final round? I wish if you can announce this as early as possible. I live near to San Francisco, and I was invited to the final last year but I couldn't make it because I was outside the US at the contest's time.

→ Reply
»
10 years ago, # |
  Vote: I like it +21 Vote: I do not like it

So late in such countries as China or Japan... The previous rounds are interesting. What a pity!:(

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

OMG! It is 1 a.m. Monday in China...:D end at 3:30... rating updated at about 4... then go to bed... And at 7 a.m I should go to the railway station and go to school. The train will cost me 8 hours... Monday is too busy for me to have a rest! Amazing Monday!

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

    Are you kidding? It's summer now — who's studying in July?

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

      But according to my parents' opinion, if I want to grow taller, I should go to bed early... T_T

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

        you can go to bed 2 hours earlier than usual, that means your sleep time of a whole day is the same.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          And when I fall asleep the clock will wake me up... Anyway it is an acceptable idea:)

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

      Because I feel boring staying at home in summer holiday. And at home I must cook dinner for myself owing to my parents always not coming back home for dinner. After friends and classmates of middle school meeting, I have nothing to do but training coding skills. Home is not a good place to train. I think I would better go to school.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I don't know about China, but it's not so unusual that we still have class in July in Japan. My friends in Japan are now taking the final exams! (In Japan, school starts in April, and the first semester often ends in July.)

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

    I catched math big god wow!

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh No~ 10:00AM PST， 1:00AM BEIJING

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes ~(T.T)~~ and 7 p.m ~ 9 p.m.in Beijing Sunday,is the bestcoder round#2...in hdu

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hey, are you both from China?

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

        Yep... there are a lot of Chinese acmers in Codeforces~

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

          I'm from China, too.

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

            I guess too~, People's Republic of China Jiang Su Wang Tianyi...Nice to meet you~are you a middle school student? Or a university student?

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

              Middle school, Nanjing Foreign Languages School.

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

                aha, so you are a noiper~

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

                Me too~I'll study in Nanjing Foreign Languages School soon~

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

    I am luckier a little.

    Converted Time

    Hanoi, Vietnam

    00:00 ICT

    Monday, 28 July 2014

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the programming language I can use in this competion?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow I have always wanted a Start[c]UP 2.0 t-shirt! Very intriguing prize! Good luck to all participants as I am at camp and will not be able to participate.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the complexity of the problems will be comparable to a regular Codeforces round

Regular Div1 or regular Div2?

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Registration is running, but it's "Private Registration" !!! What's going on!?!??! :D

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

When I try to register it says — "The contest does not allow self registrations".
Edit: Thanks, it is fixed.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can people in div 2 participate in this contest and be qualified for round 2 if they come in top 500 ??

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Just noticed that logo of memsql is very similar to that of Mumbai Indians, one of the Indian Premier League teams.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this for DiV 1 or DiV 2 ?

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

    "There are no eligibility restrictions to participate in the round". It is open to both the divisions.

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

      I meant it difficult hardly for div2. I think.

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

        if you think that it will be hard for you. you can not write it.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        We believe that participants from Div2 will still enjoy the round.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Thanks for morale boosting :D

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          seriously? sir! :(

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

          I believed the same, before the contest.

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

            That means you qualified for the second round. If that's really the case truly- Great spirits and congrats :).

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

              I used the word "before", not "after".

              → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

we are muslims we will be having breakfast as it is the last day in holy Ramadan :) 27th

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it +8 Vote: I do not like it

    Yeah , this contest will start exactly at our iftar time in Syria. however , I still want to participate.

    BTW, happy feast tomorrow to you and all muslims!

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The contest will be rated for both div1 and div2 participants?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can tell score of problems?

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

This contest start at the same time of (Iftar)
It will add another 2.5 hour to 16 hour without eating :D :D

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I'll do the same :'D this must be added to "You know you are a competitive programmer when .." :D

    → Reply
»
10 years ago, # |
  Vote: I like it -12 Vote: I do not like it

I don't think will have ocasion to continue with round 2

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

contest is not simple !

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How was problem C to be solved?

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

How to solve problems B, C, D, E, F ?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    For B, most probably the zig zag pattern made by (0,1) (n,m) (0,0) and (n,m-1) was the 4th one to be checked. The other 3 were only X-axis, only Y-axis and the 2 diagonal-one maximum side pattern. This passed pretests. Not sure though. System tests would tell us better. --- Nope, failed systests -- The method is right. Mine failed because of a typo :P

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretests were very weak again!
Lots of solutions on B, C, D will fail.........:SS

→ Reply
»
10 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Contest finished! But personally, I didn't like the idea of putting the arrays of names in problem A in sample test explanation place; because I think many people (including myself) do not check the explanation when they understand the statement. Maybe it was better if they were higher.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cmon, place your bets! Who thinks this solution will pass the final tests? Hurry up!

7269849

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

I got a kind of stupid solution at B and got hacked. I passed the hack 3 seconds before end of constest. :)) I hope it passed.

Edit: It passed. :)) Thanks to the hacker.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I scared I will get down rating !

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any particularly tricky corner case for problem B?

I see many successful hacks, but I can't come up with any special case.

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Running java programs with -Xmx512m and ML 256m is evil. I've spent most of the contest trying to make sure that my E fits in ML regardless of GC behavior :(

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

    Why not use "Off heap" memory? No GC, smaller memory footprint.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      I don't know much about off-heap memory, but I actually need GC functionality. The problem is as follows. With an implementation of suffix trees which I use (nice, readable and object-oriented, not the horror from e-maxx), total memory which is really used is pretty close to ML. Since there is Xmx512m option, theoretically nothing prevents java from growing it (by a constant factor) above ML (it thinks that it has 512m available, so it can decide to allocate a bit more in advance).

      So I decided to use an optimization: instead of Node[alphabetSize] store list of pairs (char, Node) until it grows to some constant, and then free it and use full-sized array. However, my calculations show that if GC does not reuse the memory which was freed, theoretically it is again possible to go dangerously close to ML (on logarithmic scale).

      Anyway experiments show that even my first submission passes all tests with "memory used" 188400 Kb. Maybe I'm overly paranoid, but I want my solution to be guaranteed to pass, not just pass by luck. And IMO setting "Xmx" to match actual ML would be a very good idea.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

contest really hard, hard and very hard (with me)

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it -77 Vote: I do not like it

Difficulty of problems, my impression:

A,B — div2 A

C,D — div1 B (I find D easier than C)

E,F — div1 D-E

Yet another situation (after Zepto Code Rush) where the problems are split into easy and hard ones, and time is the main tiebreaker on the easy ones. Although I don't know how many pretests there are, so I can fail on any of B,C,D during the systest.

I can write it in bold caps: MY IMPRESSION. Also, before systest.

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

    What was the approach for problem B ?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it -10 Vote: I do not like it

      I can't believe it -.-

      I got AC after contest ended. Two lines of code and it was fixed!

      There is a little 'hack' that I like to use. Watch others submissions AC's and how much system resources they use... When I saw some solutions using a lot of memory then I figured out it MIGHT not be an easy one line solution.

      My approach: Fix two points (0,0) and (n,m). You can see that it must be included in the optimal solution. Then you have two points to select among 4000. It's not wise to choose a point inside the rectangle... So choose two distinct points that lies in the border (that's up to 4000 points!). So you can run O(4000^2) to pick those points. For each set of 4 points you still have to select the best order, that is, assing p1, p2, p3, and p4 and compute the length. Pick the best, and you are done! (m==0 || n==0 you can solve by hand)

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

    F is far from div1 E and... how to solve B -_-?

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

      I just tried all the possible 4-tuples of what I considered "important points". This passed pretests. I hope also system tests (((

      7262613

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    saw a lot of hacks to B, so doubt it's div2 A level

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

    I find C easier than B.

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

      How did you solve C?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Well, this formula 1/n + (n - 1)/n * (m - 1)/(mn-1) is a solution.

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

          I need explanation !

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +84 Vote: I do not like it

            Well, There two possibilities to get the same card. 1) One card was chosen twice. Probability here is 1/n 2) Different cards were choosen. Probability of that is (n — 1)/n. Let's see on all cards that was not chosen first time, All they ahve the same probability to be chosen. There are m — 1 out of mn — 1 cards that equal to first one.

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

          magic..

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

          Found the same formula but didn't check when n=m=1...and got a WA

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    B = Div2 A? Nice joke :)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -41 Vote: I do not like it

      First, I wrote this before systest. Second, it's B. Third, there were a LOT of passed pretests, and there are still a lot of passed systests.

      Right now, I'd say that B is div(-1) stupidproblemIdontwanttocompete.

      Your comment is just as biased as mine.

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

        Did I miss any announcement of some special prize that will be served if this guy (Xellos) gets a certain number of down vote? A man with +122 contribution to this community is getting down vote even without using slang, or native language! Come on, he just shared his feelings with you guys. Anyway I "donate" my +23 contribution to you,down voters . Please take it!

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    For me, B and C were much harder than E.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      I didn't really try to solve them, and this was before systest. As I wrote, "my impression".

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

      Sorry, but stupid bruteforce + obvious combinatorics can't be harder for noone than some fancy algorithm on LCP xd.

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

        Obvious combinatorics is not that obvious for some people(like me =)). And no fancy algorithm on LCP is actually required in E, there is a well-known solution with suffix automaton for these type of string problems which is simple to understand and implement if you have seen it before.

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

        Did you say harder? If it's true I couldn't understand your reply.

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

          Lol, of course :D. Thanks for pointing that out :P.

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

        Just take a look at performance of kb.:)

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

    B can not be compared to any div2 A. You can see number of Submitted Solutions and number of Passed Solutions.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    You failed div2 A systest :)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -44 Vote: I do not like it

      Nothing unusual for any problem with weak pretests, a lot of special cases, and considering I'm the one solving. Nearly everyone I see in my Friends tab failed B, even, so the last part can probably be extended.

      I can write it in bold caps for you, too: MY IMPRESSION.

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

        Your impression is wrong.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it -59 Vote: I do not like it

          Your head is wrong, see this comment.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +55 Vote: I do not like it

            You try too hard.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it -13 Vote: I do not like it

              I see nothing wrong with trying to find where I made a mistake, and neither with having opinions.

              But I try too hard at anything, it's better than the opposite extreme :D

              → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah ! I accepted only once problems A

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

why my solution for problem A skipped?

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

    mb you cheated at contest? I you not, you can ask to MikeMirzayanov

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

    If you submit a problem multiple times, only the last one will be judged. The rest will be skipped.

    → Reply
»
10 years ago, # |
  Vote: I like it +23 Vote: I do not like it

very fast system testing! :)
thank you very much! :)

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

congratulations sevenkplus !

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +67 Vote: I do not like it

    yeah , he got 7k+ points... :)

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Wow very fast systest (considering this is a special round with a lot of participants).

Anyway, why problem C has the same point as B? I think problem C is much harder....

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

    It's just depend on the participant if it's harder or not. For those who likes such problems as me it was easier than B. So equal points is quite a good idea.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Answer to C: (n = m = 1 is a special case). Doesn't look very hard.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ah I miss this simple solution. No wonder....

      Anyway, this euphoria is over. I think I will back to yellow :'(

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

      Can you explain how you obtained that expression?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +38 Vote: I do not like it

        I considered two cases. The first case is when Alex chooses exactly the same card as you do. The probability of this is . Otherwise, you and Alex choose two different cards, and any pair of different cards is equiprobable (so, the fact that they are chosen from a random subset of size n is irrelevant). In this case, the total number of choices is , and the number of choices that result in the cards being of the same type is . By properly combining all these numbers, you get the answer.

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

      how do you reach this formula ?

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will you be providing the editorial?

→ Reply
»
10 years ago, # |
  Vote: I like it +68 Vote: I do not like it

Sorry, I didn't like any of problems from A to D at all, can't say anythig about E and F though. And seriously, how is D being D? It is much much easier than B and C!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Agree that any of problems A-D was interesting at all...

    → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

My answer is correct for problem B, pretest 1, submission #7269214

1 1
0 0
1 0
0 1

But verdict is

wrong output format Unexpected end of file — int32 expected
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A possible reason is that you output newline as '\n' rather than endl. Remember that test machines are running Windows, which uses "\r\n" as line separator.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      I have always used '\n', never had this error before.

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

      I don't think that's a problem. When you print '\n' it automatically converted to '#13#10'

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Your output is empty. And you've shown the right answer

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

      Ah, yes. How stupid of me! But the reason I got confused is because my compiler was producing correct output. I found the problem to be compiler specific, in my machine the code outputs different but correct answer:

      0 0
1 1
0 1
1 0

      My compiler info:

      >>> g++ -v
Using built-in specs.
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.4.7-8ubuntu1' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c++,fortran --prefix=/usr --program-suffix=-4.4 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --disable-libmudflap --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.4.7 (Ubuntu/Linaro 4.4.7-8ubuntu1)

      I used direct comparison between doubles (a == b), which failed in judge compiler.

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

    I changed double in your solution to long double and it got AC

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

First of all , problems were awsome. B was harder than expected and D and E were interesting. C was maths , but I liked it.

On the other side , I think the pretests at C were weak. I put m instead of n in one place ( in a for ) and because of that it didn't passed. I think that pretests are made for this kind of situations.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for tasks E and F. Looking forward to reading the solutions to those.

I didn't like the rest of the tasks though. A and B were "let's see who forgets to code one if". Disliking C is my personal opinion — but I heavily dislike N <= 1000 when there is O(1) solution. As for D, I only have to say that I haven't even read the part "Moreover, after a piece of laundry is washed, it needs to be immediately moved into a drying machine, and after it is dried, it needs to be immediately moved into a folding machine", and my "solution" still was accepted.

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

    A: A is to guarantee that most contestants get at least one AC.

    B: Apparently B has a better solution than a bunch of if's.

    D: Perhaps the two problems have exactly the same answer. Who knows? Can you construct a counterexample?

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

      about D: I think he meant that it was not reasonable to include it to the statement at all.

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

      D: No, I can't. If there is an easier approach, which can be written by accident or in wrong belief that it's the correct one; then it's authors' job to differentiate two approaches. If they haven't foreseen this approach, well, it happens sometimes. Still doesn't make it a good task. If they have known about this solution (but just couldn't find a counter-example), then this task shouldn't even be given, or that extra text should have been removed and the task should be given with less points.

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

        The problems are equivalent I think. There is no difference between having a piece of laundry wait before it goes into the first dryer or having it wait in between consecutive dryers.

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    In my honest opinion, not having the restrictions hint to the complexity of the solution adds to the difficulty of the problem. I couldn't figure out problem C for some reason. But I bet I would have had better chances if the author had written N <= 10^9. Then, my brain would have been focused on finding a formula, not all over the place thinking about DPs and such.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I did it with DP in O(N^2), so I think it whould have been harder with a formula. ( maybe worth more points )

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

    Well, If you code ifs in A or B they solved their task to diferrentiate people who will write and debug tons of ifs and those who will write 5-lines solutions where one can't have bug.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems were very interesting...!! Thanks to authors... Nice contest...!!!

→ Reply
»
10 years ago, # |
  Vote: I like it +29 Vote: I do not like it

How to create a good test for problem F?

I accepted the following flawed solution consisting of two steps.

  1. A naive approach would be: for each number x in the permutation, for all possible deltas y, check whether x - y and x + y are on different sides of the x. A partial solution is to check only the MAX first and MAX last values of y in this approach. In my solution, MAX = 60.

  2. Another naive approach reduced to a partial solution is: for each position t in the permutation, look at values at positions s from t - MAX to t + MAX, check if p[t] is between p[s] and 2*p[t] - p[s]. Again, MAX = 60.

Looks like random test with only one valid pair (a, b) as an answer would make this solution fail with a good probability. So, is it possible to create such a test? If it is possible, how to do it?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    Test with only one valid pair can be constructed in this way. If you know a permutation p1...pn which has no valid pair then 2*p1-1,...,2*pn-1, 2*p1,...,2*pn will also have no valid pair for example 1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16 . Now if you will move for example leftmost even number to the left of the rightmost odd less than n/2 then you will have one valid pair in the example 1 9 5 13 3 11 2 7 15 10 6 14 4 12 8 16

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

      In general, if you take a permutation without valid pairs and swap two adjacent elements, you would get at most two such pairs. And with a good probability, you get only one.

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

      Thank you, this construction seems to do the trick.

      By the way, the problem's test set catches me if I try using only the first part of the solution above, but lets me pass if I use only the second one.

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

      While the test you provided is what I literally asked, it does not break the second partial solution. In your example, 2 and 7 end up being too close. If we move 2 further to the left, more valid pairs will appear, such as 2 4 with 3 between them. Similarly, moving 7 further to the right soon produces the pair 13 7 with 10 between them. The problem seems to persist if we build a larger example following the same procedure.

      So, how to break that partial solution, too? It would help to insert some "garbage" between 2 and 7 in the example, but we don't have any "garbage" left if we follow the procedure.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 4   Vote: I like it +3 Vote: I do not like it

        Look at this permutation a = { 1 5 2 6 3 8 7 4 }. For each pair (i,j) index of (a[i]+a[j])/2 is not i+1 and is not j-1. This means that in each valid triple no two are adjacent. Valid triples are 1 2 3 , 5 6 7, 2 3 4. Now consider we have the permutation [1 9][5 13][3 11][7 15][2 10][6 14][4 12][8 16] in each bracket the numbers give the same remainder when divided by 8. Now replace in permutation a[] whith this brackets according to their remainder. You will get [1 9][5 13][2 10][6 14][3 11][8 16][7 15][4 12] in this permutation the valid pairs can be only with the same remainders as in permutation a[]. i.e. from group [1 9]-[2 10]-[3 11] can be choosen respectively triples and each member of the triple can be from its respective group for example 9 10 11 are choosen from the first second and third brackets. Now imagine you have constructed a big permutation as before and replaced all brackets according to their place in a[] then in each valid triple members will be far from each other because in a[] in each triple the distance of each two is at least 2.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I enjoyed problem C very much as it has a very small and smart solution. And I am really eager to know how B can be solved without the use of more than 6 or 7 if. I can't solve B but any solution i see use more than 10 if !

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

    any solution i see use more than 10 if !

    7271199 — here, i solved it (in practice) using eight if.

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

    My solution:

    n/m = 0 how to handle is given in the test case n,m>0:

    looks like only four cases

    sol: http://mirror.codeforces.com/contest/452/submission/7267559 7 ifs with two from predefined functions

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

      i think when (n>0)and(m>0) we only need to compare 2 of them.

      if n>m, the first way is obviously longer than the second, and the fourth is longer than the third. so we only need to consider the 1st and the 4th.

      if n<=m, we only need to compare the 2nd and the 3rd.

      my code:7273175

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

    Like this.

    This version of my solution is a bit messy! I'll rewrite it to be a bit easier to read.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    --ignore--

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      if(nowDist > maxDist)

      what about this one? :D

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

    How about using brute forces, we can search (0,0) (0,1) (1,0) (1,1) (0,m) (n,0) (n-1,m) (n,m-1) (n-1,m-1) by dfs.

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In problem A I failed this test case 6 ......

but I assumed that there must be at least one letter in the input from the problem's statement "you already know some letters" and "fits the length and the letters given"

→ Reply
»
10 years ago, # |
  Vote: I like it -22 Vote: I do not like it

I had thought accepted problems F with randomize (YES or NO)

→ Reply
»
10 years ago, # |
  Vote: I like it -79 Vote: I do not like it

I now see why I failed B. One line that I forgot to remove from an older solution: if(N > M) swap(N,M);. I got AC after removing it. (submission during the contest: 7262088, after the contest: 7271312)

Therefore, my opinion that it's div2 A level holds.

My solution was: we either use the strategy from sample 1 (diagonal, vertical/horizontal line, diagonal) or the first obvious greedy (longest non-diagonal starting in a corner, diagonal, longest non-diagonal starting in the other corner). Special cases N = 0 or M = 0.

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

    Pretests on B were very weak.

            x=make_pair(0,0);
        y=make_pair(N,M);
        z=make_pair(0,0);
        t=make_pair(N,M-1);

    I failed B because I mistyped the points for one "case", yet I still passed the pretests.

    → Reply
»
10 years ago, # |
  Vote: I like it +25 Vote: I do not like it

When will the contest be rated usually in codeforces?

→ Reply
»
10 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Why is rating update taking so long?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I always wonder why system test is faster than rating update!

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

      Generally the rating the updated with in half an hour of the system testing, but today i don't know what is it that they are taking so much time.

      → Reply
»
10 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Country wise rankings for this contest has been updated. (link)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    thanks! feels so good to see myself topping my country, Alhamdulillah! :D

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

      Alhamdulillah :)

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

      I think you deserve it sister. Your performance in CodeChef is also same as far I noticed! Congratulations! :)

      → Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

When will Ratings be updated ?

→ Reply
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

waiting for the editorial :)

→ Reply
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Ratings are updated!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Oh! At last having the test of being purple for the first time! Alhamdulillah. :)

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Still Div1!

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

    I'm surprised that I added rating. I decided two tasks are not particularly slowly. (Google Translate).

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

I solved F using pretty weird observation:

If answer is NO, then parities of elements in our sequence look sth like:

0000000000010001111111111111 / 1111111111100110000000000.

I mean, almost all odd numbers are before almost all even numbers or the other way around. Some inversion are possible, but only a small amount of them. Does anyone can provide appropriate bound for numer of those inversions? I bruteforced small cases and for n=10, there were at most 4 inversion, for n=13 at most 6, so I assumed that n + 10 is a safe bound and it passed. I checked manually whether those inversions are a part of a bad triple and later call recursively for odd and for even numbers which resulted in a O(n log n) solution. But I still don't know why it is correct :P.

Unfortunately I got one integer overflow in my solution and it wasn't accepted :(. After adding "1ll * " it passed ;/.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +16 Vote: I do not like it

    During contest I found a paper that said that if n>11 then the parity of the first floor(n/2)-6 was the same and the parity of the last floor(n/2)-6 was also the same. However, I didn't come up with your solution; nice one!

    Edit: paper

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

      Why those papers are always so long :(? How have you managed to prove that observation? I don't feel like reading those 15 pages xd.

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

        I actually just skimmed the paper to see if I could find ideas for a probabilistic algorithm. Without having read it in detail it seemed to me that a great part of those 15 pages were devoted to prove this, so I think it mustn't be easy to prove. One think that bothers me though is that if I understand the theorem correctly the correct structure would be more similar to: 00000000000/11111111111 or 1111111111/00000000000 since we can't have 0s at both sides (we would have 2*(n/2-6)>n/2) though this is not true for n<24

        Would your algorithm still work with this 'structure'?

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

          Um, sorry, I somehow understood that you proved that observation, but you wrote that you found it on a paper :P.

          And that sign "/" was meant to be "or". Those were 2 separate sequences :P.

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

            We both read each other's comment wrong then!

            It all makes sense now :)

            → Reply
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Round Stats

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please anyone explain how to solve D?

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

    Straight forward implementation.

    We will simulate the process second by second.

    For each machine, keep a list of pieces inside the machine right now and for each piece save its entrance time.

    Every second, remove from machine(3) the pieces whose entrance_time + t3 == current_time. Do the same for machine(2) moving pieces to machine(3). Same for machine(1)

    Now at the end of each second, try to put as much new pieces in machine(1) as possible.

    You need to check that there is an empty place in machine(1) right now and that there will be an empty place in machine(2) after current_time+t1 and in machine(3) after current_time+t1+t2.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Need to find a time when every thing is finished.

    Thing can start washing (drying or ironing) if the machine is free.

    That is if i - n[j] >= 0 then T[i] (beginning the process) = max( T[i - n[j]], T[i] ) else T[i], j is number process, i is number thing.

    End process is T[i] = max( T[i - n[j]], T[i] ) + t[j] or T[i] += t[j].

    Necessary to calculate the time after completion of each process. Answer is T[k].

    Source code: 7271703.

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm waiting for the editorial,it's so sad that I couldn't solve any problem last night TAT

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm sorry to ask this, but when the editorial will be published? Since i'm a newbie in competitive programming i can't understand most of the problems. It would be very helpful for people like me if you publish an editorial on the contest. Thanks in advance :)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Contestant thank you for good contest.

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can we expect an editorial here?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, Some of the tops I see have used something like a log table. Can someone explain what log array has to do with this?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    I had logs in my solution, just to prevent floating-point overflow. I was handling probabilities by counting the number of ways of choosing cards under certain conditions, and dividing at the end by ALL the possible ways. But these numbers (1000000! / 999000!) are far too large for doubles. So I worked with their logs instead. You don't lose too much precision.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Since every binomial in the solution has k ≤ 1000, another trick is to multiply and divide at the same time at most k times:

      double r = 1;
for(int j = 0; j < k; j++) {
    r *= n-j;
    r /= j+1;
}
      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used the formula , and it worked in this task as well:

      double ncr[1111][1111] = {0};
for (int j = 1; j <= n; j++) ncr[0][j] = 0;
ncr[0][0] = 1;
for (int i = 1; i <= n; i++) {
    ncr[i][0] = 1;
    for (int j = 1; j <= n; j++) {
        ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
    }
}
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'll take a look at your solution, it is something interesting) You need just C(n,n) — while naive combinatorical one uses C(n*m,n) (number of ways to generate deck and other stuff like that), which is too much for Pascal's triangle.

        Or could you please explain it by yourself? :)

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

          I calculate for k = 1, 2, ..., n the probability that the first chosen card appears exactly k times in the final deck and the first chosen card matches the second chosen card. The sum of these probabilities is the answer for the problem.

          Thanks for asking this, I didn't notice the other method that uses larger binomial coefficients. :)

          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@Mike Mirzayanov i have submitted my code for Problem A : Eevee during contest and it was accepted after the contest i saw in the Verdict tab writes skipped and my submisson have no score then i send again the same code after contest and it was accepted :( why this happens?

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can I expect editorials!

→ Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

http://main.edu.pl/pl/archive/ilocamp/2011/art — here you can submit F in a version when you have to count number of those pairs, not just state whether it's 0 or more :P.

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

    It is also said that you can assume that the result will never exceed 1,000,000. I think it is quite important.

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

      I was thinking about counting number of the pairs faster than in O(number number of them * log^2), but didn't manage to find a solution. Not sure if it is possible.

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

        Hmm, I believe my solution can be extended to count them in O((N + #pairs) * log(N)), but it's quite tricky, I'm kind of "cheating" using polynomial hashing, and that's not much of an improvement. :)

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

          Yes, my solution is also tricking around polynomial hashing (using binary search and information about previous differing characters positions to determine next one), but it has log^2 factor due to segment tree using.

          It's an interesting question how to avoid quadratic #pairs factor.

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

            It sounds like we have the same algorithm. But it looks like I was mistaken. I thought I could avoid a log factor using amortized constant-time segment tree queries, but that requires making O(N) queries, whereas we're only doing O(log N) queries. So the log^2 factor won't go away. D'oh!

            → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        My solution ( http://mirror.codeforces.com/blog/entry/13095#comment-180008 ) clearly can be extended to counting by generating all inversion and checking them all, but I don't know how to properly estimate complexity. For F mentioned paper states sth which implies that if there are >36 inversions, then there is at least one good pair (a, b). Maybe there is a constant such that if there are > M * k inversion then there are at least k good pairs (a, b)? If this will be the case, then overall complexity will be O(n log n + result), but there's a large constant next to result. There also a possibility that such constant doesn't exist :D. But maybe it can be at least proven that we can replace M by something growing slower than log^2 k :D. That means that following statement will be true:

        if there are > M * f(k) * k inversion then there are at least k good pairs (a, b) (where f(k) / log^2 k -> 0)

        If so, we will get better solution : p. But until something here will be proven this is some kind of meaningless considerations :P. But on a contest I will give it a try :P.

        → Reply
»
10 years ago, # |
  Vote: I like it +48 Vote: I do not like it

If not full editorial, please at least put the editorial for problem E and F. Editorials of other problems can be posted as comments of discussion in the blog.

→ Reply
»
10 years ago, # |
  Vote: I like it -12 Vote: I do not like it

I think best solition for problem B is this . best means that code is easy to read

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    And what do you think?

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

      Copy-paste shouldn't be your friend (though it was mine in this problem xd)

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

        there is a lot of DUPAs in your code, which sounds funny if I've understood it correctly :-)

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

          As I said, my code for this problem is one of the worst codes I have ever written :P.

          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does this mean from now to 8.10 ,there won't be any other CF round ?

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anybody explain the solution of problem E ?

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

    Problem is easily solvable with suffix automaton. We can use modification of algorithm from e-maxx for finding largest common substring of many strings. Firstly we concatenate strings like a#b&c%. Then we build automaton. For each state we should calculate number of paths from it ending with character '#', '$', '%' in variables f,s,t. It can be done with dfs. It will be amount of rightmost positions of current state in first, second and third string. Then we can simply iterate over the states and increase the answer by f[i]*s[i]*t[i] where i is a number of state for all different lengths of substrings that are compressed in the state. I.e. for the segment (len(link(i));len(i)]

    You can check my solution for better understanding: 7265940

    → Reply
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Who's in?

yarrr, Igor_Kudryashov and Goofy57 definitely are.

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I can't register to contest. When I click "Register now" I receive notification "The contest does not allow self registration"

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

    Did you choose the correct contest (online round)?

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -41 Vote: I do not like it
    The comment removed because of Codeforces rules violation
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      I already took a place in top 500 (such a great achievement xd) and I don't have time to come up with creative answers, so simply shut up retard.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      > rude post

      → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I hope they give editorials this time.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will people who not finished in the top 500 in Round 1 be rated ?

→ Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

It's been 2 months now since the contest...and the promised editorial has not come out. Are there still plans to release this?

If not, maybe we can compile all the relevant comments together to form what we already have.

→ Reply