qwerty787788's blog

Codeforces Round #253
By qwerty787788, 11 years ago, translation, In English

Hello!

We invite you to participate in Codeforces Round #253, which will take place on Thursday, June 19th at 19:30 MSK. The round will be held in both divisions.

It's my first Codeforces Round and I hope you will enjoy it!

Many thanks to Gerald for helping to prepare the round. Also I'd like to thank MikeMirzayanov for creating such a good platform. Also thanks to testers of this round: antonkov, Aksenov239, VArtem, subscriber, niyaznigmatul and to Delinur for translating statements.

Don't miss a chance to have fun of solving interesting problems!

UPD. Score distribution:

Div1: 500-1500-1500-2000-2500

Div2: 500-1000-1500-2500-2500

UPD2. The contest is over, thanks for participating!

Congtatulations to Div1 winners:

1) tourist

2) scott_wu

3) stevenkplus

3) gs12117

5) GlebsHP

And congratulations to Div2 winners:

1) tafit3

2) thnkndblv

3) MIT3

4) lucaslima

5) liuzhijian

My congratulations to tourist, only person who managed to solve all five problems, and only one who solved problem 442E - Gena and Second Distance!

You can find editorial here.

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

Comments Comments (127)
| Write comment?
»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Early announcement, thanks for this!

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

    Early announcement --> more up-vote!

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

      Comment regarding Early Announcement --> more up-vote!

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

        Comment regarding "Comment regarding Early Announcement --> more up-vote!" --> more up-vote! :D

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

          It's too hard to write something funny. So just down-vote me pls.

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

          Why you down-vote me? Can't we make fun a little? :(

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

            That would have led to an infinite loop :(

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

              Actually my last comment have '37' down-vote. So anyone doesn't say "Comment regarding bla-bla-bla --> more up-vote!" :D

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

                Hence No infinite loop. :)

                break; // thanks

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

            Repeating jokes usually aren't very funny, especially if they're formed by repeating someone else's joke.

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

    is it always necessary every time when the auther makes an early announcement someone writes a comment saying "wow early announcment"

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

      I think, this is earliest announcement.

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

Hope we all get good grades

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

    why so many down?

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

      Maybe because programming contests aren't school, so there are no grades? (So it's a completely off-topic/spam comment.)

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

      I think because he used "grades" instead of "ratings". Note that similar comment from the same person with correct word has been accepted AC.

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

        I have a good answer for that, too :D

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

          Consider the case when all participating users rank exactly according to their rating before the contest, and all participants were specialists initially. Then, since the participant has not been 'overtaken', his rating should not decrease.

          All constructive ideas, comments and clarifications are welcome.

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

        Well now i think it is because the probability of her hope being fulfilled is 0.000000000. Proving it is a good exercise of mathematical reasoning.

        Please think that whether you wish is theoretically possible. That comment is down voted mainly because it was intended towards just commenting.

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

Hope rating++~~~ Enjoyable contest in Codeforces becomes one of my daily life~

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

    agree. It becomes one of my daily life :)

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

    me too,I really enjoy it,espically when my rating gets higher :)

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

      Me too! I really hope improve myself and get the higher rating :)

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

        me too. Rating up and down here, so enjoyable!

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

          This is the second : tending to infinite loop in this page.

          I dont want that every user comes here and contribute like this.

          So, I hope this will break the flow :

          break;

          This comment does not wish any replies as then the brake will fail.

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

The final exam is approaching.But It is always enjoyable to have a codeforces round.Hope all the participant can enjoy the round.

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

    participate in contest can keep on the feeling of algorithm. And codeforces contest costs only 2 hours.

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

    yes,really can not stand watching stand by but not participanting in this game

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

    May the codeFORCEs be with you...during exam ;)

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

The same day with TopCoder SRM 625.

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

Thanks god there is no worldcup match that time!

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

    Colombia VS Côte d'Ivoire

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

      oops! I didn't see that!
      So, too bad that there is a worldcup match that time :(

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

Too many contests in the exam days , hope there will be that much in the holiday

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

Expecting the problems to be based on footballers / football :)

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

Hope your first Codeforces Round will success and the problems are diversity and useful for everyone

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

hope everyone get higher rating !

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

    I hope not. It would mean that there's something seriously wrong with the rating system, not to mention it'd be boring.

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

Last Codeforces round before ACM ICPC World Finals! (or not?)

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

    I think it is yes for Div1 , but it is not necessary to stop Div2 contests during the World Finals

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

last few contests users ask why problem writer write "score distribution will announce later"
but here score distribution not mentioned at all he didn't say later or mention it.

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

    I see very little point in writing "scrore distribution will be announced later" because it doesn't give readers any new information :)

    Of course as early as we dicide everything about score distibutioin I'll add the information to the post.

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

      orly? That phrase is at least more informative than this one: "Don't miss a chance to have fun of solving interesting problems!"

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

I am a new member of codeforces.. I wuld like to know regarding the concept of div 1 and div 2 What are they?? and in which of them do I belong ?

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

    Any new contestant by default belongs to Div2. If you do good, and your rating increases over 1700, then you will be promoted to Div1. The rest you will figure out once you start participating regularly.

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

Hope I will make it to first division! It's the first time I am so close. Only 31 points...

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

Looking forward to the codeforces round and the WC match after the contest between england and uruguay

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

Can anyone explain what is meant by the score distribution Div1: 500-1500-1500-2000-2500

Div2: 500-1000-1500-2500-2500

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

    There will be 5 problems and maximum points for each individual problem are 500-1500-1500-2000-2500.

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

Had a really great performance Topcoder SRM 625 a few hours ago ... hoping for same (or maybe better) performance in this codeforces round! GL & HF everyone!

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

Please can anyone upvote/downvote my comment ? I want to see what kind of notifications we get when our posts are upvoted or downvoted .

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

I'm a new contestant of codeforces so div 1 or div 2 which appropriate for me... ????

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

    Since you clearly don't know that you're assigned a division based on your rating (and unrated means div2 automatically), it's clear that you're new :D

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

    div2

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

    div2

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

      There was some problem . Xellos and aangairbender's comments were not visible when I replied .

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

        Why don't you press F5 when you reply?

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

Does Div2 B have 1500 or 1000 points?

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

I really don't understand C div 2 problem statement and examples!!!

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

Can someone explain div2 B problem ?!

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

I feel like I just took out my hack interest over the past 2 years... +4 mfw

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

Problem B Div2 was harder than usual! I also think D div2 was easier than C! Because it had more pretest passed submissions!

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

Very Hard Contest O.o , C — no idea, D-I hate statistics homeworks , E — wow what a problem, but no idea :(

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

How do you solve Div.1 B ? I see lots of people have solved it. I myself submitted something that will definitely get TLE on system testing. The solution eludes me. :/

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

    sort by decreasing values and greedy algorithm

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

      Can you prove this solution?..

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

        The editorial's up, and the solution's there. Key idea of the solution: if a set S has , adding p to it increases the result proportionally to p (so we want to add the largest p).

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

    dp[i][j], i — all taken count, j — last taken 

    for (int j = 0; j < n; ++j) {
  d[0][j] = p[j];
  no[0][j] = (1 - p[j]);
}
for (int i = 0; i < n; ++i) {
  for (int j = i; j < n; ++j) {
    for (int k = j + 1; k < n; ++k) {
      double x = d[i][j] * (1 - p[k]) + no[i][j] * p[k];
      if (x > d[i + 1][k]) {
        d[i + 1][k] = x;
        no[i + 1][k] = no[i][j] * (1 - p[k]);
      }
    }
  }
}
    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

[ Deleted ]

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

Editorial please...!

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

I hope system testing and rating update come quickly

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

Hard contest...please give editorial soon.

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

Problem C (div2) is hard to understand.

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

Can anyone give me solution for problem D div 2?

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

    See editorial

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

      I am in the same room with you~ how lucky~ When you hack others.. I felt quite scared!!!!!!!!

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

        Well, your solution was safe... which can't be said about GodDammit. Hacked after lock, early on in the contest. Talk about choosing a bad name :D

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

          It is so hard to become International master....sad....2049.....

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

the system testing is very quickly! good

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

Damn, why TL in D was so strict :/? My O(n log n) failed and I ended up on a 171st place instead of in TOP20 :/. Moreover, I wasn't the only one. There are many failed submissions because of TLE.

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

    Same here. Got TLE for pascal solution 6921143. The same code receives AC in 390 ms on Delphi: 6923185.

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

    Our Java solutions work something like 500ms... I don't think 4xJava solution time limit is strict.

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

      Are you sure? This is ~1/3 of all submitted solutions during contest.

      (Edited picture, thanks nic11)

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

        Maybe

        <img width="100%" src="blablabla">
        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        You can post the pic in HTML, you can resize there.

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

        You can look at Aksenov239 solution: 6923989, or mine 6923978 with classes and recursion. Both of them work quite fast.

        If you can't see this submissions, you can view it on pastebin: mine and by Aksenov239.

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

          I don't know exact shape of testcases, but solution described in editorial does something like "do something until something" which can be estimated by O(n log n), maybe maxtests where easy cases where your solution worked faster? My solution works offline and takes teta(n log n) time and I'm not using anything which can make constant to significantly grow like set or maps. My space complexity is also O(n log n), but that shouldn't be the case. Is there anything really stupid I'm doing, which was a reason I got TLE http://mirror.codeforces.com/contest/442/submission/6917926 ?

          And one more question — what is the point of setting such big constraints? Will anybody get hurt if n<=10^5 instead of 10^6? I guess not.

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

            We have maxtests on which model solution works teta(n log n). Setting smaller limits always increases chances some solutions with wrong complexity pass.

            But I'm really sorry that I forgot to include a maxtest in pretests.

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

              Sometimes, it's impossible to make sure just all solutions with good complexity pass. As was clearly the case here...

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

            I'm glad that swistakk solution got TL. And I will get hurt if coders like swistakk take top20 place.

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

              Lol, that's pretty rude :P. I guess this is my award for whining about TLs while I should be grateful for preparing contest, but you know, receiving TLE in solution with optimal complexity (especially those without any complicated data structures) is always frustrating :P

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

              Would you also get hurt if coders like me get second place on ACM ICPC WF ( ͡° ͜ʖ ͡°)?

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

        I got TLE because I stupidly used heap to maintain 2 maximals and use cout to output.

        I think the TL is fine, but it would be better to add maximal test case in pretest so we will know the code is not optimal enough.

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

      Hm, I got AC after changing vectors to arrays (and 1e6 to 1e6 + 5 :P). I guess what's taking most of the time is doing n resizes to 23 and 23n resizes to 2 :P. I was also really close to exceeding memory limit (230 out of 256MB). Allocating that amount of memory is slower than I wanted it to be.

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

My solution of D div2 failed in test case 5 because i didn't use setprecision :(

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

    Many many people missed D because of this :(

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

    In the Ukraine and Russia this coders are named "Loh" or "Noob".

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

    Many People missed that the error was 10^-9 and not 10^-6.

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

I feel that to give credit to the right technique for problem B (div1), the constraints should've been such that n <  = 105

P.S.: After sorting the array of probablities, I just used a naive test-all-subarrays algorithm which passed.

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

    Your O(N2) Solution couldn't pass N = 105 ;)

    Anyway , I see the O(N) solution, I think 100 has been chosen nicely by author ... cause nobody have 105 firends who set problem !!!!

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

      Mike Mirzayanov? :D

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

      "Your O(N2) Solution couldn't pass N  = 105 ;)"

      -- This is precisely why I said that the constraints should be increased. I did not find the O(N) technique and was still able to solve it.

      --I don't even feel like replying to what you wrote later on man. I'm out.

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

Div1 — B I got wrong answer at test 17.

only for this line : printf("%.10lf\n",1);

Some of you will be amused to see the output

my WA code

my AC code

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

    shit happens :D

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

    Printf expects double, you pass int. It's because of the compiler.

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

When I passed pretests on Div. 2 B, I thought I was the luckiest guy in the room(I was just playing with the code and it started giving right answers :D). Didn't pass the systest though...

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

Can someone suggest a book to study algorithms please? Which books did you use to learn them? Both Russian and English ones are acceptable ;)

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

    Introduction to Algorithms by Cormen and other guys is my favourite one, although I've read only DP chapter...

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

Hi, In Div 1 — B I got wrong the case #31, however when I run it locally it works fine and give the correct answer. Does somebody now where may the problem be?

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

    Have no idea why that is a problem, but after doing the following, it worked:

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

      Thanks, I had always though that double and long double were identical in GNU C++!. I find rather surprising the huge difference between the result in one case and in another. Well next time I'll use long double if I can remember it!

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

        You're welcome.

        But have you got any clue to why the output is like that when using "double"?

        And the more weird thing is this. I don't think it's a mere precision problem (not sure): http://ideone.com/31XMxJ

        Anyway, I haven't looked carefully at it yet. Will probably do that on Sat. isA.

        And something that may help explain the reason but haven't tried before is checking the assembly code outputted from the compiler. But of course, don't forget to use the same compiler & compiler flags as theirs. (Sorry if it's a noob note, I'm a little nooby so I assume everyone is like me :D)

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
          But have you got any clue to why the output is like that when using "double"?

          More or less I have finally found it. It has something to do with he -O2 flag it seems to handle some comparisons in a different way, I suspect that it doesn't save mx to memory so it uses a value with more precision (long double?), which is lost whne saving to memory. The question is that the order in the priority queue is changed. But now for equal values of the first parameter the queue gives the result in reverse order which is wrong.

          Possibly in your ideone output, when printing the output mx is saved into memory and that affects i's precision. (Well is an hypothesis)

          So it is a bug in my code. That's good I don't want to lose my faith in GCC !! :-)

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

    Yeah can some one tell me what is wrong with his solution?

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

I have some understanding problem about div1 D. About the 2 conditions, what I think are:

  1. All the colors of edges connected with the same vertex does not show up more than twice.
  2. If vertex i has an edge colored C, vertex j!=i has an edge colored the same C, then the path between i and j are all colored C.

Am I understand the 2 conditions right? And how does these 2 conditions affect the problem ? Thanks.

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

Round Stats

→ Reply