When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

robinyu's blog

By robinyu, 7 years ago, In English

Mabuhay!

I am honored to announce Codeforces Round #419. It will take place tomorrow, on June 17, 17:35 MSK.

The problems in this round are written by me, robinyu. I believe it is the first Codeforces round with a Philippine writer. I would like to extend my heartfelt gratitude to kevinsogo, AlexFetisov and winger for their invaluable help in testing the problems, KAN for his endless patience and support in preparing the contest, and of course MikeMirzayanov for the absolutely amazing Codeforces and Polygon platforms.

In this round, you will be helping Karen in her day-to-day routine.

There will be pretty pictures, drawn by the lovely Kazenokaze. Do not miss the round!

Both divisions will be given five problems and will have two hours to solve them. Keeping with authentic Codeforces tradition, scoring will be announced right before the round.

As a matter of course, you are highly recommended to read all the problems; though problems are arranged by expected difficulty, you may find some problems easier than others.

I hope you will enjoy the problems as much as I did writing them!

The scoring for this round is:

Div. 1: 500 — 1250 — 1500 — 22502250
Div. 2: 500 — 1000 — 1500 — 2000 — 2750

Good luck, and I wish you all high ratings and bug-free code!

Update: Congratulations to all winners!

Div. 1 Div. 2
1. Radewoosh 1. TarasSavitskyi
2. yutaka1999 2. ChillingDream
3. W4yneb0t 3. WA_TLE
4. Um_nik 4. TLEwpdus
5. eddy1021 5. Tian.Xie

Special congratulations to Radewoosh for his second consecutive Div. 1 round victory, and to both him and yutaka1999 for solving all tasks!

Thanks for your patience. The editorial has been posted. Hope it was worth the wait!

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

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

VoHiYo anime round VoHiYo

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

finally, a rated round after such a long wait...

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

    is it rated?

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

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

        What website you used to make such great pictures like this? And is the girl customizable? :')

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

        Моя попытка во время контеста: http://codeforces.com/contest/816/submission/27854137 (WA 126)

        Моя попытка после контеста(тот же код): http://codeforces.com/contest/816/submission/27876220 (ACCEPTED) Почему АБСОЛЮТНО ОДИНАКОВЫЕ КОДЫ получают WA и AC??????

        Лог чекера Can't find file C:\Contesters\Work\invoker-prod\work\codeforces2\5fce135e23ca31c3af3931016c4ef202\check-2b11d4eec984eb8ac636a09dfb665d94\run\output.fd0138e687.txt.

        UPD: все исправлено!

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

          I think you should send this to MikeMirzayanov

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

          This error might be somehow connected with your nickname :)

          To be seriously, it's strange bug. I hope you will get your honest rating scores back.

          P.S. And why minuses? People are so agressive to others problems?

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

        My rating was getting around +120, but in the end got only -1

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

Now I know I was right not to let Araragi Karen appear in round #418... in case of possible conflicts.

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

karen i can be your onii-chan

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

Hope for short statements.

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

I never understood why the scoring is announced right before the round if it's always the same...

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

    Not always, actually. There might be minor changes like it was in the previous one (i.e C and D were worth 1750 points instead of common 1500 and 2000)

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

      Why is scoring always announced just before the round, Could anyone tell what was the idea behind this tradition initially ?

»
7 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Woho.. never thought of getting an Anime theme based Round.. Made my day.

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

So we had a Bakemonogatari round and now an anime round. Things are looking bright for CF.

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

Very interesting topic..

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

"...you may find some problems easier than others."

In other words, There will be a math problem at DIV 2 C or D :(

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

Oh, there was no rated round for Div.1 for 27 days!
But today, there is a contest that probably rated for Div.1 so I'm especially looking forward to this contest.

(Previous rated round for Div.1 is Codeforces Round #415.

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

I think all anime fans will participate on this round.

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

    I don't think so. This is not a place where one who is into anime participate the contest just because it's anime-themed. Anyway I haven't ever expected to see a contest involving anime character, great surprise.

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

      Many of my friend (Japanese) says, "I like the character Kujou Karen, so I'd like to participate in this round (Actually I don't know even who is Kujou Karen)
      Another interesting fact in Kujou Karen in competitive programming is KujouKaren in Atcoder is very strong and got 5th in MUJIN Programming Contest.
      So much anime culture in competitive programming... surprised.

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

        Actually, the user KujouKaren in atcoder is me...

        I've tried to register the username KujouKaren in CF but I found that this ID has been used KujouKaren.

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

          You can take the handle in the next new year I guess if you wish as KujouKaren is inactive for 2years and hasn't participated in any rated contest.

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

just informed my friend about the round and he is a big time anime fan.

he canceled his date today :P

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

anime round , sound cool to me .

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

Karen is so cute DA☆ZE~

⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

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

Why can't I register for the contest? The system tells me that I've registered but I really have't. Upd: Fixed

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

nice round ! now i think every one want's to help karen in her day-to-day routine ;D

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

It is a welfare of otuka!!Nice picture.

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

I registered, then cancelled the registration and now can't register again.

(the other computer says that I'm registered)

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

Wow! A writer from my home country :) Congrats to kevinsogo for being top 1 in Google Code Jam 2017 Round 3 :D

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

It will be hard to concentrate on problems.

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

As we know, competitive programming is moemoeSports! I'm looking forward to the CUTE image and clear problem statement!

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

Well, I think I am the only one that watched the entire series of Kiniro Mosaic just because it will be featured on this contest. God bless moe anime.

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

I hope that problems statement very clear.

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

Short description will be helpful everybody.

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

Please I hope no 10 min delays.

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

How about the "right before the round" scoring distribution ?

UPD: Fixed

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

Very unusual Scoring for div.2 :D

»
7 years ago, # |
  Vote: I like it -23 Vote: I do not like it

i know what to comment to get upvotes!

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

Hack page not loading..?

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

is there something wrong with codeforces. I have been trying to submit C for 20 minutes but I couldn't submit. Its like there's no response from codeforces site.

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

    Same happened to me but they fixed it

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

    Please fix it soon. I am unable submit yet.

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

      Go to your contest dashboard. Ask it to the "Ask a question" section below.

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

        thanks man. submitted only 2 minute before contest.

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

edit: nvm

»
7 years ago, # |
  Vote: I like it -47 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

First time opened last problems, because of pics.

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

How to solve D?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +97 Vote: I do not like it
    1. Write brute force solution.
    2. Run brute force on all vectors (0,0,0, ... , 1, ... 0) of length k, to get weight of each individual element.
    3. Recognize the pattern. Even vs. odd n makes a difference, and even vs odd also does, you're looking for patterns depending on modulo 4.
    4. Verify against bruteforce.
    5. Step (optional): Prove the correctness.
    6. Step: Pray that you didn't miss anything.
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I recognized all patterns except n % 4 == 3. Could you please explain it?

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

        If you have n % 4 == 3 and you don't know how to answer it, just apply one step and you have n % 4 == 2 and you know how to solve it.

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

          What you mean by apply one step?

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

        If you could find the patterns for n % 2 then you could transform n % 2 == 1 into n % 2 == 0 by bruteforcing one step.

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

          Could you please improve the explanation? Thanks!

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

            My solution was simple: find the relation for when n is even. If it is odd, make 1 step for it to become even. Note through the drawing below the problem that the operations are still at the same order so you can apply what you found for n % 2 == 0.

            If you had the relation for n % 2 == 1 you could start from n % 2 == 0 and apply the step 3 times, now the operation is the same as starting from n % 2 == 1 (it starts adding) and you can use the relation you have. Other than that kind of stuff, you need to note that each number will influence the answer independently and then do some bruteforce solution to find some pattern from inputs like 0 0 1 0 0 0 0, at least I think almost everyone did that.

            This is straight from my code, it might be helpful to you (it's in portuguese and comb is a binomial coeficient):

            // par -> j par = comb(n / 2 — 1, j / 2) // par -> j impar se n / 2 % 2 == 0 é negativo, se não é positivo // par -> j impar comb(n / 2 — 1, j / 2)

            // impar -> transforma no par e resolve

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

        For odd indices the coefficients are .

        Even indices are .

        Maybe you can find one formula for both.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 9   Vote: I like it +36 Vote: I do not like it

          When you miss the case n=1 and you don't believe on correctness of your pattern

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

      If you manage to recongize one pattern it is enough, since you can build the other in a brute way from the recognized pattern.

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

How to solve Div1B :(

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

    I think to use binomial coefficients. (Pascal's triangle)

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

Is Div1 — B solvable using matrix exponentiation? would also be interested to know other methods. TIA

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

    What will be the transition function? The transition function will change depending on the level we're at. eg: from level 10 to 5 has a different transition function than 12 -> 6.

    In short, according to my understanding, we can't. To use mat-exp we need a consistent transition function, that doesn't depend on level.

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

    I passed pretests by finding pattern of the coefficients (Huh). There were 4 cases, (parity of n, parity of (n/2))

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

      Wow! nice. I was looking for a similar pattern but didn't think it would depend on parity of n/2.

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

Hack for Div 2 C ?

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

Hack for Div2 C?

  • »
    »
    7 years ago, # ^ |
    Rev. 4   Vote: I like it +13 Vote: I do not like it

    Typically, when n > m.

    5 3
    1 1 1
    1 1 1
    1 1 1
    1 1 1
    1 1 1
    
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks My output was 5 and then all rows :/

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

      The answer is 5 row 1 row 2 row 3 row 4 row 5 right?

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

        No, answer is 3 because problem asks for minimal number of moves(I saw it only now).

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

          Omg I missed it too. And most people in my room...

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

        I forgot about the min even though I checked both row and columns :'(

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

          I made the same mistake first but realized it just before the contest ended while testing my own solutions. Managed to resubmit just in time :D

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

        using the minimum number of moves

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

        No: 3 col 1 col 2 col 3

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

      Is it the right answer?
      3
      col 1
      col 2
      col 3

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

      fuck :(

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

      I can not believe this... I knew this exception but accidentally typed n instead of m...

      if(n<m) for(int i=0;i<**n**;i++) for(int p=0;p<dm;p++) printf("row %d\n",i+1);

      else for(int j=0;j<**n**;j++) for(int p=0;p<dm;p++) printf("col %d\n",j+1);

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

    Sometimes you need to start from columns not from rows... Consider a table:

    010 010 010 010 010 010

    My solution because of this was hacked... Bye bye rating :D

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

Div 2 C is from an old Cook-Off

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

    You had an opportunity to solve it in 5 minutes =)

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

      I was making sure , that I dont mess up anything.

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

    Its easier than that . Here one matrix is always all zeroes . In the question you mentioned in your link, the other matrix is different and you need to make both matrices equal . Div 2C is an easier version of that .

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

      Hmm, but can't we apply the same technique on both matrices and compare the residue matrix after all operations? If the residue is same, then they are same.

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

That feeling when you screw up your rating because of one "if" condition in Div1 A :(

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

The Art of the Covfefe

lmao

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

div 2B please ?

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

    I solved it with Segment Tree + BIT. For each given n range, update the range with segment tree. Then for each i from 1 to 200000, point query with segment tree checking whether it is >= k. If it is, then update point i in BIT with +1

    Later, for each query, just do a range query with BIT.

    P.S. I think it's pretty much overkill. Maybe others have much simpler idea.

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

      No need to use BIT/segment tree when all queries are after update.

      Code

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

    Do you know partial sum?

    for i [ 1, n ] arr[a]++; arr[b+1]--

    then find the cum. sum in the arr[].

    and then also do the cum sum in the array to find if the arr[i] is >= k.

    then just ans is for query l to r cum[r]- cum[l-1]

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

Is there the case of the type :

2 1 1 1

(div 2 C)

in the pretests ?

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

HACKATHON COMING

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

How to solve D? Is it involved inclusion-exclusion principle?

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

Div2B is very similar to this problem — http://www.spoj.com/problems/UPDATEIT/

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

    I think they are pretty different.

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

      I used the exact strategy mentioned in the link above . I have done the above mentioned one.

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

Was D variation of pascal triangle or something? can anyone tell what was wrong with my code

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

Can someone tell me what particular cases may occur in div1D? I've spent 30 minutes trying to find a bug and didn't find anything...WA on pretest 4. Has it happened to anyone else, too? If so, how did you fix it?

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

Solved C 3 minutes after ending...

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

How to solve div2 B? -_-

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

    Do you know partial sum?

    for i [ 1, n ] arr[a]++; arr[b+1]--

    then find the cum. sum in the arr[].

    and then also do the cum sum in the array to find if the arr[i] is >= k.

    then just ans is for query l to r cum[r]- cum[l-1]

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

    Solved it with segment tree.

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

    Let's say we calculate 2 arrays:

    int l_cnt[200200];
    int r_cnt[200200];
    

    l_cnt[t] — how many intervals start with temperature t?
    r_cnt[t] — how many intervals end with temperature t?

    Then we can figure out in O(1) the number of intervals covering some given temperature t in the following way:

    int covering_intervals = n - l_cnt[t + 1] - r_cnt[t - 1];
    
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    think about sum A[1...r] then you need to add 1 to [l, r]. 1<=l<=r<=a. think about sum A[1...r-1] then you need to add 1 to [l, r]. 1<=l<=r<=a. think about sum A[1...r-2] then you need to add 1 to [l, r]. 1<=l<=r<=a. You store array D[1...n] Add 1 to D[l], subtract 1 from D[r+1]. And them D[i]=D[i-1]+D[i]. Here you have a prefix array Check if D[b]-D[a-1]>=k.

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

    With Binary Search code

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

      Can you explain why your code works ?

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it
        1. For each temprature check in how many ranges it lies within the range (with binary search explained below)

        2. For all those tempratures whose value is >=k we use prefix array dp[i] = dp[i-1]+1(if its is more than k) else dp[i] =dp[i-1]

        3.now every query can be answered in O(1) time .

        Total complexity is O(nlogn)

        Now to check in how many ranges a tempratue values lie within you can use upper_bound and lower_bound function from stl calculate the lower_bound from the right array as it will return no. of values in right array more than that value , after that we need to subtract those values from the above values whose left index is more than the required temprature so we use upper_bound function , and the difference between the two is our answer , now if it is >=k than we should include it else not.

        obviously , we need to sort left and right arrays

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

My C is failing System Test today :(

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

Canany one give me a clue for problem B? I think solution is binary search but I can't code :(

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

How to solve Div2 C?

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

Of course, a coupon cannot be used without buying the corresponding good Anyone forgot this case like me ? :'(

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

    No, because then you can just use all the coupons :P

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

      No i don't think so what about this case :

      4 4

      2 1

      2 1 1

      10 9 1

      2 1 3

      We can not use all the coupons

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

    If you can use a coupon but not buy the good, Then you can just use all the coupons but buy only the lowest (C-D) items as long as you can. In other words, equivalent to the problem, you have an array of values (equal to C-D), find the max no of items you can buy with sum <= B.

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

Div 2 C was an 99% copy of this problem. MRTNSFRM

Just wrote what was in the editorial.

Edit: Did not notice bhishma's comment.

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

What was complexity of your solution for C? Mine was brute force that works in 0(500 * n * m)

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

    You can do it in if you just find minimum in row/column and substract it. Since max answer is roughly max(n, m) * 500, it is faster. However, your complexity should be totally fine.

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

      I did exactly what you mentioned . Hope i pass system tests . This is my first time that first 3 passed pretests.. Update : I got TLE in 3rd :/

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

    Also you can use DP+priority Queue to do it in (n*m). Link to my code here

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

    Thanks

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

Spent a lot of time on C, found a DP approach, proved the correctness, proved the time complexity is less than , submitted 15 minutes before end of contest and got WA on pretest 3.

Panicked.

Re-read the statement to find out that Di is the discount and not the price after discount.

Phew. Hope it holds.

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

    I am guessing it is similar to the question "Barricades" from "Looking for a challenge" book.

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

I'm guessing div1-E was inspired by Bathroom Stalls from this year's GCJ Qualification Round?

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

    So that's why it looked familiar!! The new 10^18 bounds though...

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

Problem E is similar to Problem C from this year Qualifications Round in Google Code Jam, but this problem was more challenging.

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

Can anybody please tell me, if there is a segment tree + lazy propagation approach for Div2 B ??

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

    Yes, it can be done in that way too but it can be solved easily using prefix array. Look at this code — 27855143

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

    You can just find all temperatures that suit and answer on queries using binary search

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

    Make an array of pairs with size 200000.

    let the first element of the pair as start of some of the given ranges and the second as the end.

    now iterate over all values from 1 to 200000 cumulating sum like the following:

    sum += a[i].first , sum -= a[i].second. but before subtracting the end check if the sum on index i is greater than or equal to K then on another array mark i as true or just 1.

    now build a segment tree (regular segment tree of sum) on the array of marks. and answer regular sum query on it.

    sorry for detailed explanation :D code

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

What a fucking problem D (Div.2) that was garbage :/

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

What is the time complexity of this solution for Div2 E/Div1 C?? Is this O(n2) or O(n3). I think it is the latter, what do you think?

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

    It is actually O(n^2) because for each u, the total number of iterations is the number of pairs(x, y) such that lca(x, y) = u. That sums up to number of all pairs (x,y) in the tree.

    The sad thing is that I thought O(n^2 * log(n)) was fine so I sorted each node's descendants to calculate f[u][i][0] instead of running another DP :(

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

      Yeah that's sad indeed I thought that this solution will be slow so I didnt program that and instead I was trying to optimize it.

      Shit. :(

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

    You can learn about this trick using this problem Barricades whose solution is described here (just download the preview).

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

815E - Karen and Neighborhood is a simplified version of task 3 (OGLEDALA) from Croatian olympiad in informatics 2015 March 28th

=(

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

+12:-2

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

Div2C/Div1A — https://www.codechef.com/problems/MTRNSFRM

Div1E — https://code.google.com/codejam/contest/3264486/dashboard#s=p2 (very similar)

As I know, Div2E/Div1C also appeared in some past contest.

It loks like author is very good at copying problems)

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

160+ tests in problem A X_X

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

    398 tests in problem E O_o Maybe it's E just because of that? :D

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

My last 2 minutes:  I somehow had unused functions (but compiled) that were dependent on my local template :|

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

    That's the closest clutch I have ever seen! Great job at saving your rating haha

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

Sorry, Karen I couldn't help you in Task: C,D,E :(

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

My contest submission status:



The Time and the Memory value is increasing, and I can even make two trapezoids!
That's interesting! :D

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

Very slow system testing :p

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

E peeled of easy binary searches in main and ifs for k=1,2

That's ... unexpected ;p

(this function tells "how many people will be placed on interval (l, r) if l and r are already occupied and people will not move in if distance is smaller than dis or it is equal to dis and their position is > bd)

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

    Taking someone's problem and making it just a bit harder is definitely not the best way to create programming problems.

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

Well... were I more skillful, I'd have solved C easily.

Were I more tactical, I'd have skipped C quickly and would have solved D sooner and probably solved E.

I can't believe I can't solve a task that 100+ ppl can solve. If this happens in IOI, I can put my head through a wall.

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

    That's already well known trick mentioned many times on CF that such dp runs in O(n^2) and not in O(n^3) and solving it in O(n^3) is pretty straightforward

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

      Well...I always solve this kind of tasks using dp on dfs sequences, which somehow don't work(at least I think) on this task.

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 5   Vote: I like it +17 Vote: I do not like it

        What do you mean by that? I do it in a most standard way of doing dps on trees

        Dfs(v) {
          initialize dp[v]
          for child in children[v]:
            Dfs(child)
            merge dp[v] and dp[child]
        }
        

        where dp[v][cnt][coupon] is cheapest cost of buying cnt guys from v's subtree so that I used coupon on v if coupon==1

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

          How to prove the complexity is indeed O(n2)?

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

            Search the comments here in this page...

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

            For each subtree you'll make Size of previous subtrees * Size of this subtree, the sum of everyone of these is the number of pairs of vertices (u, v), so it is O(n^2).

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

        well it works in O(n2 * logn) in this task I guess

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

As a forever yellow, I am very happy about the difficulty of Div1B and Div1C — usually Div1B is somehow clear (save for maybe some implementation challenges), and Div1C is just too difficult. This difficulty distribution definitely felt more fun.

Your mileage may vary, for others this difficulty jump might have been to much between Div1A and Div1B ... what are your thoughts?

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

It's surprising week sample, week pretest and cute image :P

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

was there any better way to solve div1B than observe pattern in this

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

    I don't think so. I also tried to do it like this (but did a mistake in a brute xdd) and people I talked to also did same thing. You can also magically guess what the answer will be and check it manually :D.

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

      I would like to know closed form for n%4 == 3 and n%4 == 0 as well. Will wait for that editorial :)

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

        For it is .

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

        for n%4 == 0 , let x = (n-2)/2 , then the sequence is xC0 , -xC0 , xC1 , -xC1 , ... , xCi , -xCi , ... xCx , -xCx.
        for n%4 == 3 , try to observe nth and the n-1th row , its either [n-1][i] + [n-1][i-1] or [n-1][i] — [n-1][i-1] depending on parity.

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

          Since pattern for n%4 == 0 is really nice one. We can just perform the operation for n%4 times and then use the pattern for the n%4 ==0. One more observation to make is that if the last operation you performed in above step ( to reduce to n%4==0 ) is '+' then now our starting operation in the new scenario will be '-' which is different then the standard problem. Only change we need to make now is to use the same formula as mentioned by @majk but just omit the pow(-1,i) part ( all the values will be +ve if we start with a '-' operation ) my code

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

good pretests for div2 C

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

system testing is too slow! :(

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

Very slow system testing.

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

Am I the only who couldn't hack any solution because whenever I tried to open some solution it wrote that I need to install the newest version of Adobe flash player?

I spent 15 minutes and finally installed new version, but I still was recieving such messages.

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

    I wanted to try hacking 5 minutes before the end so I just gave up after seeing that message.

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

    I always use Chrome but for hacking I use firefox xD (because I get same error and I don't know how to fix it xD)

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

A screencast of my (pathetic) performance.

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

Maybe I should study more math before participating future contests as of late so many DIV2 C,D are using maths. So the algorithms I know are not needed here. I wish I am a math guy lol.

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

Just some complexity checking here. Can anyone tell me why my code runs only in 62ms ? http://codeforces.com/contest/816/submission/27862413 I use 4 nested loops with O(500*n*m*(n+m)) right here. Shouldn't 10^9 at least takes 1 second in codeforces judge?

Thanks.

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

ah i could hack a lot of solutions((  but i wasted time trying to solve D

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

How to solve Div2 D

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

    ans = k0 * a0 + k1 * a1 + k2 * a2 + ... + k(n-1) * a(n-1)
    Corner cases:
    n % 4 == ???:

    1: t = n / 2 — 1;
    Then k = {C(t, 0), 0, C(t, 1), 0, ... }

    2: t = (n — 1) / 2
    Then k = {C(t, 0), C(t, 0), C(t, 1), C(t, 1), ...}

    Other two cases for exercize.

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

:3 , just :3

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

Why so many people (including me) forgot to handle the n>m case (div2 C)?.... and nobody hacked my solution :'( :'(

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

    Mine was hacked 2 minutes before the end... :D

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

the best thing in this contest that the problems was clear and easy to understand thanks robinyu

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

It's over, I have the high ground!

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

Finally I am blue again !!

I hope, I can see pink in future.

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

Finally expert!!! <3

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

Div. 2 C n > m case. RIP.

Sometimes, I just wish. D:

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

When will the next round be?

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

My screencast here (99th place :C)

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

I cant figure out why my code is giving negative output on test 19 for Div1 B. Link http://codeforces.com/contest/815/submission/27857089

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

Can not get any idea about Div2 C..Help needed about realizing the solution of the problem ..

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

    If you fix the number of times you add to the first row, all other variables get fixed automatically. Let no of times you add to row i be ri and that of column j be cj. If you fix r1, cj = arr[1][j]-r1. Now, ri = arr[i][1] — c1. After that you just check if all ri>0 and cj>0 and ri+cj == arr[i][j]. Then it is valid. If it is valid, take the minimum number of steps, which is sum of ri and cj. There are atmost 500 values possible for r1, as 0<=r1<=500 because 0<=arr[1][1]<=500.
    Time complexity is O(M*n*n) where M is max value in array.

    Code

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

In which category does problem C(Div 2) falls in?

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

Had some weird errors during the contest in div2 C. Four five submissions. Please look into it so that it doesn't repeat. submission

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

Can anyone tell me why my C answer is wrong.?

https://pastebin.com/TzpachRc

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

    You want to find the solution with the minimal number of moves. The solution 50 col 1 col 2 ... col 50 consists of less moves than your solution.

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

Nice both pictures and problems

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

ARIGATO GOSAI MASSHH for the round... :D

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

How to prove that the order of making changes in various rows and columns in div2C is interdependent .... Someone plz help i have trouble in understanding....

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

    I mean can't we apply the transformation in any order i.e why do we only need to do the rows first and then the column or viceversa

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

      Each transformation can be represented by a matrix addition. And those operations are commutative.

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

How to solve Div 2 B without a segment tree?

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

    Using cumulative sum.

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

    I used binary search. First, for each temperature you check if it's admissible or not(you can do it just iterating through them and calculating balance of segments) and add it to the array if it is(array will be sorted if you start from t = 1). Then on queries you just do binary search to find the first and the last suitable temperature for current query. My code: http://codeforces.com/contest/816/submission/27853021

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

My screencast

Hope you find it interesting

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

This is my submission for problem A:27853670

It says my solution failed at pretest 10. If i run that on my mac i'm getting the right answer which is 20. Can anybody explain where it went wrong...

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

    You are accessing the strings s1 and s2 but they are empty, which is undefined behavior. That's why it may work on your mac but not with the online judge.

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

My approach for Div2 C:

  1. first calculate minimum element in each row .it denotes the number of operation we can do in corresponding row.and store it inside a vector named row

  2. Now calculate the maximum element among each element we have calculated in the previous step.let's denote it by mn

  3. now for each column calculate its maximum element.let denotes it by mx .Then abs(mn-mx) will denotes the number of operaetion in a column, and store abs(mn-mx) inside a vector named col

  4. now to check for invalid case.make a new matrix lets say ff.each cell(i,j) of the ff matrix will be row[i-1]+col[j-1].if g!=ff then print -1 else answer exit

  5. now to calculate the answer.just calculate the sum of all element in vector row and col lets saya answer is ns1;

  6. Now do the step-1 for column and step-3 for row and store the result inside vectores col1 and row1, and calculate the answer ns2

  7. answer will be minimum of nsand ns2 see modeMy code

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

Ok, I've upsolved Div2C in greedy approach after the contest, but I don't understand why it works! Can anyone explain?

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

What problem B? I didn't understand :(( help me!!!

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

    You are tasked to find the sum of lengths of segments (all their values >= k) within given intervals [l,r] (both ends inclusive).

    This problem is tailor-made for segment tree/fenwick tree. My solution using segment tree: link.

    Of course, a fenwick tree solution is similar but easier.

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

      Your solution is 4 times faster than mine, but I can't understand how?

      Your solution's complexity:

      build: O(NlogN)

      First loop: O(NlogN)

      Second loop: O(NlogN)

      Third loop: O(N)

      Queries Loop: O(Q)

      My solution's complexity:

      First loop: O(N)

      Second loop: O(N)

      Queries loop: O(Q)

      So overall your solution runs in O(NlogN) and mine in O(N), but your solution passed in 486ms and mine in 1933ms.

      My code link

      P.S: I submitted it in practice, does it have any effect.I have seen other's solution there's too takes around 1800ms.

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

        After adding ios_base::sync_with_stdio(0) (that makes cin/cout faster) your solution runs in 670 ms, so it's much closer to 500ms :)

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

I used java for solving 816A. It worked perfectly fine on my computer ( I have JAVA 8 too) but not on codeforces. It gave a runtime error. Following is the code snippet:

//      s: scanner
        StringBuilder in = new StringBuilder(s.readWord());
        StringBuilder rev2 = new StringBuilder(in);
        StringBuilder rev = rev2.reverse();
        //Error starts here
        int rm = Integer.parseInt(rev.substring(3,5)); //ERROR HERE

//

Thing is, if in = "05:39", for my computer rev.substring(3,5) = "50".
However for codeforces, rev.substring(3,5) = ":5".
Hence, for codeforces rev.substring(4,6) = "50", while for me it is an ArrayIndexOutOfBoundError
Can anyone tell me why is this happening?

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

    I tried your solution on 1. "05:39" 2. "05:39 " It showed me the same error on (2), so I guess the test cases have a space character at the end and that is causing some problem.

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

      The scanner is set to stop amd ignore ' ' and '\n'. Is there any other characters I should ignore?

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

        you are using a readline() and your readline() breaks when (c == '\n') or (c = read() != -1), so I guess it is still reading that space symbol. EDIT: your readWord() also fails, just try this->

        if (c != ':' && !(c >= '0' && c <= '9')) in your readLine() or readWord(). This is a temporary fix just meant for this problem. I guess the input has some strange whitespace char at the end which I don't know about. I tried submitting your code with this and it worked! http://codeforces.com/contest/816/submission/27884725

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

          I guess this is the problem. Thanks a lot for your help, I was really confused!

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

    Hello, frag.jdk

    I think i found the error but if you can share your complete code i can be sure about it.

    Here is what i think : the error is the in the rev.substring(3, 5). If you are working with integers and then trying to make a string like if hh = 12 and mm = 55 you create a string eaquals to (12:55) in other word some sort of concat... you will for sure get a run time error.

    Why? imagine you have mm = 59 and you want to increment it to 60 then you which will give you 0. and imagine you have hh = 0 which you will increment to 1 the string will be "1:0" not "01:00" rev.substring have range from 3, 5 which are out of "1:0"'s range.

    I hope i made it clear.

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

I have solved 2 problems and want to know why my answers are skipped, what is the reason???

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

Any idea when will the editorials be uploaded ? Thanks

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

    May be jury doesn't have their own solutions for all of the problems and they are now trying to understand the code of the guys who solved them.

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

Waiting for editorial

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

blackEarth's (North Korea, obviously) submissions times:

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

    Not to mention subtle differences in coding styles in the submissions on D/E (using LL or ll for long long, cin/cout vs scanf/printf, if (x) vs if(x), ...).

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

Please provide the Editorial.

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

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

    Editorial will be uploaded by tomorrow

    I am pretty sure that today is tomorrow for yesterday :D

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

How to solve Karen and supermarket?

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

    Notice that coupons form a tree rooted at 1.

    Then calculate dp[current vertex][total number of goods purchased in the subtree of this vertex][did we apply a coupon for the good in this vertex]. After that the answer will be maximum possible i such that either dp[root][i][0] or dp[root][i][1] is not greater than b.

    Check my code for details :)

    27885164

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

      Thanks! So we are trying to minimize the cost of i goods at vertex v.

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

      Your complexity looks high, close to n^3 :| How did this pass TL?

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

        It's not really n^3, though it looks like so.

        Consider the two for loops for recalculating dp for current vertex u.

        The outer one indicates how many goods you buy from the subtrees of all children of u, that go BEFORE the newly added vertex v.

        The inner loop indicates how many you buy from the subtree of v.

        Thus, the two loops effectively enumerate all pairs of vertices, where two vertices in a pair are FROM SUBTREES OF DIFFERENT CHILDREN OF u, that is, all pairs of vertices with LCA = u. This means, no pair is checked twice, resulting in overall complexity O(n^2)

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

        If I'm not mistaken, the problem "Barricades" from here has much in common with this one. It's proved that the complexity is O(n^2).

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

editorial for problem B?

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

My solution for problem B. Complexity is O(3nlogn + qlog2(MAX)) where is MAX = 200001 or more. So lets first build Segment Tree with adding on segment(with Lazy Propogation) and then when comes each li and ri add 1 on segment li and ri. Then lets create an array of size MAX and for each i from 1 to MAX assign arri its value in first segment tree. Secondary we need to build new 2D segment tree that called merge sort tree on the arr(you can see realization in my code). This kind of segment tree allows us to calculate how many numbers there are in array between elements L and R which are less than any K. Finally when we have query li and ri the answer will be ri - li + 1 - K where is K is the number of elements than less k between li and ri. I know my solution is bad and very crazy thats why i am looking for an other solution. My code: http://codeforces.com/contest/816/submission/27852820 Also i noticed that my solution works when k is different for all queries.

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

    You know, all of your queries are offline... Just use prefix sum array :)

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

      Oh... of course. Thank you very much

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

    you can use prefix sum to solve this problem .

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

Waiting for editorials, Can anyone provide a tutorial for Div2-Problem D?

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

Waiting for problem D div2 solution

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

27897999 div2B. What is wrong?

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

waiting for another contest but none near by :( !!

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

Definatley should have done E instead of D. A similar but harder question appeared in Code Jam 2016 Finals.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sir, very good contest, love thee questions, thnank you