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

Автор RetiredAmrMahmoud, 9 лет назад, По-английски

Hello Codeforces!

I'd like to invite you to Codeforces Round #287 (Div. 2). It'll be held on Friday, January 23rd at 19:00 MSK. and as usual Div. 1 participants can join out of competition.

This is my first round so wish me luck! :)

Great thanks to Maxim Akhmedov (Zlobober) for helping me preparing the contest, Alex Fetisov (AlexFetisov) for testing and giving useful tips regarding statements, Maria Belova (Delinur) for translating the statements into Russian and Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform.

The scoring distribution will be announced later.

Good luck everyone and I hope you'll find the problems interesting.

UPD #1 Score distribution will be standard 500-1000-1500-2000-2500.

UPD #2 Contest finished, hope you enjoyed the problems. :)

UPD #3 System testing finished.

Winner of the contest is going to be disqualified due to "Do not use harsh, rude or misleading handle." part of Codeforces rules.

So congratulations to the winners:

chickennethsnow

qcrqgx175

mikeyue_tc

Dennord

KilluaZoldyck

UPD #4 You can find the editorial here.

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

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

Hello Egyptian contests :D

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

orzzz... Hoping to see problems without too hard data structures

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

    Masters/candidate masters are the best setters for only div 2 round.They can't invent a lot of hard problems,but if the effort problems are very interesting and solvable for two hours.

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

I hope this won't be dynamic scoring in this contest...

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

I hope this Egyptian contest wouldn't be so "interesting" such as previous one from Japan :D

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

sure you'll make a good contest my friend :D

hope the you make the next contest as a grand master :D

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

well , i didn't see that coming :D

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

I'm new here, What should I do to register? I can't see the option?

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

    Registration begins in 13 hours from now :)

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

      Thant was not really helpful :-/

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

        As a reaction to "I can't see the option"? He already knows registration is necessary, but is asking how it's done. The answer of "it can't be done yet" is perfectly valid.

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

          So probably I misunderstood the question. I assumed he knows he has to register, for example because of other competitions like TC, where registration is needed... If he knew, where to register (contest list page), he would see the countdown, so I wanted to navigate him to the page...

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

    You have to register.

    On this page will be the link to register — http://codeforces.com/contests ;-)

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

"The scoring distribution will be announced later."

So mainstream)

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

the contest is first rate to me

i hope to be good :D :D

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

All the best for this round ~

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

Is this the 1st Egyptian contest on Codeforces ?

That's awesome =D

I hope to see interesting problems =D

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

how to register for this contest? It is the first time for me to take part in the codeforces contest.

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

Finally an Egyptian contest ! That's awesome *_* :D

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

an Egyptian contest with Egyptian problems! :D

It will be a good contest I think.

Good luck ^_^

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

This is my first contest on Code-forces. I hope everyone will help in this platform.

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

upvote pls!

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

It will be attractive if all problems be about Pyramids...

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

My first contest in here, not sure how it works, but we will see :) Quite a lot of registrants so far, so it looks like to be a good contest. Looking forward to puzzles. GL&HF to all

»
9 лет назад, # |
  Проголосовать: нравится +92 Проголосовать: не нравится
 your                                               eyes 
 are                                                moving 
 from                                               left 
 to                                                 right 
 and                                                then 
 from                                               right 
 to                                                 left 
 again                                              and 
 again                                              to 
 read                                               this 
 comment. 
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

That's the first contest I cannot compete (DIV2 only), but I found that I can register as "out-of-competition" contestant. I can hardly believe, that some DIV1 guys, are creating new account, just to beat DIV2 contestants (of course except the case of dreamoon_love_AA in contest #284).

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

Good luck everyone!

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

You can use this tag :

"1 hour for system testing "

or this tag:

"dynamic scoring"

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

Where is the scoring distribution? :)

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

Thank God!! No Dynamic Scoring Gl & Hf!!

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

лишь остаток после деления результата на номер m.

Какой еще "номер"? Даже Google Translate переводит как "число".

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

i was using 1<<h and got wrong ans in pretest in C question and when used pow(2,h) got correct ans why ??? because of this i couldn't attempt more question in this contest..

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

What are the answers for following cases for Problem B:

100 0 0 0 1

1 0 0 0 1

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

      How? We can use the pin only on the circumference of circle, right?

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

        You can show that by putting the pin appropriately even on the circumference of the circle, you can always move the center of the circle by any distance not greater than 2r in one move.

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

    my answer is 1 for both cases.

    You can move center of circle to any point with distance to it not greater than 2R. Why? Let's consider a line segment between an old point and a new one. Now draw a segment bisector and put a pin in any intersection of an old circle and this bisector.

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

How to solve D? Is it DP? If yes, can you say me what is 6th case?

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

How to solve B? I solved everything but this f***ing geometry :(

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

    Calculate distance between two points, divide the distance by diameter and output ceil of it. :D

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

      Consider the test case: 4 0 0 1 0. How to do it in 1 move?

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

        The furthest point on the circle to 1,0 is -4,0, and the closest point is 4,0. By the intermediate value theorem, there exists a point that is equidistant from 0,0 and 1,0 on the circle. Using this point as a pivot works.

        EDIT: Fixed error in points

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

        I asked the same variant here

        Answer is 1. I tried to hack 3 solutions[All unsuccessful] using this case. Author's answer is 1 for such case. I dont know how :/

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

    I'm not sure if my solution is correct but for me the solution was: ceil(dist(center1,center2)/(2*radius))

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

Round #287 (Div. 2 Only): 3298 participants

Round #286 (Both divisions): 2600 participants (572 + 2028)

It seems that harder problems might lead to fewer participants, an important lesson we learned :/

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

    my personal opinion,your problems were more fun and challenging than todays contest ,,plus i really liked the editorial :D

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

    How did you count the "participants"? I guess you use the number of people who made a submission. Then that's reasonable your contest have few participants: Petr said he don't know how to solve any problem after read them, so it will be sure lots of people read Div1-A and don't know how to solve, then they will not make a submission.

    And another reason is that the difference of start time: your round start at an unusual time.

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

      My definition of "participants" is the people whose handle are on the official standings, so yes, that would be same as the people who made at least one submission. I think the current system of Codeforces which allows participants to "run away" from contests when the problems are not so convenient for them is not very fair, especially in these cases.

      The time of the round was probably a larger factor, though, since Div.2 A and B were not too hard for those slots (at least in my opinion), and Div.2 has a larger population.

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

    You need at least one easy problem in a problemset, otherwise there are lot of participants who just can't solve at least one problem.

    I know 3 guys, each of them with rating 1800+ (and one even with 1900+), each of them registered for previous round and spend at least an hour trying to solve something.

    But none of them is included in your stats, because they didn't submitted anything.

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

      Yes, we also know more than one Japanese who were motivated to participate but "failed" to do so because of harder Div.1 A. It seems that the problem in this slot should be easy to code some solution that can at least pass the samples, if the rules (which allow "retreat") remain unchanged.

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

        Right, even if it will be not so easy to write corect solution, but general idea will be obvious — number of participants will be bigger.

        Something like this problem comes into my mind... Just take a look at standings of that contest :)

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

В последние минуты пытался взломать Д. Приходил непонятный вердикт типа "отказ". с 3 раза взломалось, а те 2 взлома превратились в "игнорирован".

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

не нравится мне это в положении

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

Wow, I was stuck on D for so long with thinking that anything ending in 0 was bad since y=0. I could always make my code pass either the second or third case, but not both. After debugging for like an hour, I saw y!=0, and fixed it (badly) and found my new mistake with like 30 seconds left.

Kudos to the problemsetter for adding a case where if you forget both that 10000 works and that 01230 doesn't work you still get the same answer :P

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

Does the following approach solve D?

since k <= 100, we at most care about the 2 last digits in the suffix. so for numbers up to 100, check that the number is a multiple of k, if so then we can extend this suffix just by padding digits and making sure that the first digit is not equal to 0.

I tried it but could not implement it correctly. Also, we should not count twice: say if 12 divides k and 2 divides k, when we extend 2, it will look lik xxxxxx2 but some of these will look like xxxxx12 and those are counted already in extended suffixes of 12.

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

    Your assumption is wrong. Try with K=39 and the number=139. In this case, you would say that 139%39=0, which is not right.

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

      You are right but that's not what I mean. I think that you got me wrong. We can, for example, choose y = 39 then any number ending with 39 will work because y is a suffix of that number.

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

    What you can do is use complementary counting, and instead count numbers where there is no suffix that is a multiple of k (except 0), and subtract this from 9*10^(n-1).

    To do that, loop over the length of the number, and add a digit at a time, but only to numbers that have no suffix that is a multiple of k (i.e. don't use the 0th element to find the next row).

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

    Don't worry because you did not implement it correctly,idea was wrong!

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

    If I interpret your approach correctly, you will fail on n = 3, k = 3, among with all other cases with n ≥ 3 and k ≠ 1, 2, 4, 5, 10, 20, 25, 50, 100. You will not count the number 102 because its 1-digit and 2-digit suffixes (2 and 02), so you discard the possibility of x02 working.

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

I was on B for 1h 30m. No success! Wish I thought about C from the first place.

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

    Same here, except I wasted an hour cause I had used int instead of long long. Never making that mistake again! :P

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

C problem. Really good but I can't understand the fourth test example. Can someone explain it to me.

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

Как только закончился раунд понял как надо решать D: двумерная динамика, dp[i][j] = количество чисел, где i — длина числа, j — остаток от деления. Лень расписывать как считать, но если идея верна — подтвердите пожалуйста. Асимптотика O(10*n*k).

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

    у меня было еще 2 состояния — последняя(старшая цифра) и делился ли суффикс на К.

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

Got WA at #9 on problem C. What is it about?

I used 1LL for shifting.

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

oh my god!!!!!!!!!!!!! my C problem!!! why did it lag in 10 seconds last T_T ?!!

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

Jan/23/2015 19:59 Unsuccessful hacking attempt by * tourist

Now I have this achievement not only at TopCoder, but also at CodeForces :)

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

    lol, what did you do to him that he wants to hack your solutions so badly? :P

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

      I guess dist-=1e-12; of problem B.

      I've hacked two people whose eps is larger than 1.25e-11 with this test case:

      100000 100000 1 -100000 0

      which became the case 37 in system test.

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

        And funniest part is that my solution is actually wrong.

        This -1e-12 is too small comparing to dist; it just does not change dist at all :)

        My solution says 2 for this test case:

        100000 100000 0 -100000 0
        

        It also fails this test even with 1e-11 — this value still does not change dist.

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

          I bet here is the actual funniest part:

          http://codeforces.com/contest/507/hacks/132553/test

          This is the testcase I tried to hack you with :) and your solution prints 1.

          I found at least three ways to make it fail:

          1) Set dist = 200000; instead of actually computing the distance.

          2) Add cerr << dist; after subtracting 1e-12 from dist.

          3) Turn -O2 off.

          When none of this is done, your solution miraculously works.

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

            You are right, thank you:) Checked your hack attempt... Well, it works :D

            2) Add cerr << dist; after subtracting 1e-12 from dist.

            Yeah, and this was my mistake while trying to hack my solution in customtest; it was like let's output some debug values; I'm not changing my solution in any way, so it is OK :)

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

            4) Turn -ffloat-store on.

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

    Does Tanya Romanova love you back?

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

My accepted solution for E just finds a shortest path in the graph, if the cost of each edge is 4-z[i]... >.<

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

    And that can be proven correct, even. Among all shortest paths, the one that uses the most roads that are working is the best solution.

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

@AmrMahmoud

Nice problems. Liked the second one more :).

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

i just need ten sec

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

    I though that I needed ten seconds too. So I cry "NOOO!" when contest have finished, type last line of code ... and figure out that my solution is wrong anyway.

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

Nice problems, I loved them! (although my D failed on test 78 :( ). Still, more than the problems, I love that you put a list with the winners, which is very nice :). (at my previous div2 I was first and that guy didn't put a list with the winners, I will put him in my "black list" hehehe....)

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

The Fuck_Eyelids's profile is filtered for Iranians...

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

really nice problems RetiredAmrMahmoud :)))

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

How sad it is, that almost in all Div. 2 Only contests (and many both Divisions contests as well) the leaderboard is always filled with unrated contestants... :(

Dear Div. 1 users, there is a feature called "Unofficial Participation". Is it better to fight someone your size?

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

    I'm just wondering, what can go wrong if DIV1 participants are competing on same problem set, but in different division (not competing with DIV2 participants). I think it's still fair, for the best is maybe just typing competition. Also it might be not interesting for the best of best, but still interesting for the rest. What do you think?

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

      First of all, you already pointed it out — in most cases it will be just a typing competition. I think it will be a bad idea — to calculate contestant rating basing on results of solving such problemset.

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

        It may be also separate division (DIV1 contestants competing on DIV2 problems), but for example in my room only reds solved D and E, so for most contestants in DIV1 this might be interesting...

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

          Getting into top10 of div2 isn't easy for violet, I think that one should be at least strong yellow to have good chances for it. So even if we'll made such contests for violet and yellow (but not red) — it will not solve problem with unrated contestants in top10, i am sure that lot of them have red color at main account.

          Well, maybe CF should invent another rating — for unofficial participation:) It will not affect main rating, but may help with all those "i don't participate unofficially because such contests are not displayed in my profile", "i don't participate unofficially because it does not change my rating and i have no motivation" and so on.

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

            For div 1 users, two different rating:

            Rating div 1 contests (official -> Contest Rating)

            Rating div 2 contest (Additional -> Typing Rating)

            Image and video hosting by TinyPic

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

How rating is calculated, I joined and solved 2 but my ranking and contest tab doesn't show any change?

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

Wow, so nice!, maybe this was my worst contest (I didn't solve any problem) but, after an hour and a half of competition, I noticed that I knew how to solve the problem E, so I started to code it, and finally, 30 minutes after the end of the competition, i got ACCEPTED from my first submission, also this is my first E problem solved :D congratulations RetiredAmrMahmoud, and sorry for my english, please tell me if you don't understand something.

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

What?!? I become candidate master on first contest :) :) :)

by the way, time limit is a bit strict for python 3 user like me on problem D, I got TLE on test 74, finally I use some constant optimization to get AC on practice mode. but It's really fun :D

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

    It is known that the time limit is designed mostly for fast languages like C++. Python users sometimes need to do constant optimizations, or otherwise use another language altogether for time-critical problems.

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

As this was first contest on code-forces, I become 'Specialist' with solving one problem. Wish, better in next contest.......

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

Can somebody tell me what is wrong in this logic for C what i did. 1) calculate the parents of n upto node number 1 and store them in a array ( parents are always n/2 (integer division) ) 2) started from second last ancestor of the node ( first being node number 1 a.k.a root node ) 3) used the lrlrlrl relation to check if the number i wish to go to belongs to this sub tree or not . if it did just did count++;and changed character .(if l change to r otherwise change to l) else did count+= (1<<h) -1; and didn't change the character because my last step was already reverse of what it was supposed to be hence next will be same as before .
CODE

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

I loved the problem set. I encourage you to continue proposing problems, you're very good :).

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

lol everyone who failed B on test 37 due to floating point issues (me included, why does round return a double?), you can blame johnchen902, since the test was only added because johnchen902 hacked two solutions with it, and otherwise your solution would have passed :P

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

    lol, thats why I used integer arithmetic and binary search (I am always unsure about precision/rounding)

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

    It was not about floating point issues but unnecessary eps. In your case, your solution failed because of the minus 1e-9, which is too large. It should be smaller than 1.25e-11 to get pass test 37. In fact, you didn't need to minus anything, just like:

    printf("%d\n", (int) ceil(hypot(x1 - x2, y1 - y2) / (2 * r)));

    By the way, the toughest case I've found requires your eps to be smaller than 6.28009e-012:

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

what is the output of this testcase in B
0 0 1 1 2
the target point inside the circle ?

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

    R can't be 0, and if the target point is inside the circle, the answer is 0 or 1, depending whether the target point coincides with the current point or no, respectively.

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

Could someone please take a look at my solution to C? I got the correct answer 830699159852 for input 39 457181784666 on my machine but wrong answer 547231318312 on the judge. Notice that the second input is a 64-bit int. Later, I realized during the contest I forgot to change scanf("%lld", &n); to %I64d (9526642). But after that is fixed, I still have the same wrong answer (9538126). So I used cin instead, but again, wrong answer (9538164). Could someone please take a look? I think the algorithm is ok it is just the difference between my machine and the judge. Thanks for any help!

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

    OK. I changed the language to C++11 and it is AC now. I am more confused now. Which part of my code needs C++11 standard?

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

      It seems that the constructor of bitset is 32 bit for C++98 and 64 bit for C++11

      from cplusplus.com

      integer value (2)
      C++98: bitset (unsigned long val);
      C++11: constexpr bitset (unsigned long long val) noexcept;
      
»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Probably for the first time in my programming history I didn't care about float numbers' error and hey, it worked!

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

sorry for posting off-topic, i couldn't find any other place to post: this time AGAIN the CF round (288) is div-2 only. Why the sudden change of plans? earlier it showed both div1 and div2 o.O

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

Can someone explain the last case of DIV-2 C ? 1024 is located in the left subtree of the root(1). Now our first command is L , so from root(1) we will be going to the left subtree . That means we will not visit the right subtree before finding the exit , so how come the answer is 2046 while we already have reduced the half of the node in first command ?

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

مبروك