By KAN, 8 years ago, In English

Hi all,

The 8VC Venture Cup 2017 - Final Round is tommorrow at 18:05 UTC. Along with that, Codeforces Round #393 will be held at the same time both for Div. 1 and Div. 2 participants. The Div. 1 Edition will contain the same problems as the Final Round, the Div. 2 Edition will be easier.

Of course, those who have placed in top 200 in 8VC Venture Cup 2017 - Elimination Round should register for the Final Round, all the others should register for Div. 1 or Div. 2 editions according to their rating. All three contests will contain six problems, last two hours and be rated.

The problem authors are Um_nik, Endagorion, sivukhin, pashka and me. Also huge thanks to fcspartakm for his help in preparation, and to vepifanov and AlexFetisov for testing the round. I suggest you reading all the problems to find which one you like the most!

I'd like to remind you about the prizes:

  • Overall 1st place — $2000
  • Overall 2nd place — $1000
  • Overall 3rd-5th places — $500 each
  • Overall 1-50th place — t-shirts with 8VC and company logos
  • Local Winner — Dinner with Joe Lonsdale (founder of Palantir, Addepar and 8VC) and other Silicon Valley technologists
  • Local top finishers — Opportunity to meet with leadership from 8VC portfolio companies

Please welcome one more company became interested in the Venture Cup, Progressly!

Progressly is a cloud-based Operational Performance Management platform allows you to document, collaborate on, and gain contextual insights into core business processes and outcomes in real time.

The scoring is usual in all three contests: 500-1000-1500-2000-2500-3000.

Congratulations to the winners!

8VC Vecture Cup 2017 winners:

  1. V--o_o--V
  2. bmerry
  3. Marcin_smu
  4. LHiC
  5. qwerty787788

Codeforces Round #393 Div. 1 winners:

  1. HYPERHYPERHYPERCUBELOVER
  2. RomaWhite
  3. PavelKunyavskiy
  4. snuke
  5. vintage_Vlad_Makeev

Codeforces Round #393 Div. 2 winners:

  1. Kacey
  2. wcx5tq957i
  3. BekzhanKassenov
  4. Tailz
  5. BitHashTech

Editorial

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

| Write comment?
»
8 years ago, # |
  Vote: I like it +54 Vote: I do not like it

That's funny, my dad and Joe Lonsdale are really close friends, I get to meet Joe all the time. :)

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

Before Joe Lonsdale started 8VC, he worked with my dad in the company: formation8. Sadly, they split up! My dad started a company that has "formation" in it, and Joe started a company that has, "8" in it! So cool!

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

    Joe Lonsdale company make codeforces rounds, your dad's company don't, perhaps that's why they split up :V

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

      They used to be in an investing company together. They were like best friends. They were the founders of the company, they worked together.

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

    fair division!

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

How do I register if I qualified locally but am not in the top 200?

Also, I go to the same high school Joe went to ;)

»
8 years ago, # |
Rev. 2   Vote: I like it -54 Vote: I do not like it

Div 2 edition will be rated? UPD1: It is rated, it was unofficial at first thats why I asked.

»
8 years ago, # |
  Vote: I like it +205 Vote: I do not like it
"Local Winner — Dinner with Joe Lonsdale"

This Silicon Valley entrepreneurs think they are the big shit. Someday, I'm going to organize my own programming competition and I will invite the winner to meet me in a tea party in Crimea.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it -49 Vote: I do not like it

    I agree, I'd like to do the same lol. :)

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

      Snowden offended Barack Obama as well. He's got big balls.

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

I see the option to register for the Final Round, but I didn't place top 200 in the elimination round. Is it normal?

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

    yap!

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

    There are some people who are currently registered for the final round but did not place in the top 200 in the elimination round, so I'm guessing the option appears for everybody.

    The CF admins probably just assumed everyone would register for the correct round. I'm not quite sure how the incorrect registrations will be dealt with, so you should just register for the Div 1 version.

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

      Could you give me examples? We have some exclusions because of local finalists.

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

        I'm a local finalist but I still get the "you can't register" message.

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

          Please try again. Anyway no reason to worry, for sure you'll be registered correctly.

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

        kyleliu is an example. His rank in the elim round was 852

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

        In the list of recently registered people I found a few users who did not list their locations as from the USA (I'm assuming local finalist means from the Silicon Valley area), but it's possible they have moved. Here are 2 examples: ctzsm dojiboy9

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

      When I clicked on register button , it's showed me that I am not eligible. So that's not a problem at all.

»
8 years ago, # |
  Vote: I like it -61 Vote: I do not like it

Rating will Dowa?

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

Hope another exciting contest, interesting problem set :)

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

Contest postponed by 10 minutes?

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

Delayed !!

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

Why delay?

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

Damn, contest delayed by 10 minutes.

»
8 years ago, # |
Rev. 3   Vote: I like it -55 Vote: I do not like it

Please ignore this comment.

»
8 years ago, # |
  Vote: I like it -40 Vote: I do not like it

tourist GK hope u will 1st today , best of luck . zscoder u are just awesome zi song

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

    hoping is for us. he is first normaly

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

R.I.P. English

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

am i the only one failing to understand problem c statement ?

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

    I've read it multiple times and I still don't understand what the questions wants :(

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

      the only way is to submit wrong and wrong til it gets pretest passed !

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

        The question could have definitely be worded better. Everyone who doesn't how barbecue is made is going to have a tough time to understand it.

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

Will you upload English statements?

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

Unable to understand Div 2 C. Never cooked barbecue. :/

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

Awful contest, problem B in russian was not full, so i couldn't solve it. Hope it will not repeat.

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

Awesome contest, hope that i will pass system tests.

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

    What was your logic for C?

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

      Imagine it's a graph. You need to make it into a single cycle, and have an odd number of bs. If you have x > 1 cycles, you need exactly x operations to transform them into just 1 cycle, and then 1 more operation if the sum of all bi's is even.

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

        My bad I visualized it in terms of components.

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

        Why is the number of 1's should be even? Why is this bad b[4] = {0, 1, 0, 1}?

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

          Basically, after traversing the cycle, we need to up at the same node in the opposite direction. Only then it can visit all n positions in both directions.
          Even number of 1s will always lead to same direction after traversal.

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

          If you start from a node, and walk exactly N times, you should end up in same node because ending graph should be one big cycle. Then, it follows that you can't have visited a node more than once. If you start at node X, and when you again visit it after N times, the sum of b[i] encountered is 0 mod 2, your state hasnt changed, meaning you're going to repeat the exact same cooking(no reversing really occurs).

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

          Even number of ones means that by the time each skewer makes a full round and returns to its original spot, it will have been flipped an even number of times, meaning it will be in the same position as it started, which is not good since we want it to be in the flipped position

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

          Imagine a cycle with any number of nodes n.

          Now, if you start at a node say x, then you will travel in this order :

          x -> y -> .... -> x

          So, once you start at x, if the total number of inversions of the skewer is even, then you will end up at x with the same direction of the skewer because any change made in the direction will be reversed also. So, even if you traverse this cycle multiple times, you will reach each node with the same direction.

          But, if there are odd number of 1's, then after 1 traversal of the cycle, you will reach x with the opposite direction of the skewer as to what you started with. Now, with another traversal of the graph all nodes have had both the directions.

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

      The graph is combination of cycles, you need to make graph a single cycle. And if there is even number of 1's you should change something.

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

      I counted the number of cycles in permutation and then calculated the number of changes we need to make in order to combine all of these cycles into a single cycle.
      If all of the numbers in b were zeros I added 1 to the answer.

      This approach is failing at test 8. Either my logic is completely wrong or I made a mistake in my implementation.

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

        Your approach will fail for the following case.

        3
        2 3 1
        1 1 0
        

        Correct answer is 1, not 0.

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

    Oh no, tl on 80 test.

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

Will Div 1 and Final Round results be combined for the rating calculations or are those calculated separately?

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

    This won't. There would be a combined contest for div1 and div2 if that was the case.

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

The Contest was good, spend a lot of time on B but still unable to come up with a solution...

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

    Binary Search on answer.

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

      what was the right limit? (the left limit was 1, sure)

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

        I used M i.e number of pillows given as right limit.

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

          code I used Binary search. but it didn't succeed.. Can you please see my code (what is wrong)

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

      Can you explain your logic for div 2b ?

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

        First give everybody a pillow. Then binary search from 1 to m to see if you can give the kth position some r pillows. You can easily calculate how many pillows required in O(1) [just give the (k-1)th and the (k+1)th hobbit r-1 pillows, the (k-2)th and the (k+2)th hobbit r-2 pillows and so on..this can be calculated with the knowledge that sum of all elements from 1 to n = n*(n+1)/2 in O(1)].

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

      Binary Search was not necessary. You could brute-force by computing the number of pillows that you need for the answer to be at least 1, 2, 3... until p, where p = max(n-k+1, k), and then you could divide the number of remaining pillows (if there are some remaining) by n and add the result to p to get the answer.

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

        I did it the same way. Any idea what the complexity would be?

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

good contest

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

Me when I read div2C

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

    I need some SAT Reading skills to understand this problem :))))

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

How to solve D div1?

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

    Hint* Dynamic programming + binary search

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

      I guess I need some extra hints :)

      Also are you sure you aren't talking about Div1 B?

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

        So sorry, missread

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

        Try solving the problem "Find the number of distinct subsequences of some string S (of any length)". You can use similar ideas to solve D.

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

      Div 1

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

is there anyone who passed div1 D with 26*n^2 solution instead of n^2 ? because if there is then #%#%@#$@#@

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

    Yes, it runs in 1300ms. Use int instead of long long and do if (dp[i][ii]==0) continue;

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

      Strangely, this gave TLE with C++11 and passed in 1263ms with C++14. Never knew C++14 had so much better optimizations.

      C++11

      C++14

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

      Never would have thought there is such a big difference in speed between int and long long.

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

    Mine failed

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

    I did, 1900ms.

    edit: And yeah, I also spent 30 minutes optimizing it..

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

    I did, but I solved that in 13 mins and then have been optimizing it for 20 mins. I needed to change a bit flow of my algorithm to gain better use of cache and erase my beloved macro "#define int long long" and it passed in 748 ms. Maybe that cache thing was not necessary because deleting that macro sped up my program from 3,5s to 750ms on CF >_>...

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Did almost everyone else do ON2)? I just wouldn't imagine this passing along with modulo operations. I did waste some time figuring out how to reduce to O(N2). I did like D as a problem though.

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

      You can do the dp in O(N2) by using a prefix sum table.

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

    I did, with no optimizations at all. It passes in 1840ms.

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

    Got it passed in 1.5 seconds.

    The code running O(n2) times was the following (3.5 seconds locally on a random test):

    code 1

    First, branching gets in the way of instruction-level parallelism. So, get rid of branching by switching f to int64 (it was int32) and taking the remainder in an O(n2) outer loop (down to 3.05 seconds):

    code 2

    This was still not enough: my compiler is dmd which sometimes produces suboptimal code. Locally, this is already fast with gdc or ldc, but they are not present on Codeforces.

    So, the next thing was to streamline accesses to the transition table (1.55 seconds):

    code 3

    This looked fast already. But I added manual loop unrolling, just to be sure it happens (1.3 seconds):

    code 4

    Overall, the optimization effort took 5.5 minutes between the two submissions (one, two). Actually solving the problem took way longer for me.

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

How to solve Probelem E? Is that sth like keep the value of sum for each suffix,-1 for pop and +1 for push, and query where the last sum which is exact 1 is?

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

    I used segment tree with lazy propagation (range add update & max query). Add -1 to [0, pos] if pop, 1 to [0, pos] if push and do binary search to find the rightmost positive number. O(n lg^2 n)

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

      We can also get rid of binary search by can starting from the root and going to the right child if it's maximum is positive. It's O(N log N) this way.

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

      Um, I'm confused, Why do you need lazy propagation for this?

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

      ..... I came up with this idea and then forbade it.... that's too stupid

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

struggled to debug div1 B for 40 min because of misreading 1440 as 1140 T T

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

    Same here. I had WA 6 and was looking for a bug, but only looked at the 1440 place after your comment :(

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

Problem F: wow, such idea, very insight.

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

    Can't agree more. Who thought it is a good idea to put it on a contest? On ACM it wouldn't be that bad because we will have more time and I will have mnbvmar in team, but as a most valuable problem during a 2 hour CF round it sucks hard.

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

      It is good when people complain only about problem F

      At least problems A, B, C and D weren't bad which is not the case for many other contests

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

        EDIT: I refer to problem E here :D.

        Not sure whether this comment was sarcastic or not, but if you really want to than I also think that bignums is a lot of fun, especially when TL is very strict (I didn't solve that problem, but heard that from friends), so that you can't use Python.

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

          I solved F without using any bignums.

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

      I think W4yneb0t's comment is sarcastic.

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

    (Want to get my -100 comment)

    I'm the author. What is the problem? Swistakk is also welcomed.

    bignums is a lot of fun

    Really? It is a problem about bignums?

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

      The problem is that arriving at the solution is straightforward and the difficulty lies entirely in coding it. I personally don't find that very fun.

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

        Wow. I was thinking about 2 hours on how to avoid O(n2) for case 1 - 10n. You are very smart person.

        And when I was writing then solution about a half of the time I was sitting with pen and paper.

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

      Lol, I referred to problem E when telling about bignums xD. Should have mentioned it :D.

      F is surely not about bignums, but I don't like F because it has very low ratio of "difficulty of getting idea right : difficulty of coding it" and that is more or less what I use to sort problems by how fun they are. We need to parse everything (hooray) and what is left to do is to make some rules producing (length of expression mod P-1, value mod P) for every expression. Only rule which I didn't figure out was those intervals, but I didn't think about it for longer than 15 seconds, but I guess it still can somehow be done without some brilliant ideas.

      Btw, I do not predict your comment to get downvotes ;p.

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

        E: Division bigint by int isn't very hard, is it? Also I think that there is something else in this problem (not only bignums) and this something is what the problem about.

        F: Well, I added this parsing part to 1) combine some ideas in one problem 2) make it harder to code. But yes, the only hard part is those intervals and yes, it still can somehow be done. Maybe not brilliant but some ideas are needed.

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

          F: Then maybe the part about the intervals would make a good problem D or E.

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

            I get your idea that "all this other stuff like parsing and other operations are kinda boring" and I partially agree. But it was hardest problem in a not usual round (finalists should be stronger, right?). So I decide to add some coding part (but you should agree that parsing is relatively easy in this problem).

            Maybe it is just unusual to see "parsing" problem in a short individual competition.

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

              "(finalists should be stronger, right?)" — do you expect tourist in round called "something's final" to be stronger than tourist in a usual round ; p?

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

                Good point :)

                But rounds are made not only for tourist. Also I've expected much more AC for problem E. I'm sorry that E appeared to be more difficult than I've expected.

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

          E: Surely, E is pretty OK, this problem is by far not straightforward (however it is easier if you are not a retard like me and read that sum of b's is <=3e5). And dividing bignum by int is indeed lot easier than typical division, I thought that much more involved operations will be needed which led me to disliking this problem prematurely. Probably that problem without bigints wouldn't make much sense, so their existence here is very well justified.

          F: OK, if you say it took you 2 hours to tackle the case 1 - 10n then I guess it is not easy, so it significantly increases ratio I mentioned :p. However I wouldn't call parsing "combining some ideas in one problem", that's very nice expression for that ;p.

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

For DIV2 -C , I am counting the number of cycles and if they are != 1,I am adding it to the answer. I dont know how to handle the second array consisting of 0's and 1's. Any hint?

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

    if the bitwise xor of all bi is 0 then you should add 1 to the answer

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

    Parity

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

    If my idea is correct, you need to have an odd number of 1's in the second array

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

    If the sum of b[i]'s is even, 1 more operation is needed.

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

    Just count the sum of ones, and if the sum is even, add 1 to the answer (you need to flip 1 bit), if the sum is odd it's ok.

    The sum of the flips has to be odd because once you make 1 cycle, if the flips are odd, the next cycle every piece will be flipped, but if the sum is even, they will pass every cycle with same orientation.

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

How to solve Div1 D?

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

    Similar to counting number of different subsequences

    Here you need subsequences with distinct adjacent symbols and for each k you should count how many such subsequence you can have with length k

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

      Well I got that we can transform the problem to counting different subsequences, but I do not understand why do we need to find this number for every length. Can you explain in a bit more details.

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

Understanding A-B div 1 took me the whole contest a even now i can't even understand the samples.

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

Nice taskset, but could anyone explain how to solve Div2E?

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

Can anyone explain, how to solve Div2_C?

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

    Count the number of cylces in the graph, if the number of cycles > 1, then add that number to the changes.

    Furthermore, if the number of 1's in the second array is even, add 1 more to your changes.

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

      How does that works for this test :

      7

      2 3 4 7 6 1 6

      0 1 0 0 0 0 0

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

        The case would be invalid since array p needs to be a permutation.

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

        Your pi values don't include 5, so this isn't a valid input.

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

      I understood the cycle part during contest... however didn't get the part about even number of 1's ... please explain why even number of 1 won't work

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

        If you have an even number of 1's, by the time a skewer gets back to its original position, it will be in the same orientation as it was, however if there are an odd number of 1's, it will get to it's starting position in the reverse orientation.

        Idk how good that explanation was, tell me if you need me to come up with an example.

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

          Your explanation is great, but an example would be even more awesome :)

          I still have difficulty visualizing how all this permutation stuff works.

          Let's give names to 5 skewers: a, b, c, d, e. Rotated skewer a can be named as A. How will this original configuration change with time?

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

        Imagine the skewer that starts at position 1. If pi makes one big cycle, then after n steps, this skewer will be back where it started. At this point, we would like the skewer to go through all these positions a second time in the opposite orientation. This only happens if it ends up back in position 1 after being flipped an odd number of times.

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

I think understanding problem C was a harder challenge than solving it. (I made barbecue before but u know, it was horrible ...) Also I think preparing sth like A is not good because sb don't know about English calendar so they can't solve it as fast as other people!

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

Does anyone have any hack cases for Div. 2 A?

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

    I used m=2 and d=2 to hack one solution.There was off by one error in his code

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

    try these tests:

    input:

    7 6

    correct output:

    6

    input:

    3 6

    correct output:

    6

    input:

    1 5

    correct output:

    5

    input:

    4 1

    correct output:

    5

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The problems' statements weren't easy. I can't understand div2 D till now.

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

before 8VC cups. i would like to change my color.(to yellow(i was too close)).

8VC cups changed my color, but to blue :/.

why !?! ;_;.

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

After I clicked on someone's solution on the Hacking panel, the solution turned red/ green. What does that mean? I couldn't find that in any FAQs.

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

    red is solution that you read last.
    green are all other solutions you read.

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

A moment of silence for those very few people who failed the system test :D

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

    really sad when we use correct logic but just a silly = sign ruins it all up :|

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

I had trouble understanding the problem statements (especially Div2 D), but the questions were really fun! Really happy about finding the DP solution for D.

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

    do you mind sharing your approach for D? (div 2)

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

      Sure!

      First of all, imagine that the time ranges on the tickets work backwards (ie: buying a 90 minute ticket at time 100 covers all trips from times 11 to 100). Then, for trip ti, we would like to calculate the minimum cost ci. There are three options:

      1. Buy a ticket for one trip. This costs ci - 1 + 20.
      2. Buy a ticket for 90 minutes. Use a binary search to find the earliest trip tm that would be covered by this ticket. This costs cm + 50.
      3. Buy a ticket for 1440 minutes. Again, find the earliest trip that happened in the past 1440 minutes. This costs cm + 120.

      Total time is because of the binary search at each step.

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

      Another way is to do exactly what statement says.

      	vi a(n);
      
      	for (int & t : a) cin >> t;
      	vi his(n, 0);
      
      	his[0] = 20;
      	cout << 20 << endl;
      
      	for (int i = 1; i < n; ++i) {
      		his[i] = 20;
      
      		int paid1 = 0;
      		for (int j = i - 1; j >= 0 && a[j] + 90 - 1 >= a[i]; --j) paid1 += his[j];
      
      		if (paid1 + his[i] > 50) {
      			his[i] = max(50 - paid1, 0);
      		}
      
      		int paid2 = 0;
      		for (int j = i - 1; j >= 0 && a[j] + 1440 - 1 >= a[i]; --j) paid2 += his[j];
      
      		if (paid2 + his[i] > 120) {
      			his[i] = max(120 - paid2, 0);
      		}
      
      		cout << his[i] << endl;
      	}
      

      No DP, no binary search. 144kk operations worst case = 500 ms.

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

        Maybe I'm misunderstanding your code, but this looks like DP to me — you're using the previous outputs (his[j]) to calculate the latest output (his[i]). Nice that there's no need for a binary search, though.

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

          thanks both of you, I understood the question now. I was trying greedy so couldn't get sample case 2 correct.

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

          Well formally this is DP. But, come on, sum[i - 1] - sum[j] would be real DP :)

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

        That is definitely DP, and instead of binary search, you just do linear search, so wouldn't work for slightly tighter constraints :)

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

    Now it will send you into space :)

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

Nice time limit in E.

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

    My solution works about 350 ms. Have you ever heard about numbers in base 109?

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

      Once or twice. Look at times of AC's, they're kinda close to limit. But I know, that it's fair, one limit for everyone and things like this...

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

      TL of 1s is fine if the intended solution is 350s but bigger difference would be better (why not?), unless there exists a solution in slightly worse complexity that you wanted to fail. Also, I would say that the ratio TL/intendedSolutionTime should be bigger in problems with small time limit, because simple things take more percent of time there (e.g. reading or iterating over 1e6 values). Though, now I think that I don't consider such things/aspects myself when I'm choosing TL :D

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

        Don't get your point. Suppose that reading takes time X. So we are probably interested in ratio (because X is independent of solution). . The lesser TL is, the greater will be.

        Also, I've consciously chosen TL to fail solutions like Radewoosh's one.

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

          Your calculations are correct but I meant something else. You may assume that reading is constant but sometimes there are many ways to do something simple — so simple that participants don't care about it. For example, pushing numbers from the input to a vector (it's slower that writing to an already allocated array/vector) or using set instead of vector & sort & unique to count different values. So I meant a non-constant X that matters more for small TL. Also, I would expect bigger language differences for times close to 0 — I wouldn't set TL 0.1 if the intended solution is 0.03.

          Also, I've consciously chosen TL to fail solutions like Radewoosh's one.

          Ok, it explains an unusually small TL. I don't think choosing a good base for calculations was important in this problem but I won't argue about that (your decision was fine IMO).

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

            1 second isn't an unusually small TL for me.

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

    Codeforces exceeded time limit when going through all the zeroes in hardcoded constants in your code.

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

Upsolving!!!

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

    waiting for problems to added in practise.

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

Is there a time limit after which you can see other's solutions ?

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

Can anyone suggest how to solve Div2 B?

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

    binary search the answer. allocate the answer to k. allocate k-1 to adjacent guys etc etc.. if not able allocate, search for lesser answer.

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

    try to use BinarySearch :)

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

Will these problems be added to archive, and when?

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

So I was trying to access the problem for practice and suddenly this happened. Some kind of bug or hidden feature? o.O

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

Div-2 D is written so badly . I am still not able to understand it. Can any one help?

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

    discussed here! already

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

    The analogy of trip was badly written I believe. The trips are instantaneous are point in time so to say. So if trips happen at 1 30 50 minutes. its better to take a 90 minute ticket/pass than 3 individual tickets.

    so I was doing.. min( dp(i-1)+20, dp(last trip 90min ago) + 50, dp(last trip 1440 ago + 120) ) etc.. Finished coding 5 mins after contest end :(

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

      Yeah, I thought this was a little misleading.

      I understood the question as:

      • You only pay for a bus ticket when you board a bus, and the length of the trips don't matter
      • The ti values are the times when you board a bus
      • The 90 minute ticket lets you pay once and board an unlimited number of buses for 90 minutes
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        If only the problem could say these words, I would have been better rated today :P

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

Waiting for rating update...

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

    Only few people have their ratings updated till now like tourist. Does the process of updating take too much time??

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

      Rating of Final Round participants is updated, not other two.

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

      i think there is a problem with the site right now.i see the updated rating of tourist when i open a profile and the previous rating when i open the contest section on profile.

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

        They are looking for cheaters before computing rating. There are definitely no cheaters on the onsite event, so they have immediately calculated rating for them.

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

When will be editorial?

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

Thank you, C++, for being so tolerant to typos...

  • if (sums[left >= time]) -- passed pretests(!), WA 21
  • if (sums[left] >= time) -- AC
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why the hell codeforces hides comments with too many negative votes? They are more interesting for me :D

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

Congratulations to winners!

The onsite participants only standings page is available by the link http://codeforces.net/contest/756/standings?list=2c7ac9b338b4906db6d101641a3b06b4.

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

Codeforces rating system is kinda odd. If I had participated in div 1 round I would got a good increment (like +50), but with final round I get only +4. If there is no mistakes then the only conclusion I can make is not to participate in small-amount-of-participants rounds in future.

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

Still waiting for rate changes

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

Div1 version: Few failed systest, few hack attempt (and no successful hack), and few active participant (391 active of 656 registered) :/ Fortunately the problem is not bad :)

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

I want t-shirts but I forgot participating in elimination round lol

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

    You would have got 1000 dollars if you participated in the right contest and your problem is the T-shirt? :)) I think CF should implement a system such that you can't register at the wrong contest. And now, just for the record, was it possible for unqualified contestants to take part in the official round?

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

      I hadn't participated in elimination round so it was impossible to participate in final round. (Because I hadn't placed in top 200)

      I know I could have got $1000 if I participated in both contests. It also makes me sad but t-shirts are more (because 50 participants won them)

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

Who are the local winners?

»
8 years ago, # |
Rev. 4   Vote: I like it +34 Vote: I do not like it

I wonder,how fair is it to a guy , who attain 7'th place (world wide) in Codeforces . And gets 195 minus rating ..

It even hearts me :'v

And I also sometimes wonder how it feels to be tourist . :)

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

very good contest