VK Cup 2016 — Round 3
By Errichto, 8 years ago, In English

Hi everybody.

The VK Cup Round 3 is coming (exact time).

The duration will be longer than usual, likely 3 hours.

As usually in VK Cup, there will be three contests — div1, div2, official one. All of them are rated. Div1 and div2 versions are for individual participants, not for teams.

Setters are Radewoosh, Errichto and qwerty787788. I think that (some) problems are extremely interesting and I really wish I could participate. Thanks to GlebsHP and MikeMirzayanov, we wouldn't have a round without them. Also, thanks to AlexFetisov and winger for testing.

We will later inform about the final duration. Maybe we will inform about the number of problems and scoring.

I wish you great fun and no frustrating bugs. And Limak wishes you good luck!

UPD

  • The contest will last 3 hours.
  • ADJUSTED POINTS DROP — Points will decrease with such a speed that submitting a problem at the end would give you the same number of points as in standard 2-hour rounds.
  • I updated testers above.
  • Top50 in the "Div1 Edition" contest will get t-shirts. Have I already said "I wish I could participate"?

UPD 2

There are 9 problems. Div2 gets problems 1 - 6, and Div1+R3 gets 3 - 9. It means that there are 4 shared problems.
Division 2: 500 750 1000 1500 2250 3000
R3 & Div1: 500 1000 1750 2250 2250 3000 3000

UPD 3

Enjoy the editorial

UPD 4

The system testing is over. Congratulations to winners. Later I will try to put winners here in some nice format.

VK Round 3 Div. 1 Div. 2
1. subscriber, tourist 1. Endagorion 1. .o.
2. eduardische, Alex_2oo8 2. eatmore 2. Herzu
3. riadwaw, Kostroma 3. ikatanic 3. co_farmer
4. LHiC, V--o_o--V 4. JoeyWheeler 4. TDL9
5. KAN, vepifanov 5. rowdark 5. polingy
Announcement of VK Cup 2016 - Round 3
  • Vote: I like it
  • +327
  • Vote: I do not like it

Comments Comments (126)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it -24 Vote: I do not like it

Now my comment doesn't matter, just ignore it :3

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

G

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

Did you forget to mention AlexFetisov!?

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

" Maybe we will inform about the number of problems and scoring. "

Don't worry, that is not important :D

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

Hope to have some Small & Precise & Easy to Understand Problem Statements . And I like the Contest hosted by Errichto most . And I love Errichto as a person.

Hopefully this will be an interesting Contest .

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

Last time (on vk cup round 1) only "Bear and Chemistry" was mine and nobody was able to solve it. I hope that this time you will perform better. :P Good luck from Radewoosh!!! :D

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

What an original picture: http://codeforces.com/blog/entry/17690

UPD: (oh, looks like it's also visible only in Russian version of the post)

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

Can't wait to see the new points System hope this contest is even more fun than the last two :D

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

you said "extremely interesting"

That mean:

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

It will be rated ?

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

    Finally... There he is

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

      It's not nice to get out of tradition :3

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

No more fogotten tree:)

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

"Top50 in the "Div1 Edition" contest will get t-shirts" .

So div2's are not human?!

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

    Why should strong div2 participants have better chances for a t-shirt than medium div1 participants? Also, t-shirts for div2 may cause cheating (div1 guys participating with other accounts).

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

      At least making a combined round makes more sense , bringing everyone to compete for t-shirts is a better choice.

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

        become div.1

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

        I agree that combined rounds are good when it comes to prizes. Though, there are other factors then. Two important ones are that (1) problems may not fit such a round at all, and (2) hacking is more random.

        Maybe div2 participants should treat usual rounds as a fight for t-shirts — good results will allow them to compete in div1 contests with prizes.

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

    Ehm, yes. The idea is the 50 best guys gaining T-shirts. If you are in div.2, you cannot be the best by definition.

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

      You can have 1899 rating, after a failed contest, where you got -250

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

        If you are good enough to get top 50 in div 1, it's extremely unlikely that you would ever drop to div 2.

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

          but a lot of strong div1 coders take part in official Round3:)

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

        Unlucky man. But it is your fault.

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

Just curious — if someone qualified for round 3, but decided to participate in div1 mirror instead of main round, in case of making into top50 there he'll get two VK Cup t-shirts?

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

bug or feature?

there is 88 teams and 168 participants...

UPD: for now 73 teams and 134 participants, looks real:)

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

    No, there are teams with a single participant.

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

      Or some participants are in many teams.

      EDIT. Maybe as an organizer I shouldn't make fun in comments. To make things clear: my comment isn't serious. #politicalcorrectness

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

    I already reported that "bug" (also seeable in unofficial contests). I once thought that the number in the "Contests" page also involves people that unregistered later, but I may be wrong.

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

i'm already registered in DIV2 round but my name doesn't appear in registrants list ?

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

Is there a problem with the registrants page? Cause on the contest page it says:

But on the actual page it says:

Hoping the 2500 number is accurate but would there be a problem with contestants that aren't on the registered page? Would they be able to submit in the contest?

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

I was outvoted to post the scoring. So, check out a new update (in the blog).

EDIT: someone is working on the registration issue.

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

There is a bug with showing participants list, and may be it's something legated with teams

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

The difficulty jump from Div2 D to E and F seems huge... Kinda sad that speed and hacking is going to determine most of the Div2 results, even if it seems like I'll be at the top of the 4-task-solvers.

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

Complete problem D and thinking about sleep :)) :))

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

I made someone angry and then...

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

    Yup we were in the same room.... I don't know what was on his mind....he tried to hack mine too a lot of times!

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

      Likely one of those guys like .o..

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

      I think it's clear he wasn't happy with his perfomance and he "hacked himselft out of the contest". If you have negative score, the contest is unrated for you, or at least it used to be that way.

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

        It's not true. I've checked it today? Effect? -120 :)

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

          Yes, it seems they changed that. I think this a much more reasonable policy. But there should have been a notification about this (I searched and didn't find it anywhere).

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

            It never was like you describe. Even having an ultra-negative score always affected your rating.

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

              Okay. Sorry for mixing things up. I was definitely mistaken. Don't know how I came up with that, I was sure I had read it somewhere.

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

                I've also heard about it. Maybe there was such a bug (feature :D) a long time ago. We should probably ask Mike whether it's just a social myth

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

What is the hack for Div2D?

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

What was the hacks for Div2A and Div2B?

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

    Some guy in my room was outputting 2^(max — min — 1) and that passed pretests.

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

I didn't even submit a single problem and there it was the lock button for problem B. Must be a bug.

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

What's the idea for div1 C?How to calculate the expected value on a interval?

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

    P.S. didn't get AC on C, but I think the cost function is correct

    cost(L, R) = cost(1, R) — cost(1, L — 1) — sum_of_1/a(L, R) * sum_of_a(1, L — 1)

    idea: cost(L, R) = t_L / t_L + (t_L + t_(L+1)) / (t_(L+1))... =t_L * (1 / t_L + 1 / t_(L+1) + ..) + t_(L+1) + ...

    which then becomes much easier to see

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

    let :

    S1[k] be sum of T[i] for i = 1:k

    S2[k] be sum of 1/T[i] for i = 1:k

    S3[k] be sum of S1[i]/T[i] for i = 1:k

    then the expected time to finish the interval s->e is S3[e] — S3[s — 1] — S1[s — 1]*(S2[e] — S2[s — 1])

    from that we can turn it to a dp + convex hull optimization problem ...

    PS : my code fails test 14 — I should practice convex hull optimization more :'(

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

How do you avoid floating point errors with 1C/2E?

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

    Don't use any epsilons. Use long doubles if you want to be more precise.

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

      Why not epsilon? Is this a common problem (that you shouldn't use epsilon)?

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

        Why would you use epsilon here? What would you try to avoid/achieve?

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

Please allow practice.

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

    After the system testing.

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

      Please start system testing =)

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

        Mike and/or Gleb must work a bit after each round, to manage hacks and any issues. I'm sure they don't try to be slow to annoy all participants. You must wait a bit. In the meantime, you can check the editorial.

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

The B,div 2 is maximum bipartite matching?

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

    Nope, it's much simpler! The lower problem in each pair must be the div 2 problem. You just need to find the maximum div 2 problem and the minimum div 1 problem, then take the difference.

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

In div2 D, input :

7 11
2 4 7 3

output
2 7 1 3 5 6 4
7 1 2 4 6 5 3

Why is this output incorrect ?

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

    There can't be road between a and b.

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

    Edge 2 — 4 is present in the second line.

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

    In the second line, the 2 and 4 are directly connected by a road (right next to each other). The problem statement said that was not permitted.

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

    You can't have roads between A and B or C and D.

    You have road between A and B in second route.

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

    There can't be direct edge from 2 to 4.

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

    There shouldn't be a road between towns a and b. In your second line of output you has got such road.

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

After one hour and solving the first four tasks, next two hours were like a fishing. I was trying to catch some wrong submission and I didn't manage in it :)

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

I'm sure you are all wait for the system testing. So maybe you have time to give the feedback. Which problems were good/bad and what could be better? Something too easy or hard? Too mathy? Too not-mathy?

Someone already said that there was a big gap between div2D and div2E. It may be true. Do you agree? Other opinions?

Seriously, your feedback will make future contests better.

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

    I think B problem shall be C and C shall be B in div 2 contest .. thx at all

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

    yeah , there was a big gap ... but I liked the div2 E problem :D

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

    Yeah, it seems as though there was a ginormous gap between the two. I didn't really think much about the E problem though because I've never been able to solve an E problem during a contest. I went straight to try hacking :P (although I wasn't very successful).

    In general, I liked all the other problems though!

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

    Duplicating my russian comment in english: it would be nice to have a DIV1 C subproblem, which could be solved in O(nnk).
    There were a huge difficulty jump between AB and the others.
    UPD: so, if you are not red, then after solving AB problems in 30-60 min, there is nothing to do in remaining 2 hours, except reading other problem statements and trying to hack someone :)

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

    it would be great if you lower the accuracy of DIV2E/DIV1C and rejudge all submissions :'D

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

    I was stuck at Div1 C so I didn't read Div1 D, however it seems that Div1 D was seriously underestimated. Before system test, judging by successful submissions amount — it seems to be the hardest problem.

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

      I was also thinking that Div1 D is simpler that C, and started it, but only 10 persons solved it so far in all 3 contests >.<

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

    [TL;DR] => too many queries / expected value ;)

    [Div 1] Two first problems were like a warmup, almost everyone solved them.

    But then? [A, B, . . . . . . . . . . . . . E, C, F, G, D(wtf) ]

    Looking at the problems :

    *easy problems *

    -Shieet, expected value.

    -Oh god, queries.

    -Expected value!!!11

    -Hidden queries.

    -Even more queries!!!

    My opinion: Too many queries and expected value :) And almost every one of the C — G problems required DP (maybe with maths) , it is always nice to see a varying problemset with flows / graphs / strings (or even geometry ^^).

    This is only my opinion, please don't dovnvote just because you don't agree with it ;)

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

      The number of upvotes you got means that many agree with your comment. I see that there was too much DP, and maybe too much expected value. But I don't understand one thing — what is wrong with queries? Is it that they make a problem less elegant and nice? Because not all problems with queries are about the same topic.

      Would the following version of 643E - Bear and Destroying Subtrees be better? It has no queries (does it make the problem nicer?). The tree is given and there are no queries at all. We consider removing each edge with prob. 1/2. What is the expected value of the height after the process, modulo 109 + 7.

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

    Yeah,there was huge gap between these problems.In addition C was too easy , I think it would be better if it was problem B.

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

      Imo C is harder than B. Only problem with B was a bit overcomplicated statement :)

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

    In my opinion, the pretests for problems which greatly affect standings (for today's contest, it's all problems after div1B) should be nearly identical to final tests, that is to say all corner cases should be present. It's definitely a frustrating bug to drop 70+ places because

    for(int j=1; j<i; j++)

    should be

    for(int j=i-1; j<i; j++)

    Before you say "but what about hacks", I'd like to point out pretty much nobody is going to hack a problem with more than a few lines of code. Indeed, there were no hacks on C, D, E, F, or G of div1 contest.

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

      I think that we tried to make pretests strong in hard problems. I think that the only exception was a problem about the expected height of partly-destroyed subtree. (There, I thought there would be hacks requiring big value of MAX_H.) About which problem are you talking?

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

        I failed Div1 C because my DP formulation considered splitting n levels into more than n parts, which obviously causes bad things to happen. Any test where n = k and n >= 3 will cause my program to output a value smaller than n. Adding two characters would fix this :(

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

          It's hard to be so careful about pretests. Still, I see your point and I'll try to consider it in the future. Thank you.

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

    In division 2 C, why was index written in brackets. All the while I thought only about index of the lowest tied color :| Rank dropped by at least 200. :(

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

    This isn't that important, but I would prefer if the problem statements seemed more "natural" in some sense, maybe something that I would naturally be interested in, not too contrived statements, etc.

    I thought A was OK in this respect. B was ehh, the condition that ab, cd aren't edges is slightly unnatural. C was pretty unnatural, in the statement of the game, etc. I didn't try D, E, G so no comments here.

    F is a decently natural statement I thought, if you think about the problem mathematically.

    Tell me if I confused you...

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

      It's a very important thing in my opinion. Statements are a huge part of the contest. Initially, in B there was something like "Limak wanted to get from a to b. Unfortunately, there was no direct connection. So, he will be late anyway for some event and at least he will take a long nice walk. He then went to b, visiting all cities during his walk. On the other day, ...". It's easier to understand the story but the cost is that the statement is (much) longer. The current version is much shorter than the previous one, with some background. I was advised not to write long statements for this contest and I think it's better. For example because some people aren't fluent in English. So, maybe shorter precise statement is better than longer natural one. But still, I left some story. I will gladly hear more opinions about it.

      But generally, it's hard to invent only natural problems. I can do nothing about the fact that C was unnatural for you. I thought it's still better that only definitions ("split sequence to maximize the score defined as ..."). But some problems are just artificial. I know I will never be able to produce only non-artificial stories and problems (enough of them to make contests).

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

    I was expecting to solve more of the problems and it just feels bad to solve 2 and one of them didn't pass system tests, so I got a beautiful 1 problem accepted. I think that is because the difficulty gap between first 2 and all others was too high, if there are going to be 7 problems, I would expect the average to solve 3-4, if there are going to be 5, then 2 or 3 is nice, I just think that a minor mistake shouldn't move you more than 100 places, or 170 in my case, around half of the people that participated in div1.

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

    It would be interesting to know: is "34 accepted solutions for D-G problems" near with expected estimation of AC ratio for this problems before contest?
    What is ideal AC ratio in your opinion? (e.g. A 50%+, B 25%+, C 12%+, ...)

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

      It's hard to estimate these numbers before the contest. I'm only sure that we considered div1C (CHT) and div1D (Fanpages) to be easier than they turned out to be. I think that the number of AC's in other problems is fine.

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

Please enable upsolving immediately after systests...

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

How to solve div 2, C ?

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

Can anyone explain the idea of recalculating all of the probabilities in Div1 E? Thanks

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

Impressive performance of .o. in Div2! My NBHEXT expects +401 for him >_<

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

    Wow! So accurated! He did +411! O.O

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

round was rated or unrated ??

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

    It is mentioned in the blog post. "All of them are rated"

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

My solution in Div1C adds each of n lines in CHT after calculating DP for some k.
How to prove that the best line for i (when I calculate dp[i][k + 1]) will not have some index j > i?
It is not obviously for me but it passed systests. I even tried to change the order of addings but it didn't pass pretests :D. Or maybe weak testcases are the reason of my Accepted :D? 17793170

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

    We have dp[i][k + 1] < dp[i][k], and . I'm not sure this is sufficient to show more rigorously that adding further indices will not affect the answer, but it seems to make it intuitively clear.

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

    For your CHT you need to put lines in increasing by angle of line order.

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

My Div1-C timed out since I was using cin for input. Changed it to scanf and passed. :(

cin : http://codeforces.com/contest/674/submission/17792111

scanf: http://codeforces.com/contest/674/submission/17797745

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

Its happened first time with me this is my Div2 D soln which was hacked — > http://codeforces.com/contest/673/submission/17796235 after contest i submitted this code again — > http://codeforces.com/contest/673/submission/17798097 ( which got accepted ! and the test case on which my code was hacked seems to give correct result ) Am i missing some thing or is it just my hard — luck ??? → Reply

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

    You've sent 2 solutions, and the second one (last one) was hacked

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

Waiting for Rating Changes.....

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

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

My todo list before todays contest.

Facepalm the point "Convex hull trick" is in my todo list for a several months and I failed today to solve C although I come up with a right DP.

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

    Do you imply that you didn't yet learn CHT? sorry if I'm acting stupid

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

Lol

→ Reply