Ripatti's blog

Codeforces Beta Round #82 (Div. 2)
By Ripatti, 13 years ago, translation, In English

Good evening.

Today's round is mine, as the previous one. This round will be for participants of the second division. Participants of the first division can take part in the round out of competition.

RAD, Connector, it4.kp and MikeMirzayanov helped me to prepare this round. Delinur translated statements into English.

Contest will be in the good old tradition of Codeforces. No any innovations, pretty short and clear statements.

Points for problems are standard: 500-1000-1500-2000-2500.

Good luck everyone!


UPD. Round was ended, ratings was updated.

Winners:

1. tsundere

2. jte

3. abacadaea

4. ltaravilse

5. Billy_Herrington

Editorial.
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (75)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
there are any precision issues like last contest :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
By the way who is Delinur? Isn't he a coder or someone who belongs to CODEFORCES? Moreover i appreciate his/her translations. Thanks for all your great works. :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is rating affected by reading the problem statements? Or only if you try to submit a problem?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Good luck and good ratings to everyone
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I wonder why people gave negative votes to Mehran-r but gives  positive votes to schirevko? I think that there is no difference between those comments at all. 
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I love this contest!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
great contest..good questions (and this time shorter too).Although my ratings wont increase much but i enjoyed the contest.It was fun and a lot of learning.Thanks Ripatti:)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
testing not started yet?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Usually, when you submit a task, and it fails, it does say whether your solution had WA or TL. My submission was hacked, so I tried to find an error in it. Finally, when I resubmitted it, it said TL on hack 1.

It seems inconsistent. If it told be TL with the initial hack message, I would know what to fix straight away... :(
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Great contest! This was my first official contest (since the other one was unrated due to an unusually difficult problem), and I really enjoyed it. It was a good balance of difficulty and coding and thinking.
Can anyone help me with problem E? I know you have to find the minimum enclosing sphere, and that's what I was trying to do, but a lot of other people just seem to be starting at a arbitrary point and stepping towards the correct solution. I was considering this approach, but thought it was too risky, so I'm curious as to what the intended solution is. Since a sphere is uniquely determined by 4 points, the obvious algorithm is O(N^4), but I was wondering if anyone had a faster algorithm. If so, can you please refer it to me? Thanks in advance. (Sorry if this isn't the right place to post this, move this if necessary)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why isn't it possible to see the hacked test case after the contest?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Anyone can explain how to solve problem E?
I had an idea, but I'm not quite sure if it works.
Let C be the optimal point, R be the maximum distance from C to any other point in the input and S be the sphere with center at C and radius R. We have 3 cases:
1 - S has 2 points from the input on its surface in which case C is the center of the line connecting these 2 points.
2 - S has 3 points from the input on its surface in which case C is the center of the circle connecting these 3 points.
3 - S has 4 or more points from the input on its surface and we can determine the center easily given 4 points.
Nice contest BTW, but problems A to D are a bit easier than usual I think.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    That was what I was thinking as well too, but O(N^4) is a little big especially for N=100. 

    The smallest enclosing circle can be found in O(N) time: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm, but I'm not sure how to extend that to 3-d, and what the time complexity would be then too.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Straightforward implementation will be O(N^5). It can be improved to O(N^4), but it's too hard for Div 2 contest.

      I think the intended solution is Hill climbing
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        more details?
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Read accepted solutions. They are very short.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I loved this solution. BTW do you know other problems that can be solved using Hill climbing? Are these solutions very common?
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Many marathon matches in TopCoder require some kind of Hill climbing or Simulated Annealing.

              However, I have never seen it used in any kind of algorithm competition before. I would also be grateful if somebody could give me some more examples of problems with solutions like these.
              → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            How do you choose the numbers though? They seem pretty arbitrary. I looked through some of the div2 submissions that failed, that either timed out because their stepsize was too small, or wrong answer when their stepsize was too big. Thanks.
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              I have the same question with you. My solution is wrong answer at case 10 because of the stepsize is only 100. but when i set it to 500, 700 or even 1000, it is wrong answer just at case 7.
              → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Considering x and y coordinates only, can't we find minimum enclosing circle's centre and then search for required z coordinate because min_z <= z <= max_z,
            min_z = min. z coordinate in given set of points
            max_z = max. z_coordinate in given set of points

            Though, it might be inefficient as answer can be real number instead of integer value.
            → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        I got O(N^5) accepted by loop unrolling (Upd: actually, the final version works faster without it =) ).

        There are quite a few solutions with nested ternary searches accepted, too.
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Actually it seems that problem E can be solved in linear time according to the original paper by Mediggo in 1983 (see here for reference and code library).

      But I doubt this was the expected solution to implement, as it took like more than a century since the smallest enclosing circle problem was posed by Sylvester in 1857 for a linear algorithm to be found ...
      → Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Has anyone thought about using inversion?
    edit: never mind.  I guess I wanted apply a trick in practice like in here, but it doesn't seem to help.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it


      Here is an approach:

      -  Isolate a center point.  Call it C.  Separate it from the others.  We search for a minimum sphere that contains C.

      - Invert with respect to C.  A sphere that contains C is inverted to a plane that does not contain C.  A point inside the sphere is inverted to a point on the other side of the plane.
      In particular, the minimal enclosing sphere is inverted to a plane that is as far as possible from C, and such that all points are on the other side from C.

      - Find the 3d convex hull, in O(N lg(N)), deduce the farthest plane in O(N).

      - Invert again, to get the minimum sphere.
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I didn't perform very well on this contest, but I really liked the problems. Thanks Ripatti :)
From A to D it's quite easy to find a solution, but I wasted the first hour on E (because it seemed to me very similar to this).
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
About my solution for problem D:

http://gyazo.com/0b862656e379b4d4512a513fe884ac36

It seems to be correct, but the checker says this is wrong answer.
I want some explanation about this.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Now I know the problem.

    My program's output contains leading '\0's.

    That was my program's bug :(
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
there was lot of submission for problem E but only a few passed. What is the solution for this prob?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I like all problems except C. To understand this problem required Oxford dictionary...
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The only word that could give you prob is 'stuffing'. Others are just noun :)
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I just understand that a bun is some kind of cake, and stuffing is something to make it (don't even know exactly) :)
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hello , can anybody give me the full 5th test of problem D? in the editor only half of it is seen 
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why the rating didn't get updated yet?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there a way to know the full test case that my solution fail on? When I'm looking at the Judge protocol it shows only n first bytes of the test case.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

8th on the division and only +97?! I have got +176 before for rank 49th and less number of contestants with approximately the same rating! Is there volatility like TopCoder or what?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I feel that when falling to div 2 , it's very hard to return to div 1 because being in top 20 div 2 just add so few rating.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Well they are just updated 
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Another good problemset from ripatti :).
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Are the ratings updated for the "out of competition" participants?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    "out of competition" contestants are really out of competition :) So there are no new rating for them.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
any one can explain what this statement mean in problem "C"
Lavrenty knows that he has ai grams left of the i-th stuffing
thanks
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Lavrenty knows that he has ai grams left of the i-th stuffing. It takes exactly bi grams of stuffing i and ci grams of dough to cook a bun with the i-th stuffing.


    With bi of i-th stuffing (and ci of dough) baker can make a bun. So if he has ai grams, he can make at most ai/bi (integer division) buns with i-th stuffing.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Oh, I had a hard time understanding this, seriously.
      I misread this way:

      Lavrenty knows that he has ai grams of dough left after using the i-th stuffing. It takes exactly bi grams of stuffing i andci grams of dough to cook a bun with the i-th stuffing.

      So I asked a question and the answer was sth like "please read statement" :)
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I read the same thing as you hence I was puzzled for a moment before realizing reading the sentence twice solved my bewilderment.

        I guess the following formulation would have been less prone to misinterpretation : « Lavrenty knows that he possesses ai grams of stuffing i. It takes exaclty ... ».

        But part of solving a problem is understanding its statement =)
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Greetings,

During the contest some fatboy hacked my solution for Treasure Island, the verdict was TLE. But when i see other solutions i see that people are doing simple brute force. Now my question is, the problem says "Walk n miles in the y direction" is the form of instructions and i see that accepted solution just jump directly n miles and dont check all the blocks in between. Isnt this wrong? Tell me.

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Let Up[i][j] will be the maximum free cells Up from (i, j) and Left[i][j] - will be the same for left direction. So, to check is there any block to the North: if (Up[i][j] >= n) that's all, you can jump to the north, having enough free cells for moving.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Let a[i][j]=1 if the cell is blocked and 0 otherwise.
      Then, for example, the way from (x, y) to (x+dx, y) is clear if a[x][y] + ... +  a[x+dx][y] = 0.
      These sums can be precalculated just after reading the matrix and then obtained in O(1) time.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I'm sorry but can the author of this round tell me why my program return the wrong answer on test 12 of the C problem on Div2. I ran it on my computer and it return the correct answer. Sorry because I don't know ask you where :D.
→ Reply
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Unfortunately I missed this round. but when I was solving problems today I wrote exactly same algorithm for Problem D in java and c++, but java got TLE and c++ got Accepted.
Isn't getting a problem accepted, algorithm dependent and language independent?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I believe no, 'cause my java solution got accepted with 420ms as maximal execution time per test. So, if you have good algorithm and realization, u'll pass system tests in majority of cases.
    Here is my source code, if any.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      yeah, you're right, my algorithm wasn't good.
      but my point is if an algorithm isn't good and takes much time, it should get TLE in both java and c++ , not just java.
      otherwise I think it would be good to set Time Limit for java twice long as other languages. like some of other online judges.

      BTW, you used Thread, how much faster is it than using a simple class?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        but my point is if an algorithm isn't good and takes much time, it should get TLE in both java and c++ , not just java.- this is wrong in some cases, e.g. some manipulations with memory, etc.
        otherwise I think it would be good to set Time Limit for java twice long as other languages. like some of other online judges. - This was discussed, and  MikeMirzayanov mentioned this will be done some day.
        Nowadays using Thread's  not much faster than using simple class, it's a kind of tradition)
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I think it's OK that timelimit is same

          1) You can choose C++ and be availabale to shooting your legs or choose Java, get safe, but someproblems with timelimit

          2) adavydow wrote here about example of set big timelimit for ruby:
          > most of string problems solved more easy in Ruby, then in other languages because they are only optimized library function call(writed on C/C++). There are a lot of example of passed O(n^2) ruby solution instead of O(n) C++ ones
          Besides, not-standart algo's in Ruby overwise can be not passed, even with good asymptotics

          So, as I can see it may solve old problems badly and get new problems
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Can you tell me how to contact the administrator of the judge machine? Because I think installing numpy for Python is not a bad idea.
            → Reply