Melnik's blog

By Melnik, 5 months ago, translation, In English,

Hello everyone!

This Sunday July 2, 19:05 MSK rated Codeforces Round #422 (Div. 2) will be held.

This time I'm the only one author in contradistinction to the Round 415. Many thanks to coordinator Alex netman Vistyazh for help in preparations of the round, Vladislav winger Isenbaev, Alex AlexFetisov Fetisov, Nikolay KAN Kalinin and Ildar gainullin.ildar Gainullin for testing the problems and also to Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platforms.

As in the Round 415, the main characters of the tasks will be the stunning girl Noora and hacker Leha.

Participants will be given six problems and two hours to solve them. As always, participants from the first division can take part out of competition. Scoring will be announced before the round.

I hope you'll enjoy my round. I wish everyone good luck and high rating!

UPD1: Note that the number of tasks which would be proposed for the solution has been changed.

UPD2: The scoring for this round is: 500 — 750 — 1250 — 1750 — 2250 — 2500.

UPD3: Congratulations to the winners! Editorial will be posted soon.

Div. 2:

  1. Nisiyama_Suzune

  2. cephian

  3. Cherish

  4. Irina_Rog

  5. ColdSu

Div. 1:

  1. natsugiri

  2. Um_nik

  3. KrK

  4. irkstepanov

  5. _Reborn_

Special congratulations to natsugiri, who is the only one among all the participants who coped with all six tasks!

UPD4: Editorial.

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

»
5 months ago, # |
  Vote: I like it -48 Vote: I do not like it

Really looking forward to this round! //Why always stunning girl Noora and hacker Leha... (codeforces round 415)

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

    N** coincidence, why not? You'll feel like making "Tommy" do all sorts of interesting/ridiculous things if you do more problemsetting.

»
5 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Is it rated?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Not for you bro

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why? why? why? T-T

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

      Why do you talk to yourself? Are you so lonely?

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

    till now yes.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    В связи с последними событиями очень актуальный вопрос

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

    I want to ask it too.The past two contests are both unrated!

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it -6 Vote: I do not like it

      I'm so tired.

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

        don't worry this time it will be rated and try to learn some new things from each and every contest instead of thinking about ratings and all.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          Rev. 4   Vote: I like it +8 Vote: I do not like it

          I'd like to go to sleep if this is unrated.Then I will have a virtual contest.

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

            The virtual contest can let me learn some new things too.

»
5 months ago, # |
Rev. 7   Vote: I like it -9 Vote: I do not like it

UPD: I miscalculated it. I'm so sorry for inconvenience.

I think the time and date link is incorrect as it differ from the remaining time.] written in contests page.

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

Hopefully this time it will be rated ;D

»
5 months ago, # |
  Vote: I like it +66 Vote: I do not like it

tourist is registered and everyone is excited!

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

    He unregistered!

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

    He unregistered now, or he isn't registered basically his last visit was 6 hours ago before which is before the registration opened. Looks like you just want contributing points :D

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

      snowden.exposed

      Nice try detective, but that "Last visit" thing doesn't work well.

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

      why would a fake account wants contributing points though?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Then why I can't see tourist in the registration list?

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it -64 Vote: I do not like it

    ...

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it -23 Vote: I do not like it

      He is fond of contribution, I think he comments from this account then upvote his comment form other accounts, as I realized immediately when he write a comment he got +3 or something like this, which gives more chance to upvote him after seeing that tourist is registered and the comment took +22 before checking if he if really registered.

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

    He ranked 5 in SnackDown 2017 Finals today the 3 top are 1-Um_nik's team 2-anta's team 3-jcccccccccccccccccccccsb's team

    check Ranklist here

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

we hope it be rated and no issues during the round after two consecutive unrated round

»
5 months ago, # |
  Vote: I like it -33 Vote: I do not like it

Is it unrated?

»
5 months ago, # |
  Vote: I like it +184 Vote: I do not like it

Schrödinger's round: it's both rated and unrated until it ends

»
5 months ago, # |
  Vote: I like it +58 Vote: I do not like it

Two consecutive rounds unrated, i think codeforces should be more cautious!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    The last round was just the author's luck though, nothing could have been done to help.

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

      what? having a false solution to a problem is luck? I am not saying the that it is the author's fault, but being cautious does help in such situation, so why do you think that it is luck?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes.I think it is a luck because you can learn from it.

»
5 months ago, # |
  Vote: I like it +69 Vote: I do not like it

I can only imagine the pressure on author.

»
5 months ago, # |
  Vote: I like it -280 Vote: I do not like it

Round #422=Registration x422

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

    Soon it will be Round #422=Downvote x422

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it -10 Vote: I do not like it

      Soon the blog post rating will be 422! Great!



      UPD: It's now +416. Soon it will be 422 or more!

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Hope this time nothing to be happened to make this round unrated !

I participated in the last two rounds, in spite of Eid occasion. One of them was at the night before Eid day in our country and another was one day after the Eid day. Though my friends and relatives were enjoying and gathering by themselves with other stuffs, I participated in the contest in stead of joining with them, because I love to do contest. But unfortunately both of them became unrated !

»
5 months ago, # |
  Vote: I like it +202 Vote: I do not like it

I speak through memes.

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

No mistakes in jury's solutions, please

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

For the First time, i am Not Excited for Hat-trick .

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

after the round :D

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

Hope that this contest will be bugfree and rated even after contest unlike last twos.

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

My plan for evening: Mexico — Portugal Contest Germany — Chile

»
5 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Hope there will be no problem with any of the problems. :-)

»
5 months ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

GL & HF ?

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Hopefully history won't repeat itself...throwback to unrated #420 and #421 :(

»
5 months ago, # |
  Vote: I like it +78 Vote: I do not like it

Hmmm.. This doesn't look legit :D

From today's contest registration:

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

    Attack on acloser season 1++

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

    Ban everyone!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it possible to make User-Id using loop?

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

      If not then that guy had all the time in the world to create these lmao

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

      Codeforces has CSRF and XSS protection which supposedly should prevent anyone from running a script to send data to the server from the outside, so that lad must've had gone through lots of trouble to make those accounts XD

      Or he's really smart and he could turn around the system and find some sort of a vulnerability that let him do that.

      Either way it took him some serious effort :3

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's the gain on creating multiple dummy accounts ? Altering the quantity of people that have submitted something wrong, and in that way boosting your rating income?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    76 likes, it seems all the acloser liked this.

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

Hopefully no more server slow problems.

»
5 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Many thanks to coordinator Alex netman

Has KAN resigned?

»
5 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Exciting score distribution :D

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

My first contest in a long time.. good luck to everyone!

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

I have faith in pedrodelyra... he is a monster

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

wow great,after a long time six problems. Hopefully all problem statement will be shortly. Thanks.

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

Problem A: I shed a tear :'

(no emoji)

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

I am not able to see the source code for hacking.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    You should use glasses Maybe You can see !! :D

»
5 months ago, # |
  Vote: I like it -23 Vote: I do not like it

WA #3 preliminary test set C. C seems so easy!

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

Is there something wrong with hacks of A?

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

Pretest 2 D is killing everybody

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dp f(i)%=MOD before calculating f(i)*t^(i-l)

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

How to solve C? I had a O(n*log(n)*log(n)) approach using segment tree and binary search, but I thought it wouldn't pass. Is there a better approach?

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

    I used adjacency list + BS.

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

    EDIT: failed systests. two pointers

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

    You can sort by difference between l and r (sort by cost in case of equality) and then use two pointers to iterate your array .(runs in O(nlog(n)) )

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you elaborate on your approach . I tried this way only . the sorting logic also exactly same but i got WA on pretests.

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

        EDIT: This failed systests. this might help http://ideone.com/BU1KjQ

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        well, after sorting , you start with i=0 and j=n-1, and while(i<j) if (difference(i)+difference(j)==x) you compare cost(i)+cost(j) to your current answer(initially=oo) and decrement j (j--) (since there can't be a better solution if you increment i). and if (diff(i)>diff(j)) you decrement j and if (diff(i)>diff(j) you increment i. here's my code: https://ideone.com/avXw3e

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use a segment tree with min query and you can do it in O(n*log(n)). You don't need the binary search.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was using Binary search to find the elements which do not overlap, and segtree to find the minimum in them, I don't know how do I avoid Binary search here?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Use a segment tree with MAX_SIZE positions and put the item on its L. You'll get the ranges (0, current L — other size) and (current R + current size, MAX_SIZE — 1).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used array of priority queues

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

What is the hack for div2B?

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

    many people code like this

    they don't limit i+n-1<=m

    for (int i = 1;i <= m;i++)
       for (int j = 1;j <= n;j++)
      {
    
      }
    
    

    so hack is

    4 4
    abcd
    eeab
    
»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E ??

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D? O(nlogn) would be TLE :(

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

    Apparently not. I used a prime sieve and submitted at 1:59 and got pretest passed. (if only I had gotten it earlier though...)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      WT!!? I thought it will get TLE and didn't submit :((

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

        http://codeforces.com/contest/822/submission/28233115

        actually, I think it's O(N), not n log n, my bad. (because the number of primes less than any N approaches 1/N for large N)

        Since the prime sieve only has to go from 0 to 3000 (about root 5000000), it doesn't take a long time

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Now that I think about it, I have no clue how to calculate the complexity of my code.

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

        A prime sieve is O(nloglogn).

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        also, even if it was N log N instead of N, it would probably still pass because it only works out to ~120m operations

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

    Mine passed in 1240 ms. Hope it passes system tests too.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Mine too, but it didn't pass systests :(

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Mine passed in ~700 ms.. So guess it will run..

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

    F[n] = F[n / x] + (x — 1) * n / 2; Where x is smallest prime factor of n.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is the smallest prime factor optimal ?

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

        Idk, maybe because of comparisons sorts you try to split it into less parts and try to get to nlogn rather than n^2.

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

        Let's prove that if you can get p or q such that p * q is a divisor of n you want to get the smallest one. If you get the cost of the p and q operations you'll get:

        //pairs(p * q) * n / (p * q) = n * (p — 1) * (q — 1) / 2 this is making p * q

        //pairs(p) * n / p + pairs(q) * n / (p * q) = n * ((p — 1) + (q — 1) / p) / 2 this is making p and later making q

        After one of those you'll use the best of n / (p * q) so you can ignore it. It is easy to see that (p — 1) * (q — 1) >= (p — 1) + (q — 1) / q always so from this you see that you'll always take prime factors. Now, if p <= q, (p — 1) + (q — 1) / p <= (q — 1) + (p — 1) / q because q — p >= (q — 1) — (p — 1) >= (q — 1) / p — (p — 1) / q so you want to get the lowest.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it +4 Vote: I do not like it

      What?

      I got

      f(a) = (f(a/sf) + a/sf * f(sf))

      where sf is the smallest prime factor of a.

      You accomplish this by breaking it into a/sf groups of size sf.

      EDIT: Never mind, these both end up giving the same expression.

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

    I got pretests passed for O(nlogn) in 545 ms, hope it passes system tests too...

    EDIT: Passed system tests. Phew.

    EDIT EDIT: Never mind, looks like my solution wasn't O(nlogn)

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

When u get problem C and then rejoice but then with 15 mins left get hacked and get sent plummeting down :'(

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

Hack for C:

2 4 1 2 1 2 3 2

For A, one person in my room explicitly tried to compute the factorials of both A and B. I was unable to hack him for (N, M) = (12, 10^9), because overflow probably led M! to be equal to 0 at the end, but I got him with (N, M) = (11, 30)

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Start system tests quickly this time please!

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

May somebody please explain how to solve Problem C without getting "time limit exceeded?" Thanks in advance!

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

Since the round is done, would anyone mind sharing how they solved C? :(

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

    Loop through all the sorted start and end points and if it's an end point, add the length and cost to your set, and if it's a start point then check all the end points before the current coordinate (in the set) to match the 2 lengths together.

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

    For every length store costs and left border in vector. Then sort these vectors by left side and cost. And for every element do binary search. 28224027

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn! I never thought to use binary search! That's pretty neat

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

    EDIT: This failed systests. sort by duration of voucher and use two pointers method. works in O(nlogn) due to sorting. it passed pretests, hope it will pass systests as well. http://ideone.com/BU1KjQ

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    1. Create arrays for vacations of each length.
    2. Write all vacations into corresponding arrays (l, r, cost)
    3. Sort each array by vacation start date.
    4. For each array create a corresponding array of the same size and write minimal vacation cost for all vacations which start from x or later.
    5. Now iterate from 1 to x (length of your first vacation). Length of corresponding vacation would be x-i.
    6. On each step you have to find minimal price of second vacation (of length x-i). Because you sorted your array you can find it using binary search (also note that we use calculated suffix minimums here).
    7. On the end of each step update your answer.
  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    O(n) solution for C: 28224212 It passed pretest. But it didn't passed System test :(

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

      What is your approach?

      EDIT: I don't think it could be solved in O(n) you gotta atleast sort man.

      EDIT2: Ok I guess it could be done in O(n)

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

Problem D: Was there anyone getting wrong answer in pretest 2 ?? I don't know what's wrong with my code :(

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You should check for 32-bit integer overflow

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you done the operations MOD 1e9 + 7 ?

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

      Yep, I am also doing the modulo operation. I think I have figured out the problem. Actually , I was miscalculating he f(n) for odd numbers. I was using f(n) = (n*(n-1))/2 for odd numbers. But it seems the correct value is f(n) = f(n/x) + ((n/x) * ((x*(x -1))/2) , where x is the smallest prime factor of n.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is the same for even numbers

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For prime numbers in range, is the only possibility (n*(n-1))/2 ?? (where n is prime number)

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

        let z = small[n], is the smallest prime factor of n, let h = n/z, then ans will be

        Spoiler
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Mod the value of dp[i] or F(i).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also fell down on the second test. Then I noticed that I forgot my answer by modulo after each addition.

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

    If you are updating f[i] from f[i / p] (where p is the smallest prime divisior of i) and i >= l and i / p < l , f[i] would update incorrectly.

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

Can anyone explain the solutions of E and F?

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

    Hi, I had an idea with hashings, with some greedy steps for problem E. The general idea is to keep the matched segments in some stack and remove those segments when a better one appears. Below the steps:

    *Let's say "size" is equal to the sum of length of your segments in every step. *For every character "i" in string "t", and with current position pos = 0 in "s" do this:

    (1)Look for the ith character of "t" in s[pos... n], take the first ocurrence, let's call this position "k" in s.

    (2)Check if the largest common suffix of s[1,2,...k] and t[1, 2, ...size + 1] can replaced some stored segments on your stack.

    (3)Remove segments of the stack that can be replaced by the largest suffix.

    (4)Updated pos, size, Repeat until pos = n

    Finnaly if you got the whole string "t" in "s", you will need one aditional check if some substring at the right position of "pos" can be a better suffix for t.

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Is suffix array required in E?

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

2 minute silence for all those(including me) who initialize maximum answer to 1e9 in C

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

Idea behind D ?

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

    It can be proved (I simply bruteforced), that at it stage it was optimal to take the smallest group possible.
    Given this, you simply computed the answer with help of memoization and a prime sieve to prevent TLE.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah. That is what I want to know. How to prove this ?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I computed 50000 values and it worked. You can easily proof that taking 2 prime numbers is better than taking their product, and then generalize. I haven't written any strict proof but someone might help.

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

          Okay, maybe because we want to keep numerator small, we will greedily choose smallest prime

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You have to notice that one prime will never be in divisor. So which prime should this be?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Lets compare it with comparisons sort :D When you do smaller groups you achieve O(nlogn) rather than O(n^2) :D

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Lets say what n=p1p2...p_n. We need to show what we choose p_i in order of i.

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

    I did like this. For any n, the optimal choice is always a prime factor. To prove this, it's enough to prove that its better to choose X for N and then Y for N/X rather than choosing X*Y for N.

    F(N) = X*(X-1)/2 * N/X + Y*(Y-1)/2 * (N/X)/Y + F(N/XY) in the first way.

    F'(N) = XY*(XY-1)/2 * N/XY + F(N/XY) in the second way.

    Its simple to prove F'(N) > F(N) for any X,Y > 1 (Just rearrange the terms, do some math).

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But it's not necessary that X and Y will be chosen one after the other. Yes, all of this is very intuitive, but nothing solid.

»
5 months ago, # |
  Vote: I like it +56 Vote: I do not like it
#include <bits/stdc++.h>
using namespace std;

int main() {
    bool uDoWell, isRated;
    cin >> uDoWell;
    if (uDoWell) {
        isRated = false;
    }
    else {
        isRated = true;
    }
    cout << isRated << endl;
}
»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

just in case Rank predictor

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone help me with my code on C...I was getting WA on pretest 5. But I used exactly same logic as people have discussed here. Thank you..

»
5 months ago, # |
  Vote: I like it +32 Vote: I do not like it


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

So, in D, is the optimal f(n) simple greedily doing N/2 * [ p1-1 + p2-1 / p1 + p3-1/p1*p2 + ..... + pk-1/(n/pk-1) ] ? I can't formally prove why it will be lowest, although seems like it can be.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    F[n] = F[n / x] + (x — 1) * n / 2 Where x is smallest prime factor of n. Lets say n is composite: n=p*q. When F[n] = min(F[n / pq] + (pq — 1) * n / 2,F[n / p] + (p — 1) * n / 2, F[n] = F[n / q] + (q — 1) * n / 2) When F[n/p] = F[n / pq] + (q — 1) * n / 2 When F[n/q] = F[n / pq] + (p — 1) * n / 2 From this you somehow prove that you need to choose first smaller of p, q.

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

What a Thrilling Contest!

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

Anyone with O(n) solution for C?

»
5 months ago, # |
  Vote: I like it -11 Vote: I do not like it

i commented and asked why are we not getting ratings and contests added up in our graph ?? and my contributions went to -1

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

    I'm not sure, but if your comment rating is in [-5; 0], cf will show this rating as 0, but will count real rating when calculates contribution

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

I submitted an nlogn solution for D(I know it can be improved), but currently it doesn't appear on the standings and on the status page, my submission got TLE on test1(wtf). Is there someone else facing a similar problem?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution's complexity doesn't depend on l, r. If your solution runs like 1400-1500 ms it can get tle when rejudged I think.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think almost in the same way, but it is unfair if you receive tle on test 1, because it shouldn't pass pretest(it would give the possibility to modify my solution, instead of switching to other problem). As you said, my solution doesn't depend on l, r. So, if it pass pretests, it must pass systest, because the computations are almost the same.

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

        It's only a prediction. But if you choose to write solution that runs on edge, I think you are relying on your luck.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

what is the time needed to calculate the rate?

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

keeping small numbers as an input in pretests would have given a chance of successful hacking attempt on Question A

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

No plagiarism detection between DIV 1 participants and DIV 2 participants??.Saw a few same codes.

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

Although got WA in C due to initializing of maximum answer to 1e9 and D due to some silly mistake but still best contest in last 1 month ,waiting for more rounds by author

»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Actually, anyone mind sharing what E's test 24 or its general idea is? A lot people get WA'd but the case is too long to be read or copied.

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

    I think this.
    Note that dp[pref1][ans][flag] doesn't work

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's pretty unexpected. I originally thought about some edge cases, but did not ponder too much on the algorithm. Thanks a lot!

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

can anyone pls share solution of D?? (I was getting wrong ans on pretest 2 inspite of using the prime numbers concept to form groups)

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

    Didn't see where you're using t. You count not t^0 * f(l) + ..., but 2^0 * f(l) + ...

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for pointing that out i will try and resubmit in practice section..

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check your code if there is overflow because of int. At first , I got WA on the pretest 2 too. But after changing "int" into "long long int" , I got AC.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, you can see the test cases here for yourself.

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

    http://codeforces.com/contest/822/submission/28234001 My solution for D, developed minutes after finish of contest (spent whole time trying to solve C). Idea is: to calculate, for example, f[40], maybe optimal is to have 5 groups of 8 people, so using just prime numbers does not work. Firstly, lets set f[x] = x*(x-1). Thats always a solution. Then, lets iterate from i = 2 to i = r/2 + 1. Inside that loop, iterate from j = 1 to j = i. Update f[i*j] : f[i * j ] can be solved in two ways: 1. way either you have i groups and j people in every group, then f[i*j] = i* f[j] + f[i]
    ( if you cant understand: i times you solve groups of j people, and then you will have i "winners", so you solve one group of i people). Since i and j are smaller than i*j, i and j will be computed by this time. 2. way similar, just opposite, j groups of i people. So f[ i * j ] = max ( i*f[j] + f[i], j*f[i] + f[j], f[i*j] ) Third way if f[i*j] is already better than going with i or j. So you just calculate all values, and then sum from l to r, and must be careful about modulo.

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

So.. Does D could be solved in C#? It seems I've used asimptotical optimal solution, but it still gets TL.

http://codeforces.com/contest/822/submission/28234265

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O(r * min(pr)) not optimal really. O(r) or O(rloglogr) are optimal.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right. I should use Eratosfen Sieve, I'm stupid. But I see — on C++ approach that I've used works 1.2 — 1.4 sec, so on C++ the solution of this task is little more obvious.

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I can share my divide and conquer approach for E if someone'd like me to :)

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

    Please do :)

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

      ok :D

      Let's calculate dp[m][x]: the minimum possible position in S such that it's possible to obtain [0..m] of T using no more than x cuts. If there's no such position, it's equal to -1.

      How would we calculate this in a straightforward way? Let's try to brute this optimal position. For a fixed i in S we wanna know the maximum possible length K such that S[i — K + 1..i] == T[m — K + 1..m]. If we can add it without intersections (i.e distance between dp[m — K][x — 1] and j is greater or equal than K), it means we found the answer. This gives us an O(xnmlogn) solution provided we use hashing :)

      Let's try to speed it up. It can be easily seen that for a fixed x the dp values are monotonic (till they reach -1). Moreover, if for some i dp[i][x] is equal to -1, that means that for all j >= i dp[j][x] will be -1 aswell.

      From these points we obtain the following idea: if there are some given segment bounds (l/r for the dp positions and L/R for the dp values), we take the median m = (l + r) / 2 and check all possible i's in range L..R. If we find the optimum, we call (l, m — 1, L, opt) and (m + 1, r, opt, R). If no, it's no use checking the right part of the segment, so we proceed with (l, m — 1, L, R). This gives us log(n) levels or recursion and no more than m operations per level. Since every check is performed in O(logn) time (binary search + hashing) and there are x calls or divide & conquer, this gives us the total complexity of O(x * m * log(n) * log(n)).

      http://codeforces.com/contest/822/submission/28235167

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Last part of solution is one of the DP optimizations from next link, right? http://codeforces.com/blog/entry/8219 More precisely, It is divide and conquer optimization? Also, can u explain more briefly how do we use hashing here?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's similar, right, and uses the same idea, but applied in a bit simpler case since I know that my dp is monotonic and bounded by [0..m — 1] at the same time. This allows me to turn O(mn) into O(mlogn) as described above.

          How do we use hashing? Denote lcs(i, j) as largest common suffix of prefixes [0..i] of T and [0..j] of S and use binary search :)

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

            You can actually shave off a factor of log(n), by simply using the observation you mentioned — on the monotonicity of the dp values for a fixed x. We can simply run 2 pointers — one for S from 1..n and the other for T from 1...m. The xth row in the dp table will be computed in (n+m)*(time for computing the latest common suffix) which is log(n) using hashing.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes please!

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

Is there anyone with TLE in C. My complexity was O(nlogn).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes same here, but i think some corner cases were not being handled by that approach

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved D without prime factors or anything like that. Just bottom up DP :/ Anyway, anyone thinks that D is far easier than C? I tried to solve C for ages, and I couldnt, but I solved D in pretty short amount of time.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +1 , took me quite some WAs (and a few < instead of >=) and time to get C right, D was in one go, if only I saw D first :(

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You approach isn't 100% correct. You use dp[j] that sometimes won't have the best answer at the moment you use it so if the relation was diffent your solution would be WA. It's correct for this problem because of the fact that you need to use the minimal prime factor so you'll end up getting the correct answer.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No. You always calculate in right order. When you want to calculate f [i*j] you will always have f[i] and f[j] because its bottom up approach. Its nothing to do with smallest prime.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nah... there's more than 1 way of writing i * j. You'll for example get 120 using 1 * 120, 2 * 60, 3 * 40 etc but when i = 3 and j = 40 did you consider the case when i = 10 and j = 4 (that results in 40 and is the j on 3 * 40)?

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          tfg No. You dont understand my solution, now please try to understand it. My first loop goes from i= 2 to i = r/2 + 1. Loop inside it goes from j = 1 to j = i ! So NEVER it can be that j > i . Because of that, when I come with first loop on some number, it is surely calculated. j is never bigger than i, so I will not have problems like you mentioned.

          Im 100% that this is OK.

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

Can somebody explain me E solution without hashes?

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

Is it possible to get a particular testcase? I need case 46 of C. WA. http://codeforces.com/contest/822/submission/28232052. Otherwise, if someone helped figuring out why, it would do too!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got my bug :) But... is it possible to see a whole particular testcase, say, as a .txt file?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, what was the idea of fixing the bug? I'm also using binary search and getting WA at 46:)

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

Any help plz ? C solution

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

Does anyone else think that the time limit for D was too strict.My solution TLEd on pretest 1 in spite the logic was perfect. :(

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

    Actually, I think it was opposite. I got AC without even proving that it is best to choose smallest prime. I just had DP[x] and bottom up approach, didnt even care about prime factors. It could be more strict so only if you prove optimal strategy you get AC. Still, I think that would be too hard for D tbh.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You did O(n^2)... You should do about O(n) or O(nloglogn)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How is my solution O(n*n) bro?2 nested loops don't always mean its O(n*n)

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

        Your solution about O(nlogn): for each i = [1..N — 4] you do (N — 4) / i iterations.

        As it's said above, you need O(n) solution or O(nloglogn).

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the TL is loose. Some solutions with O(N3 / 2) passed (which is precisely your solution).

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

I keep Getting WA on test 58 on problem C, and i couldn't understand what i did wrong, can anyone please check this submission for me :(

28235829

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

I used two pointers in C. I had created a pair in map mp[{l,r}]=cst which stores the minimum value of cost from l to r. I had created an array of sets where i inserted l,r as a pair in the r-l+1 th set. After that i used two pointers in the following way : I ran a loop from i=1 to x and i had a pointer pointing to the ith and x-i th set itr and itl respectively. I will check whether the L value of itl is less than or euqal to the R value of itr ,then i will increase itl,else i would compute the answer and increment itr by 1. This is my logic with a few corner cases handled . I trie to run the code on every possible small input in the test file but it passed all of them. Please have a look at it, and let me know my mistake. I am unable to find the mistake in my code. Here is the link to my code. Thank you !

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

unlucky contest ....

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh my god , you must be so angry. You have 1899 rating. So close to div1. Man so sorry for you. I am 5 points away from specialist but you are 1 point away from div1.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had 1898 at some point and now 1899 .... Maybe I'm cursed...

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah :D, but it's time for sure you become a div1, you have lots of experience, also during virtual contests you are performing really well.

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

In problem D, I get wrong output for case 2 in codeforces but right output in home pc and ideone, can anyone point out my mistake . code ideone

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

    I had same problem few times on Codeforces. Trick is, on codeforces, default value for int isnt 0. Maybe on home pc your default value is 0, like on mine. So your array prime[x] is maybe problem. Just set everything to 0 on start. That will fix it, I am 99% sure! (also for other arrays that you have)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      fixed wasn't the default value problem , changed type of i from int to long long in solve().

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

Liked the contest very much, but i don't like when a contest becomes a fast typing one. I knew how t osolve B insantly but i didn't write it fast enoguh and that's why i lost some points. Also why where the pretests for A so easy and for C. I understand that you're giving other contestants posibility to hack but that's not cool. There where people who solved 3 problems and others who solved 2 problems and they where on the same rank just because of hacking. Not cool. But contest was nice in general.

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

I am really not able to find bug in my code :'(. Can someone please help me! Submission link

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

    I don't know if this is the only problem, but you shouldn't divide an expression by 2 after taking its modulo. Do the division before taking modulo in line 13.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanx! I m really tired of doing such mistakes! I think i am going to stay in Div 2 my whole life!

      Well, thank you very much!

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

That moment when you did well last two rounds but fail to do well this time:

Is this gonna be unrated as well? xD

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

Why am i getting runtime error but i am not getting it in my compiler. Thanks in advance. http://codeforces.com/contest/822/submission/28236678

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

regarding this submission:

http://codeforces.com/contest/822/submission/28235877

as you see it gives me time limit, isn't this rlogr ?

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

    the nested loops work in a manner like this: r + r/2 + r/3 + r/4 + ..... + r/r, take r common factor, this gives : r(1 + 1/2 + 1/3 + 1/4 + ..... + 1/r), for very large r this summation is just approximately 2.7, so complexity will be approximately 2.7r, do you know why it gives time limit ?

    EDIT: the summation is near to log not 2.7

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

      (1 + 1 / 2 + 1 / 3 ... + 1 / n) is harmonic series. Its sum isn't equal to e. It grows like log n. So, as we have 5*10^6, r log r solution may not pass.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes sorry it is not equal to e i mixed it with another thing, but still at 5 million this series sums up to just 16, why 80 million would not pass ?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is actually . You solution should pass after removing some unnecessary things, as the Time Limit is tight.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes i accidentally mixed it with the summation of 1/factorial(i) as i tends to infinity

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

    Just removing some unnecessary mod (it is too costly) and using long long only where it is needed gave AC :P Bad Luck :(
    Changed Code — 28237999
    Diff: Diffchecker

»
5 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Div2 C test 59 is a stdlib qsort() killer!

Learned my lesson today: shuffle before using quicksort

My solution without shuffle: 28226684 (TLE 59)
My solution with shuffle: 28235814 (Accepted)

Not only me, other C (without plus-plus) user (rainboy) is also affected:

rainboy's solution without suffle: 28219544 (TLE59)
rainboy's solution with suffle: 28233646 (Accepted)

Then I search for source code for qsort() gnu implementation and found this: https://code.woboq.org/userspace/glibc/stdlib/qsort.c.html

It choose the pivot element using a median-of-three decision tree. After I read this: https://stackoverflow.com/questions/7559608/median-of-three-values-strategy the median of tree is pivot selection strategy to prevent worst case performance on easy to make case like "almost sorted data".

So I think it's not easy to make this qsort work in O(n2), but this test 59 prove that it's something common (although this is first time I encounter this problem after ~3.5 years experience in competitive programming).

How to make testcase that make this stdlib qsort() run in worst case O(n2)?

I trusted this function for years and now... he betrayed me :p

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

    Why use qsort instead of sort? is there any advantage?

    EDIT: oops, my mistake, misread.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sort has a better worst case time complexity. sort has a worst case runtime of O(nlgn) whereas qsort has a worst case runtime of O(n^2).

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

      Because there is no sort() function in C, only qsort().

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

I get "Wrong answer on test 2" (E: on problem D) when I submit and it evaluates wrong answer, but when I do custom invocation it evaluates to the correct answer. What is the difference between "custom invocation" and normal submission? E: The submission: 28237592

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't mind me — there is a mistake in my code and I checked the wrong numbers...

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

My code(28230274) for DIV2 — D gave TLE when submitted in GNU C++ 14. Exact same code(28238828 ), when submitted with GNU C++ got accepted.

Why is this happening( due to compilation overhead maybe) and isn't this unfair ? Should I start submitting in GNU C++ from now on ?

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

    Accepted code has max execution time 1497 ms with TL=1500ms. It was lucky to pass.

    You shouldn't start submitting in GNU C++, just write faster solution and don't forget that compilation time isn't counted as execution time of your solution.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for pointing out :) And I just realized that the same solution passes in 1497 ms in GNU C++ 14 when I wrote the code directly main() instead of making a function solve() and calling it from main() Code : 28239178

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please share your approach to solve E...

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

Is it possible to do problem D in python? My solution in python is close to the editorial one( but failed) and I implemented one of the AC solution in C++ by others and rewrite it in python but still can't get pass testcase 8. Anyone help? Thanks a lot!

  • »
    »
    5 months ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    I think you can try to use a better algorithm to solve the problem. If your C++ program runs more than 1000ms,your solution in Python is hard to get accepted, and I think my idea of problem D is better than the editorial

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for your advice. I will take a look of your solution and see what happen if I implement it in python.

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

Can anyone check my solution to C using Binary Search link: http://ideone.com/hC25Oz

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

Can Someone explain me the solution of problem C ? Thank You.

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

    I have used 4 vectors in my solution.

    1. vector<pair<long,pair<long,long> > > deal : This stores all the packages.
    2. vector<pair<long,long> > pack[k] : An array of vector in which pack[i] will store the {starting day,cost} of a package which extends over 'i' days.

    During input itself I ignored all packages which had a length of 'k' days or more since I could not use them with some other package (would have exceeded the constraint of EXACT k days). So, in vector 'deal' I pushed the {cost,{start,end}} and in the vector pack[end-start+1] I pushed the {start,cost}. Once the input part was done, I sorted the pack vectors one by one from (0,k). Now i created 2 more vectors :

    1. vector pack_day[k]
    2. vector pack_cost[k]

    I created these 2 new vectors because if not, then I had to write a binary search function separately. So I basically kept the pack[i].first portions in pack_day[i] and pack[i].second.portion in pack_cost[i] so that I could use the lower_bound function. Let me illustrate this with an example.

    Suppose I had 3 packages: (k=4)

    1 3 5

    2 3 4

    6 7 2

    Then deal would store this : { {5,{1,3}} , {4,{2,3}} , {2,{6,7}} }

    Then pack would store this :

    pack[0] : {}

    pack[1] : {}

    pack[2] : { {2,4} , {6,2} }

    pack[3] : { {1,5} }

    Then pack_day would store this :

    pack_day[0] = {}

    pack_day[1] = {}

    pack_day[2] = { 2 , 6 }

    pack_day[3] = { 1 }

    Then pack_cost would store this :

    pack_cost[0] = {}

    pack_cost[1] = {}

    pack_cost[2] = { 4 , 2 }

    pack_cost[3] = { 5 }

    So now, if I am provided a package starting from L, ending at R and costing W, then I will have to search for another package of length LEFT = K — (R-L+1) days. So will have to search the pack_day[LEFT] vector and find the position from where the packages start further from (R+1). So if for example,

    L=3

    R=6

    W=5

    K=10

    DAYS IN CURRENT PACKAGE = 6-3+1 = 4

    DAYS REQUIRED IN OTHER PACKAGE = 10-4 = 6

    So search in pack_day[6] for the position from where packages start from (R+1=7) 7 so that disjointness is satisfied. Once you have got this position, all you require is the minimum cost from THAT POSITION to the end of the pack_cost[LEFT] vector.

    Finding the position aspect is taken care of by lower_bound :

    IDX= lower_bound(pack_day[LEFT].begin(),pack_day[LEFT].end(),R+1) - pack_day[LEFT].begin()
    

    Now you require minimum cost in pack_cost[LEFT] vector in range (IDX,end of that vector). So for the minimum cost finding part, we shall take minimum from the end of the vector to beginning.

    for(int i=0;i<k;i++)
    {
        long mini=1e10;
        for(int j=pack_cost[i].size()-1;j>=0;j--)
        {
            mini=min(mini,pack_cost[i][j]);
            pack_cost[i][j]=mini;
        }
    }
    

    So the minimum in pack_cost[i] vector from position IDX to end is = pack_cost[i][IDX]

    So, iterate through the DEAL vector and for each package find its optimum partner package and keep taking a global minimum of the costs :

    mini=min(mini,W+pack_cost[i][IDX])
    

    My AC Code Complexity : O(Nlog(N))

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

      Thank You So Much! I understood very well..

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

can anyone tell y my soln to C is giving RTE 28228552 . Thanks in advance.

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

Can anyone find my bug please :/ problem: D

http://codeforces.com/contest/822/submission/28252419

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

Div 2 C giving WA on Test Case 25. Can anyone help me in finding the error?

http://codeforces.com/contest/822/submission/28250623

Man this is the third time I'm commenting. After commenting, I'm not able to find the previous comments. Why does this happen ?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro..Your code is extremely lengthy to look at. Let me explain you my logic. I hope it will help you.

    I have a map<pair<int,int>,int> mp-stores the minimum value of range {l,r},

    an array of set<pair<int,int> > st[N]-store the value {l,r} in the r-l+1 th set.

    So you have a map in which you can get the minimum cost from range l to r and an array of set in which st[i] has all the ranges stored in increasing order whose distance is i. So now lets run a loop from i=1 to i<x and continue if st[i].empty() or st[x-i].empty(). We will only consider ranges from st[x-i] which occur after the end of a particular range in st[i]. So this is kind of a merge function in merge sort. Let me explain it. Initially we will have the pointers itl and itr pointing to the beginning of the i th set and the x-i th set respectively.

    We have two cases :

    1)R of itl is greater than or equal to L of itr-in this case we know that these are of intersecting type (or the itr pointer's range is completely before the itl's range-we do not need to consider this because this will be considered when i=x-i). In this case we can safely say that since the range at itl is not satisfying itr,all the ranges that come after it wont satisfy it as well. Hence we increment the pointer at st[x-i].

    2)R of itl is less than L of itr- in this case we know that it is a valid range which can be a candidate for the answer. Hence we compute its cost. But wait you will not simply add their costs. Instead you need to keep a variable which stores the minimum of all the costs of ranges in the st[i] set. This is because if a range in st[x-i] satisfies with the j th range in st[i] it will satisfy with all the ranges which occur before it. Hence you will keep a variable global and whenever you encounter this case you need to update it to minimum value possible.

    How to calculate minimum-Whenever Case 1 occurs just compute cost=global+mp[{itr.first,itr.second}] and update ans=min(ans,cost); Just keep in mind you need to consider all the elements in st[x-i] even if st[i] elements have finished because they also satisfy all the elements in st[i] if at all they satisfy even one of them.

    Just be a bit cautious while writing the code, and surely you will get an AC. I did not get an AC during the contest as i was very careless — well it has become a norm nowadays :( :( .

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much for the explanation. That helped !

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

I would really appreciate it if someone could help me figure out why the following submission ended up with WA on testcase #7. I'll try to explain each of my steps in this post if anyone is confused with what I was trying to do :^)

http://codeforces.com/contest/822/submission/28232461

So I have an array arr that has dimensions n x 4. The first column was meant to store r — l + 1 and I was planning on doing a sort based off first column with my own comparator. Up till this point my code was successful (I'm 100% sure). However, I feel the mistake lies somewhere in the way I applied the binary search to find the other value in the array such that both sum to x. Any advice is appreciated greatly!

Thanks for the great contest Melnik :)

»
5 months ago, # |
  Vote: I like it -22 Vote: I do not like it

IS IT RATED IS IT RATEDDDDDDDDDDDDDDD

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

Can someone tell me how to solve a variation of Problem C, i.e., if more than two disjoint trips are allowed? All I can think of is a recursive approach. For N trips and Duration K, choose

min(cost[i] + Trip(disjoint_trips(i), K - dur[i]), Trip(remove_i_from_list(i), K))

. Any approach to implement this would be nice. Thanks

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

    I only can think about DP... O(NK^2) DP[i][k] stores min cost ending at i with length k. Initially DP[i][k]=inf, DP[i][0]=0 for every vacation (sorted by r) (l, r, c) DP[r][k]=min (DP[l-a][k-r+l-1]+c). Also you can do O(N^3) by compressing intervals in O(NlogN).