Блог пользователя chrome

Автор chrome, 9 лет назад, По-русски

Привет всем!

Завтра в 15:00 MSK состоится Topcoder SRM 679.

Предлагаю обсудить задачи после контеста.

Контест начинается менее чем за полтора часа, успейте зарегистрироваться!

  • Проголосовать: нравится
  • +78
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +52 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +84 Проголосовать: не нравится

Facepalm. Hard solved 54, medium solved 29.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +77 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +45 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится -10 Проголосовать: не нравится

          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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

  • »
    »
    9 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +44 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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 ?