chrome's blog

Topcoder Single Round Match 679
By chrome, 9 years ago, translation, In English

Hello everybody!

Tomorrow at 15:00 MSK will be held Topcoder SRM 679.

Let's discuss problems after contest.

Contest start less than an hour and a half, you have time to register!

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

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

Curiously, in div.1 easy, why do we need 2 arrays salary and productivity instead of one?

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

    Probably just to make the problem statement a little bit more interesting. Obviously it was not necessary to work with the two arrays. You can replace them with one array called profit. Any many people have done this.

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

      Let's make statement even more interesting by adding a few more arrays — direct income, indirect income, taxes...

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

        The reason was to make the statement more interesting, I knew it wasn't needed but it made more sense.

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

Facepalm. Hard solved 54, medium solved 29.

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

    In Soviet Russia you do not solve problems, problems solve you

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

One serious question. What do you think about examples in TopCoder? Is it ok that in some problems they are very weak, like in geo today? I think it's fine. It makes a problem harder and gives a possibility to do something during the Challenge phase. Or do you maybe think that it's unacceptable to make examples so weak?

FYI: I didn't organize this SRM.

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

    It should ignore some corner cases, but shouldn't be shitty like that. It should contains some large random test cases

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

    I hate so weak samples in such tasks.

    I would accept sample like "1\n1 2\n" if in task there is a permutation and there is a very easy slow (e.g. n!) solution, which I can write in one or two minutes to stress my solution.

    But in non-trivial geometry task like this I should write very non-trivial slow solution and non-trivial generator to check my solution. It would take me for half of the contest, so, I just submitted this problem when I have passed samples. Fortunately, I rechecked my code and resubmitted it after few minutes, because I made a stupid bug, and samples didn't catch it.

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

      But you didn't have to write a slow solution and generator, you can test your code however you want. In this case it was probably easier to make some cases by hand. Testing solutions well (finding the best way to test, making good tests, etc) is also a skill and a part of competition as much as solving problems in the first place.

      Of course it is up to the problem setters how strong their samples are but I don't think they should make them strong just because testing is 'hard'.

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

    On systems where you don't get any feedback about the correctness of your code during the contest (TopCoder, Facebook Hacker Cup, Google Code Jam, etc.), I think that the samples should be a bit larger so that you don't make a very trivial mistake that is caught on every case except the really small ones. However, for contests where you are given some feedback during the contest (ICPC, CodeForces, etc.), I think that weak sample data is perfectly fine because you are told that your program is wrong during the contest and then it is up to you to find out where you are wrong.

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

    Weak examples for 250s (which usually contain corner cases for hacking) and strong examples for 500s.

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

    No less than 8 samples was the rule I gave myself for my (one) SRM. Competitions like TCO final may be an exception, but I tend to differentiate between competitions and lottery. I'm not really interested in preparing the latter.

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

    I'm sorry for the weak examples. We didn't intend to make a lot of solutions fail. What is intended (at least by me) is not to cover every corner case of the problems so that you have to think well the solution and then have chances to make challenges. I'm sorry if this bothered many of you.

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

      Ok. But the problem requires to draw a convex polygon, but all samples has this property: All blue points lies on boundaries of a convex polygon. This let me forget to check whether my polygon is convex. The test I failed, which is a small random test with 10 points each color, can be included on sample. It is general case, not corner case.

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

        You're right, I didn't notice that and neither did the testers. Besides that, as a general advice, always try to create you own tests by hand to test before submiting.

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

          That won't help anyone find out that they missed something in the problem statement, which is one of the most important reasons for samples. Besides, solving geometry problems on paper is more of an expected skill of an architect or engineer, not a programmer.

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

    I think that the samples always should be good, because solving of the problems is more important than challenging other solutions.

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

div2 problem statements were unnecessarily too large. And compared to previous rounds, problems were not interesting at all. Mere implementations :/

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

I successfully hacked a solution with pretest. Is this possible?

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

My 500 is fallen. I think it's TL. Am I the only one who solved it with O(3^(n/3))? It's really weird, I was competing in the srms with problems about maximal cliques.

The idea: let's assume that we've taken a set of blue points. We need to check that it's convex hull doesn't contain any red points. It's equivalent that for every pair i,j triangle 0,i,j doesn't contain any red points. So we just need to fix the 0 point, and then find the biggest anticlique.

Update: my fault, too hard to write five-lines algorithm.

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

Anyone knows the solution for Div1 medium? I had some ideas like finding the largest convex subset of points after fixing 1 point and doing some stuff with convex hull. But it was too complicated and my geometry skills are poor :P

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

    First for every triangle with blue points as vertices compute number of blue and red points inside that triangle. Then fix lowest leftest point of the convex hull. Imagine that we build the convex hull. To add a new point we need to check the last 2 points that are already in the convex hull. So we sort all points by angle and calculate dpi, j =  maximal number of blue points if the last 2 points in the convex hull are pi and pj. To calculate it we try all pk with angle larger than pi, check that cross product of points pi - pj and pk - pi is positive and check that triangle (o, pi, pk)(where o is lowest leftest point) does not contain any red points.

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

      Understood the solution now! Thanks for explaining:)

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

Screencast

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

For Div1 900 in Testcase #2, I'm getting 890856142 instead of 450750683 on my laptop. During the contest I tried the brute force solution and didn't manage to debug it. During the challenge phase I wanted to challenge one solution with an obvious bug (which did fail the system tests), but wasn't sure about my input because for their code I was again getting 890856142. After the contest I took tourist's code, and still the answer I'm getting on my laptop is 890856142. What can be the reason?

BagAndCards.cpp — http://pastebin.com/pVGf2RNz

BagAndCards.sample — http://pastebin.com/eSFGqDWS

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

    I discovered the bug for one of the members of my team. It is an issue with Greed, actually. It downloaded the inputs incorrectly. If you look at the BagAndCards.sample file, it is wrong--There are quotation marks around the string. I should point out that I also use Greed, but a newer version, and this did not happen to me during the contest, so you may want to consider upgrading. =)

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

      Oh, thanks, I should have noticed the quotation marks ...

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

Another question (curiously), did anyone think about FFT while solving div.1 hard? Does anyone think that the problem setter was thinking about FFT while choosing this problem as div.1 hard?

Edit: My fault, FFT is too slow for this problem.

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

    Are you sure? FFT was my first thought and it looks like an intended solution (big TL).

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

      I originally thought it was FFT as well. After a quick scan through the AC solutions, I don't think anyone got FFT accepted. Some people tried it, but everyone got it wrong for one reason or another. The intended solution is better (both runtime wise and asymptotically) than doing the O(n^2) FFTs.

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

      Haha yes. Actually I only tried to solve this after contest. The progress was like this: After reading the statement, I thought about FFT (because of big TL), but I didn't know how to face up with mod 1e9+7, so I looked through some accepted codes. After looking, I realized that FFT wasn't required. Hence, I posted the above comment to ask you guys, but while posting, I forgot the TL and thought FFT is too slow. LOL

      Btw, anyone tried to code FFT for this problem?

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

    The intended solution is something similar to FFT: instead of finding Fourier transform (calculating f(r^0), f(r^1), f(r^2).. where r is a unit root), we just find f()s at any m different values, like we just find f(0), f(1), .., f(m-1). Note that we don't need a 'fast' transform: we can just do it in O(m^2) for each of n vector. And we can precalculate how to restore answer from f(0), f(1), .., f(m-1).

    Code: http://ideone.com/XFomMa

    We intended to use another task that requires above idea, but then figured out that task have a simpler solution (but not like this one.. at least worth 600p). So we decide to change it to a new one just 2 days before the contest — and we just didn't notice this new task have such a simple solution.

    I apologize for this issue and we will be more careful in the future.

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

      It's the solution I used in the contest. :P

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

I cannot understand a case, check out test case #8 from this: https://community.topcoder.com/stat?c=problem_solution&cr=22263204&rd=16649&pm=14117

{0, 4, 0, 6}, {1, 6, 6, 8}, {7}, {2} 4 Passed

I've draw the points but they did not form a convex polygon:

Did I miss something ?

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

    The triangle ABD contains C (C is inside), so all 4 points are inside this convex polygon

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

      Thanks, now I realized that I've misread the problem.

      → Reply