Rockethon 2015 Announcement
By Seyaua, 10 years ago, In English

Hello Codeforces community,

I am happy to announce that Rocket Fuel Inc. will be hosting a Rockethon competition again! The contest is prepared by Rocket Fuel employees Eldar Bogdanov, Anton Lomonos, Lasha Lakirbaia, Alexander Ruff, Nikhil Goyal and me, Ievgen Soboliev. We hope everyone will find some interesting problems in the contest and everyone will have as much fun solving these problems as we had preparing them. Just like last year, the best participants will receive valuable prizes and top performers will get Rockethon 2015 T-shirts! Also, Rocket Fuel is interested in hiring people after this event, so please fill out the simple form during registration.

About Rocket Fuel

Rocket Fuel is building technology platform to do automatic targeting and optimization of ads across all channels — display, video, mobile and social. Our pitch to advertisers is very simple "If you can measure metrics of success of your campaign, we can optimize". We run campaigns for many large advertisers and our clients include many top companies within the following industries: autos, airlines, commercial banks, telecom, food services, insurance, etc. Examples include BMW, Pizza Hut, Brooks Running Shoes and many more!

We buy all our inventory through real time bidding on ad exchanges like Google and Yahoo. Ad exchanges are similar to stock exchanges except the commodity being traded is ad slots on web pages. Our serving systems currently process over 60B bid requests/ day with a response time requirement of 100ms. Our data platform has 64 PBs data that is used for analytics as well as modeling.

Our engineering team is still small (~150) enough for any one person like yourself to make a huge impact. The team represents many top schools in US and outside — Stanford, Carnegie Mellon, MIT, Wisconsin-Madison, IIT (India), Tsinghua (China).

Rocket Fuel has been named #4 on Forbes Most Promising Companies in America List in 2013 and #1 Fastest Growing Company in North America on Deloitte’s 2013 Tech Fast 500 and our CEO George John was recently named “Most Admired CEO” by the SF Business Times in 2014.

My Personal Story

About one year ago I visited CodeForces and saw an announcement of Rockethon 2014. My first thought was "Another competition from a big company, that's nice!". I took part in this contest, performed quite well and recruiters from Rocket Fuel have contacted me and scheduled some interviews. I passed the interviews and now I'm here, in Rocket Fuel.

It has been a nice opportunity to learn advanced concepts of software engineering from a huge amount of smart people working with you. Also, our activities here are not limited only to writing code — we do fun things here like playing basketball, soccer, table tennis. I invite everybody to take a part in the competition and would be glad to hear if any of you thinking about joining Rocket Fuel.

Contest Overview

The contest will begin on February 7, 9AM PST.

The contest length is 3 hours.

The testing of each submission will be performed as soon as the submission is received and the verdict will be delivered to the submission author right away.

The problemset will consist of 7 problems. Each problem can contain from one to three subproblems. Each subproblem will be worth a fixed amount of points. The ties between contestants with the same score will be broken by penalty time which is computed similar to ACM scoring system.

Prizes

The top three contestants will receive the following prizes:

1) IPhone 6 (16 Gb)

2) Participant can choose Apple Watch or Samsung Gear S

3) Participant can choose Apple Watch or Samsung Gear S

The top 150 performers will receive a Rockethon T-shirt designed specially for this contest.

If you are unable to take part in the competition but are interested in joining Rocket Fuel, we will be screening resumes submitted through the special form.

Announcement of Rockethon 2015
  • Vote: I like it
  • +607
  • Vote: I do not like it

Comments Comments (185)
| Write comment?
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Would it be rated ?

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

You might want to move it, it intersects with COCI. In general, if you're planning a contest one weekend ahead, chances are high that it intersects with something.

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

    Thank you for your feedback, we have moved our contest by 1 hour.

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

      would you delay it for another half an hour or at least a quarter? i mean it's really hard to do contests 6 hours nonstop, we would like to have a pee break or something

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

        You're joking, right? 6 hours nonstop?

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

It will be a rated div1+div2 contest... This fact should give a huge motivation to participate in a contest for most CF users, unless MikeMirzayanov changed rating calculation after Good Bye 2014 :)

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

Where are your engineering offices situtated? Your site gives quite a long list of offices but I suppose not all of them are engineering offices. The form you provide on CF seems to assume US to be the location for the candidates, is it correct?

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

    Currently, the only office where the software development takes place is our HQ in Redwood City.

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

America: 9AM Vietnam: 0AM i'll go to sleep at 3AM :v

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

Are there any internships being offered too?

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

    Most probably yes. I work at Rocket Fuel and I was told about a week ago that we're planning to hire interns for summer.

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

    We do offer internships but we do not sponsor visas for internships so if you are not in the US you will be responsible for providing your own work authorization.

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

It's 0am in my country, another sleepless night :D

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

ACM ICPC Rules?

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

like acm format？

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

For registration CV is Necessary. But I have Not Prepared CV yet :D

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

    If you are not planning to apply to Rocket Fuel, you do not need a CV. Please, wait some time for regular registration for the round.

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

Will the contest be according to ACM rules or the codeforces normal round rules ?

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

    "Contest Overview" section of the announcement has already answered the question.

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

A typo in "About Rocket Fuel" section : "commercial banks, telecom, commercial banks"

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

I'm very sorry, but what is TBD?

One of the first results of the search is some torpedo bomber :

Douglas TBD Devastator

Of course, I'm not against the idea of owning a plane, but it seems a little bit strange :)

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

Nice :)

thanks all and hope for nice rating :)

I have a question :)

rated?

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

In the registration page, I cannot upload my CV. Is there any workaround to solve this issue?

Error

UPD: It's worked now :D

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

Backup standings this time :)

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

I'm very sorry, but what is CV?

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

http://bit.ly/1Cv4Zha

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

Problems will be sorted in the order of the difficulty?

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

    Each problem will be worth a fixed amount of points and you'll be able to see these points. And these points are our estimation of the difficulty.

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

A necessary Problem
Rated? ;;)

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

I want to share an idea, That if there is no limit can improve ranking.

If you want to solve a problem for a large N directly you think that increasing N doesn't matter in your solution, submit it to the large N (before testing for small N) then if you realize that its not good enough or some serious bug you can get the small N without penalty.

PS: It work in case you have a brute-force solution for small N, this used to work in Rockethon 2014

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

    You can use this in case there are some not-so-big test in the large subproblem to verify correctness. However, once your code is too slow, you will have no idea whether it is because of big N or the solution itself. Anyway, it's not the big deal if you already have a brute force solution. I would just submit it for small tests and use the small tests to double check my solution for large test (I guess this works since problems are in ACM style).

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

      Actually this was my fault in Rockethon 2014 I missed the big N and also got penalty for small N.

      I took the risk like "Okaye I will get the three sub-problems at once, no waste time for brute-force" .

      Yes, In case you want to go step by step this is nothing.

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

Sponsor visa for full-time job offer ?

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

    Yes, our company will sponsor visas for full-time job offers.

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

"The ties between contestants with the same score will be broken by penalty time which is computed similar to ACM scoring system." — from this phrase I conclude that each wrong submission will be penalized with extra 20 mins, while since this is an individual contest and shorter than ACMs I think that GCJ penalties (4 mins or something in between) will be much better. Is it possible to apply this?

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

    We did the same scoring system last year and it wasn't bad, so I assume that it is completely fine to use it again this year.

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

      On second thought, if someone solves task with 2 subtasks then time is doubled, so 20 mins penalty has lower impact.

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

        Obviously, one always can find some advantages and disadvantages in any scoring system. But in general almost all of them are relatively fair.

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

Your bets, will this contest beat Good Bye 2014 by number of participants?

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

How do the subproblems work? Do we need to make a separate submission for each subproblem?

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

    Each subproblem can be seen as single problem. Yes, you need to make a separate submission for each subproblem.

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

At first : WOW Iphone 6 , cool :D
Later : Damn it tourist has registered.

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

You mean Gold version of Apple Watch? No body's gonna be first :D

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

5

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

rated? (:

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

will "WA/RE/TL/etc on test 1" count?

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

    Because it is ACM style, so i guess they will count.

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

      On Round #289 I've made a WA1 submission and it wasn't counted.

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

How do we check whether a participant has registered or not from the list of all registered participants?

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

    The most simple way I know is to add him to friends and open Friends Only list.

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

    Add them as a friend (by click star next to their name in profile). Then in registration click the friends tab and you can see all of the people you have selected as friends that have registered.

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

    You can add him as your friend and then check it. nic11 and poikniok were faster ..

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

6200+ registrants, sounds great ^_^

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

3 hours before the end of registration! O_O

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

    Since it's ACM-ICPC format, there's no need to put people into rooms (because there are no hacks) and thus there's no reason to stop accepting registrations after the contest starts (except that the late participants lose the time missed).

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

6000+ registrants and full feedback. I'm pretty scared of what the queue will look like, hopefully it won't get stuck :P

Edit: No offence, Mike, but it was kind of obvious that there would be flood of submissions? If you can't afford a good enough system to get so many participants then either limit the participants or don't accept hosting competitions for companies, as now they're getting bad advertising from this contest...

Edit2: At least it was fixed fast enough to not have a serious impact on the results :)

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

    My task A (which submitted 10 minutes ago) haven't been judged. :(

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

    Or we could have a tougher first problem to begin the contest with.

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

Why judging is too slow?

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

    here's my guess:

    1) Since it's ACM-ICPC format, it needs to run all the system tests instead of pretests.

    2) The number of participants is simply a lot.

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

17 minutes in queue for me... Also what happened to problem D1 and D2? It says "Statement is not available." in my computer...

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

I guess you should make it unrated. We have no chance to check if we are correct or not.

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

I've found mistakes in my code and resubmitted my B1 and B2, and my A is still "in queue"!

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

The site is very slow... can I just safely assume that it will be unrated and go to bed? :(

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

I have uploaded my solution nearly more than 10 minutes ago still it is in queue waiting for my submission result.I am very disappointed with that.

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

Shit, I haven't noticed for 40 minutes that my A hasn't been submitted because of server fault =(

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

    I request the organisers to please make this contest unrated being full of unexpected delays and problems.

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

Guys, I'm sorry for technical issues. This time they came from unexpected side. Codeforces services work fine, but nginx (or something else in front of Codeforces) doesn't work well. I'm worry about the issue very much, the more that being sick for a long time I did really good testing and preparation before.

Good news are that it looks quite straight-forward to diagnose it and fix. I'll do it ASAP.

Sorry again, I guarantee you that a work to improve the system is doing every day.

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

    Thank you sir.So is the round unrated?

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

      It should be rated.Codeforces was unavailable only ~1/6 of contest time,its usual for cf.

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

    Amazing! I have seen that at the same time there are at least 50 submissions judged! (Because there are only 50 submissions in one page...) How fast!

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

That awkward feeling when you've found a lot of patterns, but still did not solve the problem.. :|

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

    I hardcoded B1 . saw all the permutations but couldn't figure out any pattern :(

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

    The same thing happened to me for quite a while on B :P

    The real pattern is amazingly simple: start with an empty permutation, now put 1 in either end of the permutation, then put 2 in either end of the remaining blank space, then 3, ...

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

    Is it permutation B2? Because I had that moment too :)

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

    A pattern was floating in front of my minds. But could not code it. -_-

    This feeling is probably the worst.

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

Aaaaand the IPhone is gone...

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

How to solve F?

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

    F was max flow problem.

    • Obviously, we can decide the gender of the "other" one
    • Binary search the answer.
    • Construct graph with 6 layers of vertices:
    1. Source
    2. Males
    3. Empty cells
    4. Empty cells again
    5. Females
    6. Sink
    • Add edges such that, 1 pair of (male — female) correspond to flow with value 1 from source to sink
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you solved it did you do anything special with the max flow? I got TLE on test 92 all contest on it and I don't understand why.

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

        I used Dinic max flow. It was fast enough without any optimization.

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

        There is O(n6) solution. Will be posted in editorial.

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

          Same complexity here. Maximum 2 * N^2 push-flows ina graph with O(N^4) edges which yields O(N^6) solution. Guess the time limit was a little to tight for the general max-flow.

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

            I looked to your code, and I see that your solution has complexity of O(N8). You are calling dfs with complexity O(N4) N4 times.

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

              Oh, sorry. Yep, that's the problem. Thanks a lot :-)

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

      I think you can get rid of binary search here. Instead of binary searching the answer you can add the edges in the order of their increased cost until you get the desired max flow value. The only key difference here is that every time you add an edge you do not calculate max flow from scratch, that will obviously TL. Instead you resume the previous computation of max flow (which can be done quite natural if you use Dinic algorithm for max flow). That should be plain O(N6) with no log factor.

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

        Actually it is O(N8), but the idea is right.

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

          I'd say it's O(N6), I just didn't give away all the details :) There are some tricks there regarding when to run DFS, when the max flow will be increased, etc.

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

            Then your solution is right. Still, I think, you will need to try more than that to get Java solution. Unfortunately, TL for C++ was too big, and TL for Java was too little.

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

      Sigh...When I read this problem statement and realized it can be solved by maxflow, it was 5 minutes left... I spent(wasted) too much time on G3. I thought of the matrix all the time.

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

Why made the example for task D so weak?

I thought "a b LEFT" means b is the left son of a, and stuck for over 1 hour..

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

    "System" tests (at least for D1) were weak, too...

    My brute-force solution passed... even though it stated there is solution for the following input:

    3 3
1 2 LEFT
1 3 RIGHT
2 3 RIGHT

    (which is clearly impossible as 3 would have to be both in the left and right subtree of 1).

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

    same here lol, the statement of task D is really confusing...

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

    yea, thought every node suppose to have 0/2 child... forgot the definition...

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

Can someone tell me what's wrong with my solution got G1? Thank you!

http://ideone.com/x0oF5P

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

    Can you post link, not full code there?

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

      Ok changed. What is wrong?

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

        It is a problem when you post your code like that because it takes a lot of space and disrupts the discussion here, but I would say that -72 is a bit overreacting.

        UPD: I'm sorry... I thought you were asking what's wrong with posting source code like that; you were asking what's wrong in your solution :)

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

    The first problem — K may take a value of 4, but the second index dp [1000] [4] can not. Second — do comparison "dp [x] [k]! = 0.0" is unsafe. Read about comparsion of doubles. Finally, you didn't calc inv[0] — inversion in start permutation.

    My freaking English better than this solution, sorry.. Why dont write easy dfs without any states and get 3 points?

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

Контест будет рейтинговый?

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

What is wrong with my code for problem C? Kidding, can someone tell how to approach it? :P

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

    For each amount of money that the company who won has to pay, you calculate the prop by using bitmask.

    Let fixed the amount of money x. 1. If the winning company bid x unit. Then there has to be at least another company bid the same x. 2. If the winning company didn't bid x unit, the company had to bid higher, and there are also at least one company bid the same amount x.

    Here is my sol: Code

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

    For each possible value v, compute the probability of: 1) [1 company bidding more than v] * [k companies bidding exactly v] * [n-k-1 companies bidding less than v] 2) [p companies bidding exactly v] * [n-p companies bidding less than v] (where p >= 2)

    The probability that the value to be paid is v is equal to 1) + 2).

    In order to compute 1) you can iterate over all companies (to choose the one that bids the maximum amount) and inside that iterate over all subsets of companies (ignoring the ones that contain maximum bidder) to pick the ones who are bidding exactly v.

    To compute 2) you simple have to iterate over all subsets of companies that contain at least two companies.

    The only primitives you need to compute 1) and 2) are p_bid_more_than(company, value), p_bid_less_than(company, value), p_bid_exactly(company, value) which can be computed in O(1) given L and R for each company.

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

    You're a mean minion :P

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

What's B2 TC #20?

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

    I suppose smth to get rid of solutions O(n!), just huge amount of permutations.

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

      I've WA, not TL, so interesting why. I tried to find a case, but didn't.

      UPD. Ok, now I understood: I used to convert too large number to its binary representation using "sprintf" function. Using "bigint" module didn't helped here.

      Ideone gives me the correct answer which equals to that Codeforces expect. 9765553

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

    probably something related to long long int. I got WA on #20 and it went away after I changed "m" to long long int.

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

    Yes, I got WA 20 first and then fixed. The problem for was long long literal type. I did a bit shift 1 << length while it is supposed to be 1LL << length.

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

I'll understand if this is asking too much, but is there any chance shirts could be offered in Tall sizes? Some stores have them, and they're basically two sizes longer. So a medium tall would be roughly M in width but XL in length.

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

    We inquired about this with our manufacturer. Unfortunately, the whole batch has to be either in normal or tall sizes so we'll stick with normal since this is the preference for most people.

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

      Alright, thanks for checking. I have never seen tall sizes be an option at special events, but I hope to see some eventually. Great contest! :)

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

I'm waiting to see what's the magic to solve G3 with complicity like O(n3log(k)), but I saw this:

  if (k > 1000) {
    k = 1000;
  }

In tourist's 9761881.

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

    The possibility will be stable.... I tried to find the matrix A for dp(n-1)*A=dp(n).... But failed.

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

      Yes, I know the reason that could pass is "The possibility will be stable".

      But I still want to know if it is the intended solution (I thought is is not) — if yes, then that's too crazy. :P

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

        This observation is a part of intended solution. But the complexity of intended solution was O(N2·K) (with K capped at something like 10N). Unfortunately, all of the competitors who solved it during the round got AC with much slower solutions.

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

Does our new rating depends on the previous contests rating?

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

Got WA on D1 and D2, because of a == b case.

Very sad.

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

Can somebody explain me in detail problem C and E?

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

    Task C.

    For every guy a, for every guy b ( b != a), for every number (bid) k from range of guy b:

    What is probability that a is a winner and b has second place with a bid k? It is easy if you don't have problems with draws. We can say that with some equal bids a guy with lower index is a winner. With this trick we have easy implementation. my code

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

My solution for D2 was judged as RE because of stack overflow. I thought stack overflow would result in ML, not RE. I tried the same test locally with -Xss64M, and it worked fine. It's strange that you have 256 MB of memory but can't use it for stack.

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

    I can hardly name a resource where stack overflow causes ML, but not RE.

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

    Had the same problem. Looks like java commandline was different from described here.

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

      In order to solve this problem in java you need to construct inorder order iteratively instead of recursively. It is interesting that you don't actually need to change the main algorithm of constructing the tree; it can remain recursively.

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

        I know that, that's how I solved it :). But recursive inorder construction should work too if -Xss64M is set.

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

Why did my submission for G1 print out a crazy number?

http://mirror.codeforces.com/contest/513/submission/9761884

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

    Because MinGW. It cannot print long double, you should convert it to double first.

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

    You can use "cout" for long double...long double is not prepared in printf/scanf

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

I want to suggest that penalty time for problem should be scaled proportional to the number of points it costs, because now if you solve simpler problems you get much more time spent, than if you solved more difficult problems.

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

    You also get more points and points are the main ranking factor. If two people get the same number of points, then you can't say one was expected to take more time than the other.

    Or do you mean the case where you start with hard problems?

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

      I think he means in case of a tie, person that solved 4-point problem has a huge advantage to person that solved 2+2.

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

        But then the 4-point problem should be that much harder to do. Difficulties don't scale linearly with points, so the time needed to solve a 4-point problem may be 10 minutes, contrary to 1 minute for the 2-point problem.

        I'd say it's actually the opposite, when solving hard problems gives you a greater penalty than solving a lot of easy ones, just because the easy ones are so easy. It's similar to the problem with point values for hard problems dropping too quickly with standard CF scoring.

        And I'm not accounting for subtasks here, since that question wasn't raised (but it is an artificial fix and messes things up).

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

Will there be an editorial?

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

4th again. Argh

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

Is there any internship opportunities?

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

thx

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

I wrote my address a moment ago, not recognizing that the information disappeared due to the Black Day of Codeforces. Can I still get a T-shirt?

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

    Same here.

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

    The participants eligible for the T-shirt will need to fill out a separate form (address, phone, T-shirt size) which is not ready yet.

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

[deleted]

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

Has anyone received his/her t-shirt yet?

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

Will there be Rockethon 2016?

→ Reply