Блог пользователя Melnik

Автор Melnik, 7 лет назад, По-русски

Всем привет!

В воскресенье 2 июля в 19:05 MSK состоится рейтинговый Codeforces Round #422 (Div. 2).

На этот раз, в отличие от раунда 415, я готовил задачи в одиночку. Большое спасибо координатору Алексею netman Вистяжу за помощь в подготовке раунда, Владиславу winger Исенбаеву, Александру AlexFetisov Фетисову, Николаю KAN Калинину и Ильдару 300iq Гайнуллину за прорешивание задач, а также Михаилу MikeMirzayanov Мирзаянову за прекрасные системы Codeforces и Polygon.

Как и в раунде 415, главными героями задач этого раунда будут красавица Нура и хакер Леха.

Участникам будет предложены шесть задач и два часа на их решение. Как всегда, участники из первого дивизиона могут решать задачи вне конкурса. Разбалловка будет объявлена ближе к началу раунда.

Надеюсь, раунд вам понравится. Всем удачи и высокого рейтинга!

UPD1: Обратите внимание, изменилось количество задач, которые будут предложены для решения.

UPD2: Разбалловка для этого раунда: 500 — 750 — 1250 — 1750 — 2250 — 2500.

UPD3: Поздравляем победителей! Разбор будет опубликован в ближайшее время.

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_

Особые поздравления natsugiri, который единственный из всех участников решил все шесть задач за отведенное время!

UPD4: Разбор задач.

  • Проголосовать: нравится
  • +428
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится -48 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Is it rated?

»
7 лет назад, # |
Rev. 7   Проголосовать: нравится -9 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

tourist is registered and everyone is excited!

»
7 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

Is it unrated?

»
7 лет назад, # |
  Проголосовать: нравится +184 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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?

»
7 лет назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

I can only imagine the pressure on author.

»
7 лет назад, # |
  Проголосовать: нравится -280 Проголосовать: не нравится

Round #422=Registration x422

»
7 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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 !

»
7 лет назад, # |
  Проголосовать: нравится +202 Проголосовать: не нравится

I speak through memes.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

Hmmm.. This doesn't look legit :D

From today's contest registration:

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully no more server slow problems.

»
7 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Many thanks to coordinator Alex netman

Has KAN resigned?

»
7 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Exciting score distribution :D

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem A: I shed a tear :'

(no emoji)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

в задаче D у всех наверное валиться из за неправильного остатка

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there something wrong with hacks of A?

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Pretest 2 D is killing everybody

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    I used adjacency list + BS.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    EDIT: failed systests. two pointers

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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)) )

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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).

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the hack for div2B?

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve E ??

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why is the smallest prime factor optimal ?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

      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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

как решать D?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Start system tests quickly this time please!

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    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.
  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You should check for 32-bit integer overflow

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Have you done the operations MOD 1e9 + 7 ?

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the solutions of E and F?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Is suffix array required in E?

»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Idea behind D ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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).

»
7 лет назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится
#include <bits/stdc++.h>
using namespace std;

int main() {
    bool uDoWell, isRated;
    cin >> uDoWell;
    if (uDoWell) {
        isRated = false;
    }
    else {
        isRated = true;
    }
    cout << isRated << endl;
}
»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hello, folks. What's the solution of E problem?

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

just in case Rank predictor

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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..

»
7 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится


»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

What a Thrilling Contest!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone with O(n) solution for C?

»
7 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

what is the time needed to calculate the rate?

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    http://codeforces.net/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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Please do :)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +29 Проголосовать: не нравится

      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.net/contest/822/submission/28235167

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 :)

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes please!

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    +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 :(

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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)?

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody explain me E solution without hashes?

»
7 лет назад, # |
Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any help plz ? C solution

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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. :(

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

unlucky contest ....

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Is this gonna be unrated as well? xD

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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

Is this gonna be unrated as well? xD

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

regarding this submission:

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

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      (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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 ?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

    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))

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone find my bug please :/ problem: D

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

http://codeforces.net/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 ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :( :( .

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.net/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 :)

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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).

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Забавная отсылка к трекам ЛСП)