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

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

Codeforces Round #328 (Div. 2) will take place on October 31, 19:30 MSK, as usual Div. 1 participants can join out of competition.

Problem Setter: Morphy (Alei Reyes)

Coordinator: GlebsHP (Gleb Evstropov)

English to Russian translator: Delinur (Maria Belova)

Codeforces and Polygon: MikeMirzayanov (Mike Mirzayanov)

Hope you enjoy the problem set.

The score distribution will be announced later.

UPD. Score Distribution: 500 — 1000 — 1500 — 2000 — 3000

UPD. Problem Analysis is available

Congrats to the winners!

Div. 2

 shamir0xe

 lbn187

 SuperLoser

Div. 1

 uwi

 NanoApe

 Haghani

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

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

Краткость — сестра таланта :)

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

"Codeforces and Polygon: MikeMirzayanov" wrong. MikeMirzayanov is a human he can not be codeforces and polygon. he is codeforces and polygon manager and creator.

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

MikeMirzayanov is human.. Thank you, I always thought he was like this

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

Short announcement :D great!

Let's hope for short problem statements too.

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

hope there is no Physics and Chemistry problems this time :))

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

waiting and hope nice rate this time :)

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

short and good blog :) thanks

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

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

is this your first time ?

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

    Yes If he's any previous one , simply you will find a "Problemsetting" section in his profile :)

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

It looks like Morphy was so bored when he wrote this blog :/

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

Upvote just for the amazing text :D

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

No Delinur as problem translator?

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

Как боженька смолвил.... ;)

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

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

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

MikeMirzayanov is mentioned in announcement

I guess ,no delay in closing ceremony this time :-p

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

Finally a nice short anouncement.

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

at least for me I think longer round announcement with some words about authors like education, experiences, career,... will be better.
and about problem statements I like short ones with little story I don't like statements like given x calculate f(x).

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

I hope that it will be a great contest and we will find out something about author's country

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

I will get lots of downvotes but I'll say it : I hope there will be lots of math in the contest !

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

why the minutes before contest are like hours but the hours of duration of the contest are like few minutes?

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

hello.who will help me to solve the questions of this contest

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

please help me,please,please

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

First problemset made by a peruvian coder in Codeforces :D!

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

Morphy his nickname says math problems

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

Am i the only one who didn't even understand the problem statement of problem C after trying it for 1 hour -_-

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

I tried to send solution to A and forgot delete files and I got WA2. How it's possible that my solution passed first test?

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

ZzZZzzzZZZZZzzzzzzzz is the true MVP of this contest!

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

У меня 228 за А

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

I am sure lot of C are going to fail :)

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

Terriblest C in my life :(

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

Problem C PreTest 11 :/ Kept failing on that pretest

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

This was a very educational round.

I learned like 20 ways to calculate N^2

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

    How come?

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

      Problem 2 was effectively a super glorified way of asking for (N-2)^2.

      When hacking solutions, people had all sorts of crazy lines that somehow came out to (N-2)^2

      My current favourite is 1+((n-3)*3)+(n-3)*(n-4)

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

        Oh...haha!Poor guy, he must be thinking how come so many people already solved it so quickly :D

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

        my was n-2+(n-3)*2+(n-4)*(n-3). I really like this formula.

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

        at first problem B looked impossible to solve and i was like "solved prob A and thats it for today!!"

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

        I used such an approach. Having seen some (n - 2)2 solutions I still don't know why it works :D

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

          There is a nice explanation in the comments below. The main rays from 1 divides the plane in n-2 parts. Rays from each of the other vertices divide the parts into n-2 sub parts.

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

        Haha, that was my line! :D

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

        I used that one, the idea is that the point 1, 2 and N create N-3 areas. All the other ones do N-4 so it's 3*(N-3) + (N-3)(N-4) + 1

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

How to solve D?

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

    I almost got in time to solve it, missed a couple of minutes. My approach was:

    1. Clean up the tree, meaning we delete all the unneeded paths (if you draw your graph and then mark attacked nodes as red, unneeded paths are those which start at red node can't lead to any other red node). Sounds difficult, but computationally I just used a BFS starting from the nodes which are not attacked and which have only 1 child node.

    2. Find a diameter of the lefrover tree (this part is where I couldn't code the solution in time). Mark the nodes which the diameter consists of. Now start from one end, and traverse the nodes in the with the next dfs: first visit not marked nodes, calculating the distance on the way in and out, then visit the marked node, calculating the distance only once.

    Now the resulting distance is known, the starting node should be one of tho ends of the marked path (one with the lower index).

    I just haven't ever wrote a "find diameter of a tree" solution so I couldn't code the solution under the pressure.

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

There's a point about C!

Contestants which code with Python or Java which includes BigInteger option, could have solved this problem easily! Is this fair?!

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

respect for E. Came up with solution, but haven't managed to code it in time. Beautiful problem imho

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

Share your C hacks! Mine was 5000000000000000000 274177 67280421310721 for unsigned long longs, because the product of the last two numbers is precisely 2^64 + 1

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
if (minA < minB) cout << "A\n";
else cout << "B\n";

It seems that many people made this mistake at problem A. :)

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

    Some people failed coding a O(n^2) solution. I've hacked with this test case

    ........
    ..B.....
    ......W.
    ..W.....
    ........
    ........
    ..B.....
    ........
    

    Because they didn't check the 'B' in position (7, 3)

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

    I got 4 hacks using this :D

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

Психанул

P.S. Еще и А упадёт.

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

    Ну у тебя это хоть не официальный контест:D (Хотя я и не пытался взламывать)

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

Is the solution for problem E the number of triangles over points (ri - c, wi - d) that contain the origin?

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

my way for solving C were that count the number of k and k' that ka + c = k'b + c then the answer is

mul that to number of such "c" that it is min(a , b) — 1 that(non of a and b are not 1) is it true?

i could not write its code in true way!

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

    i'm so stupid! i need just using lcm(a , b) instead of a*b!

    i won't become a programmer! :( ;_; !

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

What the hell does it mean to hack problems ? For no reason someone hacked my problem A,which is quite rude since I thought a lot at how to get it done.I locked my problems because I thought this is a way to show that I am sure of my solution,and I that's what I get...

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

    Well, getting hacked helps a lot of times.. its better to get hacked, and re-attempt, then to fail at the sys-tests.

    What a lot of people do , is only lock if they are pretty sure that their code won't go wrong on some boundary cases, or if their approach is completely right.

    I only lock, after I am pretty sure, or my codes have sustained some failed hack attempts.

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

    It is a feature of contests in Codeforces. It just means that somebody looked at your solution, found a bug that was not being tested for in the pretests, and made your program fail to earn themselves points. You get to correct your solution when they do that (if you haven't locked that problem), so it benefits you, actually. If you submit a solution that passes pretests but has a bug, it will ultimately fail system tests assuming that the problemsetter has robust system tests. So being hacked is actually better than not being hacked, imo :)

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

How to solve Div2 B?

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

Just a combined contest!!!

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

Div2-D today killed me. Spend 1 hour 30 minutes just to get WA on pretest 9. Is there anything special in it? I almost died with that.

Anyway, why Div2-B answer is always (n-2)^2?

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

    If you follow what the problem statement says, the polygon will be divided the n-2 triangles and each triangle will be divided to n-2 areas. So the number of total areas would be (n-2)^2

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

    What was your idea? I have got WA3 with this one: find two bad vertices with maximum distance.Find subgraph which have all bad vertices in it, and there is no outside. Answer is (2*(number of vertices in subgraph)- maximum distance between bad vertices).

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

      Exactly the same with my idea. Don't know if this idea is incorrect, or there's some problem with my implementation.

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

      I think it should be (2*(number of EDGES in subgraph)- maximum distance between bad vertices), which is always 2 less than what your algorithm would answer. But I might be wrong, because that would give WA for the sample tests as well, and I suppose you tried those, right?

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

    killed you ? that's cute

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

    I actually saw the pattern then went forward to write a small induction proof that says that the addition of a new point to any polygon with n regions will introduce 2n-1 new regions.

    And we know that n^2 + 2n-1 = (n+1)^2.

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

      No.

      Actually, the first vertex is special — it creates (n — 2) polygons. The second vertex and the last ones also require special treatment. They both create (n — 3) new polygons.

      All the rest vertices add (n — 4) polygons each. And there are (n — 3) of such vertices. That means these ordinary vertices create (n — 3) * (n — 4) polygons in total.

      So, you get the formula: (n — 2) + 2 * (n — 3) + (n — 3) * (n — 4) = (n — 2) * (n — 2)

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

        I had to convince myself with that formula by drawing.

        When I meditate long enough over that picture, the formula becomes obvious :)

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

Competed after, like 5 contests due to some or the other reason for missing them. Felt so good :) Got A hacked, but still, I'm happy to be able to compete today :)

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

TOO MANY OVERFLOWS in this contest :|

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

XD my submitions for Div 2 B!!!

1- (n-2)^2

2- n^2 — 4n + 4

XD XD!

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

Верно ли, что задача D решается за O(n*log(n))? Почему может быть TL на 9-м претесте?

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

    я решил(ну еще, правда, не отправил, тк на контесте не успел) за O(n)

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

D — easier version of Problem 6 — KAMP from http://hsin.hr/coci/archive/2014_2015/contest1_tasks.pdf.

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

I'm really happy to see very little unregistered users in the top 50, at least compared to pre-color revolution.

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

I'm really happy to see very little unregistered users in the top 50, at least compared to pre-color revolution.

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

Please start system testing. we all are waiting ! :(

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

So. Era of long wait for System Tests and rating changes has begun.

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

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

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

please start system testing!!!!

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

TIL Python is a good language for competition programming.

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

problem D is really nice! Had a lot of pleasure when solve it :)

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

Oh please system testing, don´t let my solution for C, falls into the abyss :(

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

Return TestsNotFound Exception()

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

Return TestsNotFound Exception()

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

хм, не пора ли начать системное тестирование?)

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

Editorial before System Test :o

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

.

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

Waiting for systest got me like

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

Thanks for the speedy editorial! :)

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

Wrong answer on test 106? O.o

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

Насколько корректно в задаче C не принимать ответ 1, а вместо него требовать 1/1?

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

    На 100%, поскольку просят вывести ответ в виде несократимой дроби

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

I was so confused about my solution of C and D . System Test was so late that I wrote many random huge dataset for them and took high rated coder's code as AC solution . My code worked for them and got some relief . :D

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

Please improve the problem statements, some of them were irritating.

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

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

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

I'm not sure why my solution for C is wrong..

My source is here. http://mirror.codeforces.com/contest/592/submission/13988182

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

    I compare using double to avoid overflow.. Is that a problem? Test 58 shows wrong answer, but it shows correct answer on my local environment..

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

      This is a precision problem. Note that in the failing testcase we have and t = lcm(w, b) = w * b. But multiplying w and b apparently introduces a floating point error that makes lcm(w, b) exceed t, resulting in the wrong answer.

      Here is the accepted solution: 13994692. I replaced the doubles with long doubles (and also fixed a bug in your gcd function). In general though, I would not recommend completely replacing integer computation with floating point computation, this problem can easily be done with integer arithmetic alone (e.g. by noticing that is equivalent to , and then after establishing that t exceeds the lcm you can safely compute it).

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

        Thanks. I've checked and I have one more question.

        I'm using MS C++, and if I choose MS C++ solution still shows wrong answer. But if I choose G++11, solution passes.

        Is MS C++ has a precision problem? G++ is more accurate?

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

          See here, for some odd reason long doubles use 8 bytes in MS C++ (exactly the same as doubles), whereas G++ gives them 12 bytes (also 8 bytes for floats).

          Go to custom invocation and run this code with both compilers:

          #include <iostream>
          using namespace std;
          int main() {
            cout << sizeof(long double) << endl;
            return 0;
          }
          
          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I still don't understand why 'double' works in G++, do not work in MS C++. They both using 8 bytes, but their precision is different?

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

        I've checked once again, just using 'double' instead of 'long double'. 'double' is enough if I use G++. MS C++ sucks...

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

Why are the problems not up for practice?

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

У меня тут уже минут 40 систестирование висит на 100%. Это норма?)

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

Problem C wrong answer test case 58 it's weird because my machine shows correct answer, but on codeforces output is different. and i am not using any built in functions . Any explaination?

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

такс такс такс што тут со взломами...

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

What is the maximum size of an int when using MS C++ on codeforces? This question pertains to this codeforces problem: 328 div 2 problem B

This code: #include <iostream> using namespace std; int main(int argc, char **argv){ int points; cin >> points; unsigned long long answer = 1 + (points-3) + 2*(points-3) + (points-3)*(points-4); cout << answer << endl; return 0; }

produces an output of: 18446744072365138081 when given an input of: 54321 The correct answer is: 2950553761

Yet.....This code produces the correct answer for all of the test cases. #include <iostream> using namespace std; int main(int argc, char **argv){ int points; cin >> points; unsigned long long answer = 1 + (points-3) + 2*(points-3) + (points-3)*(points-4); cout << answer << endl; return 0; }

Last time I checked the maximum size of an int is much bigger than 54321.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    • points = 54321
    • (points — 3) * (points — 4) = 54318 * 54317 = 2 950 390 806
    • MAX_INT = 2^31 — 1 = 2 147 483 647
    • (points — 3) * (points — 4) > MAX_INT

    try this

    • 1LL * (points — 3) * (points — 4)
»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Is the round unrated? My rating change is gone.

UPD: Sh*t, it's back :D

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

Problem C is a little unfair to C/C++ coder!

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

    There was a bit of discussion above.

    The general consensus is that BigInts aren't really necessary to solve this problem, you just need to be clever about how you handle your calculation of LCM.

    And if you know C/C++, and really don't want to handle big numbers, then learning a bit of Java shouldn't be too much of a stretch.

    Also there's that one datatype, __uint128_t, I think it was. Last I checked, there was actually no overload to print it, but you might be able to use it as an intermediary for holding large numbers. I haven't tried, so don't quote me on that last one though.

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

      Well, it's certainly easier to use python or java than c++ on C, and the main mistakes people made on the problem would not have been made to c++.

      Personally, after seeing the limit I immediately switched to coding python in Custom Invocation, and I think it would be better to have problems that don't require much additional thinking (algorithmic not implementation) for different languages.

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

    So either you learn how to handle big numbers, or you learn a new language. Choice is yours. I personally would go with the first , if the only reason to learn a new language is to avoid having to handle big ints :p

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

    Search for "C++ BigInteger". There are some short & good implementations that you can use for contests.

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

I still can't believe that I got the rank#2 >.< It was my best result >.< But I hope that I can pass the NOIP(a contest in China). If I can't pass it, I will keep away from OI. QAQ

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

In the past contest, I tried to solve "Problem C — The Big Race", eventually, got wrong answer on test 58 However, I check my program with the test 58 locally, the answer is correct! I'm confused! Does anyone know why? Thanks!

pic 1 -- local

pic 2 -- online judge

P.S: I got AC when changed unsigned long long to long long Still do not why......

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

    It is related with double's precision error.

    w*b is q, therefore a-q is zero, and sgn(a-q) should be 0 if there is no precision error.

    However, with how compiler optimize the code, result can be different within machine epsilon. That depends on compiler, even unsigned long long and long long can be different. In Codeforces environment, a-q might little bigger than zero, and it may occur wrong answer.

    Avoid using real number as possible as you can.

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

Медали в посте подтолкнули на мысль о том, чтобы добавить возможность получать achievements(медали за места, n взломов за контест, решил все задачи div 1, и т.д.) в профиль. Или хотя бы чтобы призовые места где-то кроме рейтинга отдельно фиксировались. Кстати а за призовые места в div2 дают какой-то приз?

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

I still can't understand the problem C , can any body explain it ?

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

    M = min(w, b)
    G = gcd(w, b)
    L = lcm(w, b)
    K = t div L
    All distances D, when Willman and Bolt tie have form D = k*L + r, where 0 ≤ k ≤ K and 0 ≤ r < M.
    Why it is true? Easy to see than for all D Willman and Bolt run for k*L meters. And for all another distance if M = w Willman run for k*L + w meters, when Bolt run for k*L meters.

    All possible D is k*L+r (except 0). How to find count of that? Let's imagine table, where row indexed 0..K, and columns indexed 0..M-1. And fill table with all possible D. Then one can see, than ans = M * K - 1 (for all rows exsept last)  +  min(t - k * L + 1, M) (for last row).

    Example: t = 10, w = 2, b = 3.
    M = 2
    G = 1
    L = 6
    K = 1
    Draw table
    0 1
    0 0 1
    1 6 7

    ans  =  2 * 1 - 1  +  min(10 - 1 * 6 + 1, 2)  =  1  +  min(5, 2) = 3

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

      thanks , but i wasn't looking for a solution i didn't understand the problem it self , for example for the first sample why 6 is a tie ?

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

        because both runners in same time 6 meters, and because of abyss no one can run more, so it's tie. Same thins for 7 — both will run 6 meters.

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

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

During the contest, I got a solution for D but it failed on test case 3. I have debugged it with over a dozen small corner test cases, but I can't find the mistake that its making on the 3rd case. The 3rd test case's first line is 123456 123456, and my incorrect output says to start from node 1, but the correct answer is some other node which yields a smaller distance than what I output.

Is there a special thing you must consider for this test case, and did anyone else have the same problem? If someone could help me with my code that would be great; it is fully commented at http://pastebin.com/m5yEa778. I also appreciate feedback on style, tips for simplification, etc.

My method was (as far as I can tell) equivalent to the official solution. I remove all unnecessary edges, then find the two farthest nodes from the root in different subtrees and use the one with smallest index to start (I assume this is the diameter).

Edit: For some reason my browser arbitrarily italicized parts of this text; is there a way to fix this?

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

Interesting problems,thx

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

Ok, you should definitely lower Div2 problem difficulty... Problems A and B were excellent. Problem C... i don't even know what to say about problem C. It's difficult to even understand what is asked. Problem D should at least move to most difficult and problem E is for Div1 ...

This is my humble opinion, but i think others will agree.