AlexSkidanov's blog

MemSQL start[c]up Round 1
By AlexSkidanov, 11 years ago, In English

Hello everyone!

The first round of start[c]up is upon us. It is open to all participants. Registration works as a normal CodeForces round, and will close five minutes before the start of the contest.

The contest uses normal Codeforces rules, and will be rated. The score distribution is 500-1000-2000-2000-2500.

The problem set has been developed by MemSQL engineers pieguy, nika, exod40, SkidanovAlex and dolphinigle.

Top 500 competitors will advance to the second round, with the top 25 Silicon Valley residents invited to participate on-site, where there will be special prizes.

Good luck and happy coding!

UPDATE: Please note that the score distribution has changed.

UPDATE: Editorial is up now!

Announcement of MemSQL start[c]up Round 1
  • Vote: I like it
  • +165
  • Vote: I do not like it

Comments Comments (140)
| Write comment?
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Glad to hear of such contest :).

How will you determine the top 25 Silicon Valley residents? And what's the definition of Silicon Valley residents?

Will summer interns be eligible? Anyone that is visiting SV during that period? Or anyone who can make it to the round at MemSQL HQ on their own?

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

    "Silicon Valley resident" just means "willing to provide own transportation on-site, or close enough that we can pick you up in a car".

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

Wish this will be my first contest in codeforces.I just registered and hope for a better start. :)

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

    Nice! :) Well you can solve a couple of problems here to get used with this platform :)

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

    "Wish" — "better"

    R.I.P English

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

Woww... 17:00 is the final round of the international volleyball league 2013, Iran VS Germany... Who will hold the contest at this time???

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

    Yeah, there are at the same time but I will hold the contest...

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

Will it be rated for DIV 2 ?

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

1 a.m. o'clock in China... It will be so late and tired at that time though I wish to participate in...

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

So late in China... Obviously I can't participant:( because tomorrow is the first day of National Olympiad in Informatics

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

    Wish everyone good luck in this round as well as NOI...

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

      Best wishes to all who will participant in NOI2013!

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

    Is it a new round for ioi2014?

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

      Yeah...50 gold medals will have the opportunity to IOI2014

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

        Can you explain Chinese NOI format? It's strange for me that ioi2013 ended and NOI for io2014 will start next week)

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

          NOI 300->50 Winter Camp 50->12 Chinese Team Selection Contest 12->4 IOI 4 Gold Medals So long a term is Because the large population:(

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

Is the contest the same rules as div.2 ?

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

I hope it'll be a nice contest.

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

500! among all reds & purples

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

Was someone else also confused by statement of problem A? I thought we needed to test if a subset of given rectangles forms a square.

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

    Yes, me too. Strange that this wasnt covered in pretests

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

      Really? My first solution just checked if any of the given rectangles was a square, and it failed the pretests...

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

        That will fail pretests when no single rectangle is a square but the union of all of them is.

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

        Mine checked if any subset of rectangles forms a square, and it passed pretests.

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

          I've got some bad news for you....

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

          i have succ. hack with this test case

          2

          0 0 3 3

          3 0 4 1

          there is 2 square and answer is "NO" this explains all of this questions:)

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

    That was my interpretation as well. I found the problem statement extremely confusing.

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

    We were trying to be more mathematically correct than "check if the union of all the rectangles form a square", but looks like it backfired... :/

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

      Actually, I like this one. Simple and easy to understand.

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

        This is a little confusing -- example: in this interpretation it's not clear if a square with a hole is considered a square.

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

          Then why not: "check if the union of all the rectangles form a square (without hole)" ? This is much easier to understand. Or somehow have both sentence in the problem statement.

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

            And then there's the recent trend of "shorter statement = good" in CF

            ...but you're right, we should've done that here. Apologies and lesson learnt.

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

          (First, thank you guys for organizing the contest.)

          If you added something like "all rectangles must be used", then there would be less confusion...

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

      "at least one rectangle" ???!!!

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

    I interpreted the same, and got hacked as well. Rest of the contest I tried many interpretations except the correct one.

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

    " determine if the set of points inside or on the border of at least one rectangle is precisely equal to the set of points inside or on the border of some square. "

    Then What do they mean by " At least one rectangle " ? I thought we have to test subset of rectangles. I Understood this After "One Unsuccessful Hacking Attempt ". The problem statement should have been more clear .

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

      The key phrase is:

      "The set of points inside or on the border of at least one rectangle"

      There is a single set of points which defined by the rectangles you are given. The reason for "at least one" is that a point could be on the border of multiple rectangles.

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

        I understand by "The set of points. . ." you meant any point. But during the contest, I overlooked it and was scratching my head to understand, why answer for sample case #2 is "NO" while it has the same set of integer points of sample case #1.

        I couldn't manage to submit A correct but I'm not complaining as I believe, dissecting a problem statement is part of the challenge to solve it correct. But I can't resist myself from saying, "Statement for problem A could be a little bit more clear. Perhaps with a note or analysis of case #2"

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

        Thank You. I don't know why didn't I understand that in contest. May be I have to learn English too along with Programming.

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

        So, that statement includes all rectangles because of "The", correct?

        I guess some people have better understanding of English than others.

        I cannot blame problem statements for misreading them (happens to me a lot) but this one, IMO, was a bit too subtle for a non-English speaking person — especially because of "at least" part (or should it be "... the 'at least' part"? You understood me either way, right?).

        Still, I don't know how I understood the second part to mean "all points within some square" and not "some points within some square". I am inconsistent, that's it. Or the second example clarified it.

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

    I interpreted the same. Something needs to be done about it.

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

    I too got confused with ambiguous statement of A. Developed both cases, and they both passed pretests. So I chose to leave the more difficult case (any subset forming a square). Wrong choice...

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

    I made the same mistake,I realised that it wrong when I tried to hack somebody.

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

    So did I :) Thanks for the guy who challenged my solution

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

    I think this was a big mistake in the problem statement its also very clear it says : " determine if the set of points inside or on the border of at least one rectangle is precisely equal to the set of points inside or on the border of some square."

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

Really disappointed by the last minutes of the contest.., I submitted the solution of the second problem 6 minutes before the end and it remained in queue until the last 40 seconds and then showed compilation error although it was running on my machine...!! http://mirror.codeforces.com/contest/325/submission/4064969

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

    I think that it is being fixed. Because the number of ACs is increasing :)

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

      The reason for the increase was not the fix but perhaps those submissions which were still in queue.. :(

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

So how do we solve B? ^_^

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

    For any answer, let 'x' be the odd number one gets after dividing that answer by 2 repeatedly. then

    n = x*(x-1)/2 + (2^a — 1)

    solve this for 'x' using different values of 'a' (which are very few).

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

    Suppose a required number V has K powers of 2 in it (i.e. we will get an odd number after K rounds of matches). Then V is O*(2^K), where O is an odd number. Now you should write the number of matches as a function of O and K. It is an increasing function of O.

    Then, iterate on K (0<=K<=64) and binary search for a valid O.

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

Why not start system test first..?

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

    Because there is still a problem with hacking attempts...Some of hacks hasn't still been judged

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

Problem A was extremely confusing : subset v/s union. Something needs to be done about it.

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

Someone tell me how to solve B?? I was stacked by that problem, then turn to E.Bu..guess what, my E pass the pretest...

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

    This problem is straightforward.
    Assume the answer is 2^k*k1, where 61>=k>=0, k1 is odd.
    You need to find all (k,k1) such that 2^k*k1-k1+k1*(k1-1)/2=n
    Since k is limited, you just need to solve the quadratic equation when k=0,1,2,3....
    In the end, check whether k1 is odd, sort the solution...blah blah...

    The difficulty is that n is too large.
    I have to use BigInteger in Java to solve the equation.
    I also saw someone use long double in C++ as well

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

      Emmm...Generally clear(Why didn't I think of that>_<).THX~

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

The first problem was very poorly written and not clear at all.And no explanation of the test cases made it worse.Very disappointing.

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

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

    You just wait for system tests. I suppose something will change...

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

And for 2 hours I believe the statement for problem A was correct and couldn't understand how that could be a 500 point problem...

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

Yeah... This contest was exactly 0,5 sec too short for me to send my solution to E :P. I loaded my code but I didn't manage to click "Submit" :P. My greatest fail on an algorithmic contest!

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

    Indeed, Accepted, eh :P. And 335th place instead of ~30th :P.

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

It's 3:30am in China,I'm waiting for the system test.....

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

Anyone know, why http://mirror.codeforces.com/contest/325/submission/4064830 got compilation error?

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

    is that your main function without return 0?

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

      It is ok to hava main without return, but it doesn't work for g++ if you do not have a return type for main(even if the standard says that no return type means return type is int)

      It is really strange.

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

    (I use gcc version 4.6.3 (Gentoo 4.6.3 p1.13, pie-0.5.2) )

    $ g++ -Wall -Wextra marcin_smu.c++
marcin_smu.c++:32:6: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]

    However, this is just a warning.

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

    It's strange. Your code works on the "Custom Test" tab.

    Maybe you should connect MikeMirzayanov and report this issue?

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

    I've tried your code on the "Custom page" test and it ran correctly. Looks like not only JVM was crashed.

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

Make this contest unrated for those who suffered in the A problem..

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

    I decided not to participate because I had a similar problem with a previous contest where although problem A was ambiguous I decided to submit a solution anyway which eventually turned out to be wrong.

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

when does system testing end usually ?? :)

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

How long does system testing usually last? :-)

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

system testing!! where are you??

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

Those who submitted the subset solution to A, should also get AC. Its lame that there was no such case in the pretests. My solution dint even get hacked.

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

Some people was afraid to send one valid submission. 2551 people registered and only 1188 people sent solutions. Hard contest for div 2 coders like me.

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

Interesting .. I think I have never read problem statement so many times. And as a bonus, my interpretation of statement is wrong (at least according to the discussion). That's kind of disappointing.

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

My solution to problem A was submitted at 00:32. It was hacked at 01:32 but the hack was shown to me after around 10 mins of the contest. btw, I locked my solution at around 01:55. :P

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

subset solution passed XD

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

    Very strange. My solution doesn't passed and all solutions, which failed on test 26, too.

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

    Can you please tell What your code returns for this Input

    2
    0 0 1 1
    2 3 5 6

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

      Strange ... Dixtosa 's code return "YES" for the above case . yet his verdict is AC . bt I got Unsuccessful Hacking Attempt using this case. That Code returns "NO" . Can Anyone plz clarify me the reason.

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

      It prints NO, because he have a bug: if(bit&(1<<i)>0) -> if((bit&(1<<i))>0)

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

    My subset solution failed test 26. But it's strange that I cannot find any difference between mine and yours~~

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

The submission 4064843 got Compilation error and it should be Accepted, can you fix it please? And I made the following submissions after it: 4064970, 4065029 and 4065041. Can you delete them please?

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

When and how will you announce the top 25 Silicon Valley residents?

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

    Will be 2nd round :P

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

      I think the 2nd round will be the onsite round.

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

        Oh ye, sorry, i misunderstood the rules.

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

    The 2 quotes that are not consistent. "with the top 25 Silicon Valley residents invited to participate on-site," Top 25 SV residents => eliminate all non-SV from rank and get 25 people.

    "Yes, top 25 people from Round 1, who are in the Silicon Valley as of August, 3rd." => Top 25 from current rank who are also SV residents..

    I guess there are no chances to get invited onsite if you are not in original top 25...

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

About Task B... I'm curious about how many test case is made by the author, or from which case it's from Hacking attempt. In fact, many got Wrong Answer in case #38...

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

4063931 4063524 4064205 4064405

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

    One more: 4064766 (I suppose they just solved it the same way.)

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

      Thanks

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

        And what about this one 4064895? Will you ban it too?

        Administrative repressions during online rounds of annual competitions continue...

        IMHO, you have no ethical right to ban these submissions. This is like ban similar solutions for A+B problem. Once someone got the idea of this simple solution there are only a few possibilities to code it. So no wonder they are so similar.

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

          4065191 4064895

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

            Right. In this case there is matching of pair of submissions. Typically, if it is first time violation we skip the latest submission. I hope it will be a lesson for both of them.

            I clarified the reasons about submissions noted by [user:cerealgy] below (in Russian).

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

        O_O я надеюсь, у вас аргументы за бан повесомее, чем похожая реализация одного решения. А то страшно жить.

        ============================= (sorry for Russian)

        I hope you have better reasons to ban them than just similar realizations of one idea.

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

          Наташа, зачем на русский перешла?

          Ты правда полагаешь, что это просто "похожая реализация"?

          Она не просто похожи, синтаксические деревья программ совпадают. Код копировался и правился. Первые два кода вообще различаются практически только форматированием. Неслучайно код у zfmdhy786 набран без шаблона, тогда как все остальные попытки на C++ со вполне заметным шаблоном. А еще сравните решения kAc и zfmdhy786 по B. Опять "похожая реализация" с одинаковым синтаксическим деревом. Последняя троица из одного универа, что увеличивает вероятность не просто совпадения. Парочка kAc и liouzhou_101 давно практикуют парное программирование. Посмотрите контест 317. Там несколько задач имеют "похожую реализацию".

          Я полагаю, если замечено очевидное списывание, то надо принимать меры.

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

            Прошу прощения, потеряла дар речи от удивления. Сейчас переведу.

            Я-то, когда кидала ссылку на еще одно решение, имела в виду не "это читеры, забаньте их", а "ух ты, какие короткие и похожие решения".

            Я правда полагаю, что это может быть похожей реализацией. Решение-то простое: строим с конца, ставим каждый раз большего из возможных предков, когда доходим до 1 — заканчиваем дописыванием "0 1". Как это еще писать, если не так в этих посылках? Тем более, если участники из одного университета, логично, что у них один стиль. Вот еще, кстати, такое же решение: 4064517, от автора одного из раундов CF, тоже читерское? (Я и Gassa как-то написали еще более похожие решения на контесте, одинаковые вплоть до отступов, причем находились при этом в одной комнате физически. Списывания не было, был одинаковый ход мысли. Без шаблона я тоже иногда пишу, когда мне кроме stdio ничего не нужно — приятно, когда решение короткое.)

            А может быть и списыванием. Если приглядеться, решение действительно странное (половину случаев в dfs-e можно безболезненно удалить, они нужны только для нечетного n, но для него все равно не строится), и предыдущая история, да, тоже подозрительная, и это как раз аргумент. Но даже с ее учетом, откуда уверенность, что ВСЕ они списывали?

            ==========================================

            Sorry, I was so surprised that lost my speech. Will translate now.

            When I gave a link to one more solution I didn't mean "ban these cheaters", I just meant "wow, how short and how alike are their solution".

            I really think this can be just similar realization. Their solution is simple: construct the answer from the end, putting every time the biggest of all possible anchestors, and when we get to 1 — finish by writing "0 1". How can you write it other way than they did? And if they are from the same univercity, they can easily have common style. Here is one more similar-looking solution 4064517, by the author of one of CF rounds, is he also cheating? (Me and Gassa have once written even more similar solutions, ans there was no cheating. And I also don't use template when I don't nead it — I like short solutions).

            And still, yes, it can be cheating. The solution is strange (a half of it is unnnecessary), and the previous story is strange too (and it's really a reason). But how you can be sure that ALL of them cheated?

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

              ... I print the result in a external file and observe them for more then 45mins but still have no idea until someone tell me "try to build the reverse-graph" then I have realized why it works.

              Although it is a nice problem, but I think the score distribution may should be 500-1000-2000-2500-1500, there are some "constructive algorithms" problems are much harder then this one. http://mirror.codeforces.com/problemset/problem/198/D

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

                have no idea until someone tell me

                Ouch.

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

              Seems that 4064517 was not cheating. And make_pair (kAc, liouzhou_101) have shared code with 99% probability.

              This is the same thing as when you're copy somebody's homework in school. Even your handwriting will change.

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

                I'm not that sure now.

                And thanks, i didn't know about changing handwriting and it actually explains some issues with my students. I wish I had that experience at school :)

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

        4064825

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

I'm a little worried about the difficulty of Round 2. The announcement (http://mirror.codeforces.com/blog/entry/8051) says "comparable to a regular Codeforces round" for Round 1, and "higher than a regular Codeforces round" for Round 2. If today's C,D,E becomes A,B,C, and harder D,E is added...? I don't want to imagine that!

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

    Actually this round's "more-than-difficult-C" was an accident.

    ...and we just underestimated the difficulty of D (this always happen for my problems... i wonder why).

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

      Problem C is very straightforward and it's solution quite long. As I think, many participants solve it quickly and then spend a lot of time writting and debugging it. So, they simply haven't enough time for other problems. On the other hand, D need nontrivial ideas and have simple realization (very beautiful problem). In my opinion, such tasks are difficult for most of contestants due to lack of mathematical imagination. I think the main reason is that usually algorithms are taught directly instead of helping to invent them themselves.

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

        I've found the main idea in D, but have problems with realization (there were two missed special cases: m = 1 and m = 2). The most difficult was contest time (21:00), as for me.

        In problem D, my way was: let's start with maximal network flow of size M. To block it, there should be a cut of size M. But what is a cut of size M in N*M grid? It's obvious that it is a cycle in 8-neighbours grid.

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

          Lots of corner cases is an idea problem, not realization. For example, I used another idea for searching a cycle which works correct with c=2 and I have only one small "if" for c=1 and still contains only one dfs to merge components without storing them explicitly. Finally, of course, using for(i=0;i<8;i++) with constants dx[8],dy[8] help you to reduce the size of your code and save you from bugs in copy-paste, but it is really realization optimization.

          So, imho, mainly you have problems with ideas, not with realization. You've found the main idea, but not all.

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

Wow, I failed B on case 101 because of a precision error. I don't like this contest.

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

    I liked this contest because it reminds me that precision errors are very important!

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

Is there something special about test #24 in D? Can't find my mistake.

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

    Same here.

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

    Try this:

    6 6 14 1 1 1 4 2 2 2 5 3 3 3 6 4 1 4 4 5 2 5 5 6 3 6 6 1 6 6 1

    Expected answer is 13

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

I got this runtime error during the contest: Error occurred during initialization of VM java/lang/ClassNotFoundException: error in opening JAR file C:\Programs\Java-7\jre\lib\rt.jar

http://mirror.codeforces.com/contest/325/submission/4064975 Anybody got any idea why this is the case?

[EDIT] http://mirror.codeforces.com/contest/325/submission/4066219 It's AC! Can this be fixed? :)

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

problem B wa on test45,but the code gives the right answer when running on my own computer.change unsigned long long to long long,I got accepted.

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

Please ignore this comment, editorial is already posted by AlexSkidanov

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

Hello. I have competed in the first round and have taken place 311. So can I compete the second round at home via internet? And when will the second round be held?

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

    The second round will be held online for the Non-Silicon Valley Participants I believe. I will (hopefully) be there too, although I was told I took place 386 but the standings show me at place 408.

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

any update on SV participants?

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

    Mike will send out all the information to top500 very soon.

    → Reply