Tigutor's blog

By Tigutor, history, 9 years ago, translation, In English

Hi all!

In two days, at 19:35 MSK Codeforces Round #339 (Div. 1 & Div. 2) will take place. This is an unusual round since we — the problemsetters — are highschool students who participate in the programming training group at high school #179. This round is our first effort and we did our best to make it interesting and bug-free. I invite you all to compete in this round since the problems will be solvable, but even tourist will have to think over some of them. :)

With supervision and control from Mikhail Tikhomirov (Endagorion), the problems were developed by: Egor Chunaev (ch_egor), Vasily Alferov (platypus179), Dmitry Sayutin (cdkrot), Timofey Gutor (Tigutor), Maria Fedorkina (crossopt). Mikhail Sorokin (themikemikovi4) and Sergey Aleikin (Derrior) contributed their problem ideas.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements in English, AlexFetisov and winger for testing, and, of course, MikeMirzayanov for unique CodeForces and Polygon systems.

Round will have standard Codeforces rules, with pretests at first, and final tests afterwards. Take care to account for all possible cases.

Best of luck to everyone!

UPD Points for problems are

Div 2. 500-1000-1750-2250-2250, Div 1. 750-1250-1250-2000-2500

UPD Congratulations winners! standings

Div1:

  1. TankEngineer

  2. KAN

  3. Petr

  4. Um_nik

  5. snuke

  6. matthew99

  7. jcvb

  8. superpear

  9. pashka

  10. fsouza

Div2:

  1. mingaleg

  2. Ronnoc

  3. BoQiR

  4. maks1906

  5. zloyplace35

  6. huansuz1

  7. 2016

  8. Danlark

  9. MrPapaya

  10. bohuss

UPD Editorial

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +152 Vote: I do not like it

Poor english, let's hope the english statements will be better..

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

    Yes, i dont speak english very vell, but lately we'll correct this post. English statements will be created by Delinur, and she know English very well.

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

    Statements were pretty clear, thanks for that!

    problems were also nice and interesting, I really liked C div1 and D div1 :)

    my only complaint is A div1. there was no idea behind it, just a stupid geometry formula.

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

i has very very good expect contest, so many prepared people and i like endagorion contest because they very very good.
best hope much good statements

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

    isn't it rude to make fun of someone who just prepared a contest for you?

»
9 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Yeee, another codeforces round rated. Wishing ratings high to all, hope math problems to see.

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

Google Translate would have done better. :D

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      "we, its drafters — ordinary students, united by the fact that together are engaged in the circle in 179 schools"

      Somebody help, my sides are leaving the orbit

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

      Is this the original post? Hillarious!!!

      because the problem will be solved, but even the tourist-y have to think about some

      I bet touristy will scratch his head for the entire duration of contest, as to why the drafters have given solved problems in a contest :D

»
9 years ago, # |
Rev. 5   Vote: I like it +32 Vote: I do not like it

The statement of problem B in the last round was horrible, i was not able to understand it till the contest ends.

and from the English used in this blog, I think this one will be worse :(

please make sure the problem statement be clear and concise to be fair enough for all contestants.

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

I want to say the Tigutor-у that his knowledge of english is very good.

I'm not only fan of Ilya_MSU but fan of Tigutor too. What tasks have you created except Div1E?

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

    You will see the problems authors in the editorial when it is published :)

    I will keep silence before.

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

    Div 1, F, certainly.

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

How do you know tourist will have to think it over..?

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

»
9 years ago, # |
  Vote: I like it -20 Vote: I do not like it

It's really inspiring to me that someone with less rating than me could hold an CF contest. Thanks!

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

    I'm so sure in Tigutor that I'm going to cut my balls off if he won't be red in a month. Just like Ilya_MSU

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

      I'll remind You to do so. ;)

      I'm waiting for next month.

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

        S/He seems careless! Maybe s/he is the girlfriend of IlyaMSU?

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

          I'd like to but I'm not. :(

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

      Username relevant.

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

      I don't want to underestimate from anyone but he has Registered 18 months ago and the maximum rate he can get 1514 and now you say that he will be red in a month do you actually think so

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

        Thanks a lot for your research

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

          research!! it just a click on his handle

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

I enjoy contests by lower rating writers. They usually contain interesting problems that involves creative thinking.

»
9 years ago, # |
  Vote: I like it -23 Vote: I do not like it

I think there are at least 3 problem eassy in CF round 339.

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

    No buddy. All problems are solvable by you if you are coder like Tourist :)

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

      why you must compare with tourist... you must do better and you must solve problems even tourist cant... you must make it solvable.

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

        It is quite impossible for him . I know him very closly

»
9 years ago, # |
Rev. 2   Vote: I like it -52 Vote: I do not like it
Your code here...
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

A contest prepared by so many people is my worst nightmare. Hope for the best though.

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

I'm new here, could you tell me if there's a difference between Div. 1 and Div. 2? Thanks

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

    Hello, Div 1 is more difficult and is generally for contestants with a rating >=1900. On the other hand, Div 2 is easier and for less experienced competitors.

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

    When the contesters take part in Codeforces contest, they raise or lower their rating that reflects their ability to solve the tasks. The rating is a modification of Elo rating, several details can be read in a fuller form. According to the rating, the contestants are split into two divisions: the second one (the weaker one, amateurs) and the first one (the stronger one, pros). The contestants who don't take part in contests and those whose rating is below 1900 belong to the second division. The 1900+ rating means that you're part of the first division. Usually two types of contests are held on Codeforces: for the second division contestants (the first division contestants can take part there out of competition) and for both divisions. The first contest type contains simpler and learning-oriented tasks.

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

    What is your div1 account?

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

    Difference between Div. 1 and Div. 2

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

To be honest I don't think the English is poor...quite clear for me...

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

    they edited it, the last version was a bit funny but if you tried your best you could understand what it meant

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

      yes!

      Initial revision is really funny!

      Look, like this one : << I invite all of you write this round >>.!!

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

BTW,you're good-looking:D[user:Tigutor]

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

    Aren't you male?

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

      Yes...But it doesn't matter to praise him...

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

      He is a she. No guy praises another guy for looks bro, unless gay.

      Otherwise, chinese names gender neutral. I know a girl who has same name as her.

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

        it's quite normal for us to praise other's looking no matter what the gender you are,if you like.

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Alright, I accept that. But YOU are a girl, unless, your name is gender neutral and you are gay(which is cool, btw) :)

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

            but you're wrong.maybe there's something different between our culture.anyway,stop talking about this.

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

»
9 years ago, # |
  Vote: I like it -49 Vote: I do not like it

哇塞高中生出题好厉害也!

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

I hope tourist takes part in this round and talk about the difficulty

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

Does the scoring mean that the difficulty of div2 D & div2 E is the same?!

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

    It's difficult to say. For decent div1 coders it may be same. For good div2 coders it may not.

»
9 years ago, # |
  Vote: I like it -69 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

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

Can someone plz explain the second testcase in DIV-2 1000 points....

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

If i get WA in pretest then also 50 points will be deducted?

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

    yes, but if you don't AC that problem , there will be no decrease on your total score.

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

      this is what Codeforces says : "there is 50 points penalty for submission which fails the pretests or resubmission (except failure on the first test, denial of judgement or similar verdicts). "

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

I'm becoming newbie today n:). So happy to achieve this feat. Feeling gratefull. after being hacked 3 times. :)

»
9 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Well. That could've gone better.

But dat number of pretests... I really hope not to fail systests now :D

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

Let the hate begin!

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

Will the tests which lead to successful hacks be used for system testing?

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

Do we need convex hull in div2C or we can find the smallest radius without it?

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

    Min from distances to all edges.

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

    No, because points are given clockwise or anticlockwise direction.

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

    Look at the second test

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

    You just need to find the point on the polygon closest to P and the one farthest away, the one closest to it is going to be on one of the edges ( so check each edge), the one farthest away is going to be one of the vertices ( so check each vertex )

    Let MAX be the largest distance to P and MIN be the shortest distance to p. Then the aswer is (MAX*MAX-MIN*MIN)*PI.

    No convex hull required.

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

      the one closest to it is going to be on one of the edges

      wrong.

      Consider the segment with end points -1,2 and 1,2. The minimumis at point 0,1.

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        read more careful, 0,1 is on the edge

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

      I tried something similar , but I was checking for min distance on vertex too. Can you clarify a bit more why the one closest is going to be on one of the edges?

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

        It could be that the point which is closest to p is an endpoint of some line segment. In general, for a given line segment if the projection of p lies on that line segment then that's the closest point to p on that segment. If not, then the point which is closest to p is going to end up being one of the endpoints of that segment.

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

    I think we just need to find the point of intersection of each side with normal from origin to that side. If it lies within that segment, then that point is to be used to find minimum radius, otherwise, the smaller distance to origin from the 2 end points of the segment are to be taken as candidates for minimum.

    Waiting for editorial.

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

      edge is not the same thing as vertex. The one farthest away is a vertex, the one closest is ON an edge.

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

    we can do it without convex hull also. to find shortest distance of each line segment from center first find distance of both points from center and then check if the line having slope equal to the perpendicular of this lines egment and passing through center intersects the line segment or not. if yes, calculate intersection point as well as its distance from centre. take minimum of all calculated distances.this is the smallest radius.

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

I don't think Div1 B and C worth the same score. T^T

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

What's the idea behind Div2 Problem C pretest 3?

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

    I tried a naive solution by finding nearest and farthest radial points of the polygon. Guess there is more to it. This approach works for the illustrations

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

    I suppose something like:

    3 0 0
    -1 1
    1 1
    0 2
    
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

     I think this

»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Div2 B time limit was a bit too strict I thought

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

    Dont use python or biginteger.

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

    No! You must check if the given number is beautiful (reading it as a string). If it isn't beautiful, save it for the final step. For each beautiful number, you have (lenght-1) zeros. So, if the number is only composed by one "1", and this one must be at the first position (because the restrictions), you don't need to do estrictly a "product", because most of them are one "1" and a bunch of "0". You need to save the sum of total zeros of beautiful numbers called "zSum". So, if the non-beautiful number is zero, the answer is zero. Else, the answer is a string composed by the non-beautiful number (remember to read it as a string, because the lenght can be 100000 as maximum) and then "zSum" zeros. I took me a few submissions before figure it out.

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

      Yes, my java submission counts number of zeros and appends a 1 or the non-beautiful number at the front. In java, it TL-ed on test 8, but in c++ it did not. Minor optimizations could drastically change the verdict for this problem. That is why I think this TL was too strict(I wonder how hard it was to pass for python users...)

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

The test case 1 900000000000000000 12345678, helped me earn 1800 points in the contest by hacking the first problem of almost every user in my room. My best ranking ever, thanks to hacks.

Actually python rocks for this question.

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

    Whats the correct answer?

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

      1 12345678 152415765279684, is the correct answer

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

        I think 1 12345678 152415765279684 108064748184340920 is the correct answer

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

          I think with C++, something like taking logs should have been used. Damn so much overflow :\

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

            The only you need is to check whether if LONG_LONG_MAX/n<k you need to brake a cycle, where n is current power of k.

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

        My solution with unsigned long long int fails :\ Another -1 so

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

        FFFFFFFFFUUUUUUUUUUUUUUUUU----------------

        Arithmetic overflow is such a bitch....

        It gets me every time...

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    deleted

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

Div2B pretest 9? how?

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

    This one checked if your program could answer correctly the case where all numbers were beautiful

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      What?? There's always 1 non beautiful number..

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        at least n - 1 beautiful numbers

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

        some number of tanks of one country was removed from the game, hence the number of tanks of this country may not remain beautiful.

        may may may may

        it just guarantees for atleast n-1 beautiful numbers. never for atleast 1 non beautiful no

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

        There is always one number subtracted from, but it might remain a beautiful number. Confusing, I know :P

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

      And here i was thinking i can hack some submissions because of this. -_-

»
9 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

There could be a lot of hacks on problem A if not third pretest(

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

    There could be a lot of hacks on every problem if not these good pretests :)

    I think it was a bit cruel — to give samples which can be solved with "point-point" distance, without "point-segment". And at the same time there was no crazy hack fun...

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

      I figured out the point-segment thing with concave polygons after failing the 3rd pretest, but didn't have time to code it all...

      Effing geometry.

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

I remember some people were joking about the difficulty of the problems before the contest... Anything to say? :P

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

Can anyone explain Div 2 C? My idea was to find the minimum distance from P to the polygon and the maximum distance and then pi*(max*max-min*min)

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

    I don't know correct solution, but yours fails at this test:

    4 0 0
    -1 -1
    0 2
    1 -1
    0 1

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

      My idea was exactly similar to this comment Now I'm confused

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

      You're wrong. The minimum distance doesn't have to be the distance from P to one of the point in the polygon.For example, for the test: 3 0 0 0 2 -1 1 1 1 The minimum distance is 1 while not sqrt(2).

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

    Minimum distance doesn't always lie on vertices.

    eg 3 2 -1

    1 0

    2 1

    3 0

    ans = pi*(4-1) = 3*pi.

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

      I handled that issue

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

        Then maybe you didn't handle the finite line issue.

        The min point must lie on the finite line segment.

        If you just considered perpendicular distance from point p to line then you might fail some cases.

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

        I also handled the issue and failed test 3 : maybe you forgot the edge between the first and last vertex.

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

          Maybe your solution to find the minimum distance from a point to a segment has some bugs.

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

            No I just added the last edge and it passed all tests :)

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

I think this round is too difficult ....

»
9 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

What is the intended approach for div 1 D?

The same question for a single query can be solved using dp on trees in linear time which led to me to come up with an approach which involved using HLD to compute dp at the bare minimum required nodes (klogk for each query I think) but the implementation was turning out to be too long so I went off to sleep instead.

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

    You can first build the auxillary tree, which is a compressed tree of the marked nodes in O(klogN) time consisting of O(k) nodes and then apply the same dp on this tree in O(k). For implementation details on how to build the auxillary tree, refer my soln here

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

Div2 A should've been named Hack those overflows.

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

My WA solution for div2 C was to compute minimum and maximum radius, find difference between circles and output. I specially handled the case in which all radii were the same(answer =0)

I claim that any radius between [minradius,maxradius] can be attained by some point in the polygon. Is this false?

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

Thanks for great div2A! 22 successful hacks are non penis canina. My hacks:

1 1000000000000000000 1000000000
1 1000000000000000000 536870912
1 1000000000000000000 536870913

536870912 = 2 ^ 29

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

    Very good!

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

    second test case can be used to hack unsigned right , awesome

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

      Yep, and the third one is the test, which generates overflowed long long less than 10^18 and greater than previous one.

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        In first redaction 1 ≤ k ≤ 109 but we thought that it is big trap for Div2A.

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

    Can you describe how do you find second and third tests?

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

Thank you for strong pretest for B!

»
9 years ago, # |
Rev. 2   Vote: I like it -32 Vote: I do not like it

I hate Div. 1 A. No interesting idea, just applying mathematical formulas and crying when wrong answer on pretest #3 shows up and then finding a typo in one of these formulas :'(

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

    I agree div1A doesn't find its place in any contest it's a stupid problem.

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

      But we struggled with it. It was for us.

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

      I think this problem fits well in some ICPC-style contest. However, CF round is not ICPC :)

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

        I don't understand what you all are talking about. I see the only problem with it: some guys could use prewritten geometry and get accepted a little faster (several minutes). I haven't used it.

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

      It is the great problem to have a lot of hacks/challenges :)

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

        I don't think it is a good idea to have an ugly problem for the sole purpose of allowing people to hack more

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

      I just used the ternary search for each side of polygon

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

        same here but got TLE on test 37 :(

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

        Same here, but could not get AC during contest. Missed the line segment between 1st and last point :(. Code Link

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

      I don't get it. Why your comment gets +28 while mine gets -32? Is there something wrong with my comment which doesn't meet Codeforces standards?

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

    By mathematical formulas you mean distance between points and distance between point and line? They are well known and quite easy. Actually, geometry problems are quite rare on codeforces, so it's good to have them sometimes.

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

      'Well known' — yes. Quite easy? Well... (between points ok, that's easy, but I didn't remember the formula for the distance between a point and a line and I had to deduce it by myself)

      Also there surely are many much better geometry problems than that.

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

        We have this formula on the lesson in 8 form: abs(a*x0+b*y0+c)/sqrt(a^2+b^2) x0, y0 — point's coordinates

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

    There is an interesting, simple idea. However, there's also annoying geometry. If P was inside the polygon, though, it could've made an easy div1A without the annoying stuff.

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

Any One Please tell me that is What is "Hacked".

After my submission I received a message that solution is hacked...

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This means another contestant has found a case when your program produce wrong output. In short, your solution is wrong.

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It means someone found bug in your solution and found test in which your code fails. So, your solution incorrect and you should find bug and resend solution.

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

Thank you for preparing such a contest like this!Although I don't pass Div.2 C,this contest is well! Thanks everyone!

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

At this time tourist

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

What is test case 9 in div2B?

»
9 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

The only problem I liked from this set was Div1 D :(

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

    Seriously? My code started working after the contest (on pretests) and it's 300 lines. I don't like it. Idea is simple: there is a stupid algorithm with time O(n+k). How to fit the queries? Just compress the graph to make it O(k) vertices. Or do you have another solution?

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

      I liked the problem D too.

      My solution is slightly above 100 lines; the idea is to compute the answer in offline and to use maps with small-to-big optimization.

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

        And I just processed 64 queries at once using bitmasks :)

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

      My solution is heavily based on LCA. We sort vertices from the query in the Euler order (it's computed in one of LCA implementations anyway). Then it's optimal to take consecutive vertices whose LCA has the largest depth and disconnect them by deleting their LCA. If LCA is also a selected vertex, we need to delete some of its children, also -1 case is handled here. The only difficulty is how to implement this idea in the best way, but anyhow it should be O((N + K)logN).

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

    What about div. 1 C? I know you enjoy palindromes :)

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

Any idea in DIV2E/DIV1C?
There are no DP, right? Just only some tricky but easy-to-implement construction? :)

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

    If we have two letters with odd ai then the answer is 0. Otherwise the answer is g = gcd(ai).

    Let's build such string:

    1) If all ai is even then we can build a block of length with occurrences of the i-th letter (in any order). And then copy that block g - 1 times, each time reversing it. Easy to see that we will have exactly g palindromes (because g is even).

    2) If we have some odd ai then g is odd. So for each even ai the value is also even. So we can build g identical palindrome blocks of the length , where the letter with odd ai will be in the middle and all the letters will occur times.

    It's not hard to prove that the answer can't be greater than g.

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

I don't like Div2B statement — take too much time to figure out that numbers could be very long etc etc. One of these tasks where statement reading takes the same (or more) time as solution finding and coding.

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

Authors at this moment...
system testing

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

    We're sorry, because The Great Admin now in taxi and hurry to start system testing)

»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

When I read the problem statement of Div2.B at first, I could not understand.
By repeating to read the statement many times, I noticed that "find the product" stands for calculating , and then I could solve immediately.
By and large, the accounts for sample case are too short for me.

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

Div1A is really great for Educational Round. Authors would do better by PM'ing Edvard with this task. I know that it's wrong, but I was badly confused about this right from the start of the contest.

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

    Did you participate in Education Rounds with geometry problems? In the first one, half of solutions were hacked due to precision problems. In the second one, even the author solution had precision problems and they had to increase the error tolerance 1000 times. I think it is not a coincidence that there are no geometry problems in the last 3 Education Rounds. Too much work to get them right when your adversaries have 24 hours to find challenging cases. Unless you want to restrict coordinates to be less than 100 and set required precision to 1e-2.

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

Its very funny that participants who have 26 successful hacks on A failed A on system testing :)

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

    Anyway, they earned a lot of hacking score (besides they didn't solve the A)

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

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

Super Contest, I got a lot of fun!!!!!!

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

Look there, running code: here

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

Why system testing stuck at 100% ?

»
9 years ago, # |
Rev. 2   Vote: I like it -25 Vote: I do not like it

Thanks to authors! : )

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

Endagorion tomorrow published editorial, please wait...

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

div2 D. Skills what's the answer of 3 5 1 0 4 0 4 1

»
9 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Another test case for Div. 2 A:

9007199515875289 9007199515875289 94906267
»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My code working fine on my machine but failed system test for the same code. Working fine on custom invocation also.

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

    I'm sorry to say there's no way that code's "working fine". You're getting an overflow error, checking that it doesn't become smaller isn't enough, as it can overflow into a bigger number.

    For instance, consider numbers modulo 40, k = 4. The powers are 4, 16, 24. 24 is clearly wrong, but it's still higher than 16. Your code won't detect this kind of error.

    What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right.

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

Don't know why it failed system test ? code

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

Ratings Updated!

»
9 years ago, # |
  Vote: I like it -22 Vote: I do not like it

the worst contest I see in codeforces problem B was unclear

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

    Can't agree with "worst", was quite well overall.

    But Div2B is bad, I agree with that. Statement is over-complicated a lot.

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

      As for me it was one of the best problems during last several rounds because it is the one i have just solved and only thanks to it i have become a "specialist") And it is the one you haven't solved (from what you have tried to solve), i know(

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

        Congrats :)

        Yea I've failed on that one — algo was correct, but I didn't checked all branches correctness. My failing case was where non-beautiful number comes before 0 in sequence, so I printed "nonbeautifulnumber0" instead of "0". After self-analysis I blame my bad emotions about problem statement — because of them I wasn't very concentrated when checking.

        Besides that, its very easy problem. ProblemStatementComplexity > ProblemComplexity. I really hate these ones (and my hate is what caused these bad emotions) :)

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

That moment when you realize you failed test 3 on Div2 C because you forgot the edge between the first vertex and the last one...

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

Div. 2 D is interesting except for asking the final value of the numbers, that adds nothing but boring and time consuming implementation.

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

    I was thinking about and decided that it doesn't add a lot of code, and has some advantages.

    Firstly, you can check participant's answer more precisely.

    Secondly, you could detect [potential] situation when participant's solution is better than jury's one and report.

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

      It's true a lot of lines of code aren't added but the logic behind them takes a lot of time to think and debug properly. It costed me 15 minutes to code it on top of the 30 minutes used to find the best value.

      Indeed, but I still think the problem is already good without them, maybe just asking the minimun value and the number of maximum values used is enough.

      That's not a job for contestants.

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

        2) Yes, but first reason still applies =)

        What about your idea to output a number of full skills and the minimum level I think it is too spoilerish, because allows to guess that the maximums can be taken greedily.

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

Can anybody please help me where my div2 A problem is getting wrong. ?

Code link — http://ideone.com/EzXlNf

Input case : 1 999999999999999999 1000000000

My output : 1 1000000000 1000000000000000000

Correct output : 1 1000000000

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

    You are using doubles for l and r, doubles have precision problems. It's probably representing 1000000000000000000 and 999999999999999999 as the same number.

    You should store l and r in long long and use doubles to check possible overflow.

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

Was long intended to fail the tests (Test 24) in Div 2 A in JAVA ? I changed my code to BigInteger and it passed.

I'm sure a lot of people used the method I did. All I did was preprocess the powers, store them in a TreeSet and print subSet(l, r+1) (which is an inbuilt method in JAVA TreeSet (similar to C++ std::set)) which prints all the elements in the range [l,r]. You can do this by adding it to a vector, then sorting etc, same thing.

I don't think these solutions should have failed. This is just my opinion. Here is the WA code and AC code.
Only changed Long to BigInteger, nothing else

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

    You need to be clever if you use 64 bit ints (java long) in order to avoid overflow errors. Echoing a similar answer I already gave:

    Checking that the numbers are in the correct range isn't enough, as they can overflow and land in the range again. For instance, consider numbers modulo 40, k = 4, and [l,r] = [3,25]. The powers are 4, 16, 24, etc. Since the third number should be 64, 24 is clearly wrong, but it's still in the [l,r] range so your program will print it out.

    What you could do is checking whether the division is sane: check that the next number divides the previous into k. That is, if pow[i] / pow[i-1] = k, then you know it's right and you don't have overflow errors.

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

    This problem basically asks you to properly handle the overflow. If there exists an input which make your code fail, then your code should fail (no excuse).

    You can deal with overflow problem without having to rely on BigInteger.

    From your code, you only need to add one line before start *= k;

    if ( start * k > LIMIT ) break;  // check overflow (LIMIT can be 10^18, or you can use 'r')
    start *= k;
    

    But wait, start * k can be overflow, can't it? Yes, so change it to this:

    if ( start  > LIMIT / k ) break;
    start *= k;
    

    You don't need BigInteger at all.

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

(http://imgur.com/JckabmD) Why is my output wrong?

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

Got WA in problem a, initially I was using long double, and I lost a lot of time because apparently codeforces wont work correctly with %Lf. So I switched to double, then I got WA because I needed long double precision. What was the point of div2 a? To get me not to use c++?

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

Oh, I didn't know that Decimal in Python is so slow. TL56 on Div2 C :( And the same solution with the usual Float is correct.

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

    Its not "decimal in python", its "python" itself who is slow :)

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

      It is ok for the problems like Div2 A-C. I just mustn't be too greedy for precision in 2C=1A.

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

        Well yea, I was using it before. But then I've failed to implement some solutions because it was 40 times slower than C#. So I've decided to switch.

        And I believe two active languages is a bad idea for competitive — it is better to master one (there is a lot of cases to study, like overflows, reading 1e9 test inputs, etc etc).

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

    On the bright side you got to hack my botched handling of vertical lines.

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

Div2 problem A, good example how useful Biginteger can be.

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

    BigInteger Will get TL, Muhaha.

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Not sure about C++, but in C# we have "decimal" type which can store up to 28-29 digits (basically it is int128 with "floating point position").

    I also have another somewhere interesting solution for C#:

    Do all the math on regular long type (int64) inside the "checked { }" block which force compiler to check all math operations for overflow. If got an exception -> break cycle.

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

      Cool solution!

      Also, there's BigInteger in C# (in System.Numerics), which is also fast (in such small case).

      To Java Users : ...... and easier to write. 15385528

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

      I think It's fair to say that decimal can be used more like int97 or unsigned int96 rather than int128. Because mantissa is only 96 bits plus 1 sign bit.

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

Typical GNU C++:

pair<int, int> s = pair<long double, long double> (13.3, 14.4);
cerr << s.first << ' ' << s.second << endl;

No warnings.

if (rand() % 10 < a.size()) puts("0");

naive.cpp: In function ‘int main()’: naive.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (rand() % 10 < a.size()) puts("0");

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

    Sad but logical.

    With floating point types being silently and implicitly converted to integers all the way in the history of C/C++, it is only logical to extend this property to simple aggregate types as well. So, no warning, as in int x = 4.59;.

    Regarding rand() % 10, there is no way to tell that the result of int rand() is actually non-negative, except if we go and analyze the source of function rand(). In the general case, it would be impossible for a compiler to do (with halting problem as a subproblem). Why rand() returns int and not unsigned is however a good question — why, indeed?

    And the problem the compiler warns about gets quite real with if (rand() % 10 - 10 < a.size()) when the part rand() % 10 - 10 is converted to unsigned (~4 billion) before comparison takes place.

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

      I don't understand why this get warning:

      int ans2 = (long double) (10 + rand());
      cerr << ans << endl;
      

      naive.cpp: In function ‘int main()’: naive.cpp:85:38: warning: conversion to ‘int’ from ‘long double’ may alter its value [-Wconversion] int ans = (long double) (10 + rand());

      but conversion for pair<long double, long double> don't. My solution for A fails today because of that.

      And about comparing of signed and unsigned values. Why it can't compare them in the following way: if signed value is negative then we know answer, otherwise compare them in unsigned type?

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

        Oh, there's -Wconversion which is not covered by -Wall or -Wextra. Didn't remember that, sorry!

        Now that's actually strange. In my hand-rolled implementation of pair <T1, T2> (version 1, version 2), such usage does trigger a warning with -Wconversion right where it should. Perhaps the library authors do something more clever, or, theoretically, not detecting the warning in the library code might be a compiler bug.

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

        Regarding comparison of signed to unsigned, that would be a really clever move if there was a processor instruction to do exactly that. Looks like that's not the case, and the alternative is to issue a branch instruction, which may be an expensive operation on a modern PC. And C/C++ compilers usually produce efficient (while not necessarily intended) code by default.

        Also, legacy software may depend on the current documented behavior.

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

Not knowing how to know when overflow will occur in power costed me getting to expert. Oh well, atleast I learnt something today. :)

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

Can someone tell me which edge case did I miss for DIV2B ? http://mirror.codeforces.com/contest/614/submission/15367847

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    It seems your code fails for such a non-beautiful number:

    100005

    Its start from '1' AND have zeroes. So you count these zeroes towards the final answer, but also printing the number as it is. So 4 more zeroes than necessary.

»
9 years ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

Picture removed.

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

    Please don't take it personally but honestly speaking I don't like this picture. A national flag is the symbol of independence and sovereignty of a country. Inappropriate uses of a national flag is not appreciable. May be you didn't do it purposely. But you should know that we can't disrespect our country by using our national flag inappropriately. As a Bangladeshi, my request is please remove this picture. It hurts my feelings. I don't want to see a big hole and some stripes on our flag.

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

    I'm not sure with the question, but I guess, the answer is yes.

    I also fell for the notorious test case #3. My solution was: find the furthest and closest point among the N given points to P. Apparently the "among the N given points" part is wrong. The closest point is not necessarily one of the N points.

    consider this case: 3 0 0 -1 1 1 1 0 2

    The closest point is (0, 1) which is not among the 3 points in input.

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

So where is the tutorial ?

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

can anyone tell me what is the logic behind div2 B ?

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

    The beautiful number are in the form of 1, 10, 100, 1000, 10000, ..., and there is at most one non beautiful number. So you only need to print the non-beautiful number, followed by as many zeroes as there can be. However, you should be careful with the case where there is zero or no non-beautiful number.

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

WOW!!! We have 9 Legendary grandmaster now!!! :D

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

    There were only 5 after the rating changes if I remember correctly. I wonder what happened, wasn't the new system supposed to counter rank inflation?

»
9 years ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

I passed the pretest of problem D with a little issue, and I skipped my old solution and lost 145 points when I found the issue. But when I submitted my old solution today I just surprisingly found it pass the system test.

Your text to link here...

This is the correct one. Just press "compare" to view the old code and the obvious issue.

»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

It seems that the contest will be with no Editorial :(

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

NICE

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

That moment when you realise that E is solvable faster than all other problems (except A). :(

Just because there's no different cases and the most complex operation is modular plus.

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

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

hello, have a question: is double on the system a single-precision float? because i believe my solution of the problem C of DIV-2 was correct and on my computer i had correct outputs and apparently on the system it has output different answers.

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

    No. I don't know any system where double has a single precision.

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

    Use %lld to read numbers.

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

I think problem A is one of the most Hacked problems on Codeforces.

I hacked 11 and an other 15 solutions failed system test .

every one will know how to handle overflow after this contest :D .

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

just another way to describe div-2 A

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

    how did you do in the contest? I am surprised that you found time. Syllabus finished?

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

I am getting wrong answer on Case 56 for Div2 C . i used ternary search.. Can someone please help ???

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if( abs(x2-x1) < 10e-10 )
    

    I feel vertical lines you don't like.

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

There wont be any editorial for this round?!

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

How to solve problem C from Div.2? I assumed that it is necessary to subtract the area of the minimum of the maximum circumference. But it is not so. Thanks

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

    Yes we need to find the area between the farthest point as radius and the nearest point as radius. farthest point is just the vertex at maximum distance from P , but the nearest point can be a vertex or an edge . So just find the distance between each edge and P and take minimum.

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

      But it wont work for the second sample test case. In that case you can see there is a traigular segment with its base towards the pivot. The distance between the line and the pivot is 1. If I use the above approach the answer would be 9*PI — 1*PI but the answer is clearly 9*PI — 2*PI.

      I am still unable to get the approach for this problem and waiting for the editorials eagerly.

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

        It works all right ! :D .

        In the second sample case farthest point is clearly (1,2) and when you compare distances between every edge and P , You will get the minimum distance with either point (0,0) or (2,0) . I'm not sure what's confusing you !

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

          but when you consider the edge joining (0,0) and (2,0) the distance between that edge and the pivot is 1 which is smaller than sqrt(2) which is the distance with point(0,0) or (2,0).

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

            There is no edge between (0,0) and (2,0). edges are given in clockwise or anticlockwise direction. You are mis-understanding the question. Read it again carefully.

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

How to solve Div2 D ?

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

How to hack a c++ solution that use the defined pow() function ?

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

Waiting for editorial~~~

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

Still no editorial?

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

Many people don`t know English very well. And I also. But we are gathered here to develop our skills in programming!

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

Auto comment: topic has been updated by Tigutor (previous revision, new revision, compare).