Morphy's blog

Codeforces Round #328 (Div. 2)
By Morphy, history, 9 years ago, In English

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

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

Comments Comments (195)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +59 Vote: I do not like it

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

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

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

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +80 Vote: I do not like it

Short announcement :D great!

Let's hope for short problem statements too.

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

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

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

    What about biology?

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

      :P

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it -7 Vote: I do not like it

      maybe other subjects such as sociology and ... :|

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

        How about history? I have history exam tomorrow.

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

          and literature and geography :|

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

            implying humanities sciences are actually sciences

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

              >look I know how to greentext
              >implying geography is a "humanities science"

              But I agree otherwise.

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

      I don't find anything wrong with this "Biology" problem: 579A - Raising Bacteria

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

        So irrelavant to programming!! even that problem doesn't need to know about biology, but in the last contest, we have problems which solved using physics!!

        → Reply
»
9 years ago, # |
  Vote: I like it -13 Vote: I do not like it

waiting and hope nice rate this time :)

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

short and good blog :) thanks

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

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

is this your first time ?

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

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

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

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

Upvote just for the amazing text :D

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

No Delinur as problem translator?

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

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

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

MikeMirzayanov is mentioned in announcement

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

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

Finally a nice short anouncement.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

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

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

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

    His country is Berland or Byteland. Neither of really existing ones.

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

      That moment when you realize that Berland is not an actual country.

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

      And Byteforces it is.

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

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

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

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

→ Reply
»
9 years ago, # |
  Vote: I like it -45 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it -25 Vote: I do not like it

please help me,please,please

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

    From the Beatles it sounds better... :D

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

    Solve yourself. You won't get any benefit if you do like that.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

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

Morphy his nickname says math problems

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

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

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

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?

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

ZzZZzzzZZZZZzzzzzzzz is the true MVP of this contest!

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

    Wow, first time I see my name on the comment :)

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

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

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

Terriblest C in my life :(

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

Problem C PreTest 11 :/ Kept failing on that pretest

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

This was a very educational round.

I learned like 20 ways to calculate N^2

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

    How come?

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

      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)

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

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

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

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

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

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

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

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

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

          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.

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

        Haha, that was my line! :D

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

        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

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

How to solve D?

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

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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?!

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

    Yes, it is. You don't need the LCM(w,b), if it is bigger than t.

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

      but you cant * if w and b are 10^18.

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

        For what do you need to multiply them?

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

          to se if LCM(w,b) is bigger than t.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            ← Rev. 7   Vote: I like it 0 Vote: I do not like it

            So you don't know how to check it without direct multiplying?

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

        k=a*b/gcd(a,b)

        Then, k=a/gcd(a,b); You can simply leave out multiplying it by 'b', and later multiply by b separately wherever needed. Hoping my solution passes

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

        Check if (b/__gcd(w, b)) * w give overflow first. If it does, then it definitely greater than t.

        How to do that:

        #define ull unsigned long long
bool overFlow(ull a, ull b) {
    return ((a*b)/b == a);
}
        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is really easy to solve this problem without any big numbers. The only problem is to check a * b > max long long.

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

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

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

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

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it 
if (minA < minB) cout << "A\n";
else cout << "B\n";

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

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

    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)

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

    I got 4 hacks using this :D

    ........
.W......
........
........
........
........
......B.
........
    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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!

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

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

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

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

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.

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

    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 :)

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

How to solve Div2 B?

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

Just a combined contest!!!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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?

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

    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

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

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

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

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

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

      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?

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

    killed you ? that's cute

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

    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.

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

      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)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        I had to convince myself with that formula by drawing.

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

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

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 :)

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

TOO MANY OVERFLOWS in this contest :|

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

    Codeforces Round #-328481999481

    AKA

    Codeforces Round #OVERFLOW

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

    Codeforces Round #328 — Halloween Special: Overflowed Overflow

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

XD my submitions for Div 2 B!!!

1- (n-2)^2

2- n^2 — 4n + 4

XD XD!

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

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

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

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

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

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

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

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

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

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

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

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

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

please start system testing!!!!

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

TIL Python is a good language for competition programming.

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

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

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

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

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

Return TestsNotFound Exception()

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

Return TestsNotFound Exception()

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

Editorial before System Test :o

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

.

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

Waiting for systest got me like

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

Thanks for the speedy editorial! :)

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

Wrong answer on test 106? O.o

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        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?

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

          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;
}
          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

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

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

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

Why are the problems not up for practice?

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

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?

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • 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)
    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Is the round unrated? My rating change is gone.

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

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

    I noticed the same thing--thought I was going crazy for a second.

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

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

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

    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.

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

      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.

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

    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

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

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

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

    I am a Chinese Sophomore, but I don't heard the NOIP in high school. Now, I'm studying hard. Come on and good luck!

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

    Good luck!

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

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

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

    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.

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

      Thank you for your advice!

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

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

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

    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

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

      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 ?

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

        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.

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

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

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?

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

Interesting problems,thx

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

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.

→ Reply