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

Автор Melnik, 2 года назад, По-русски,

Всем привет!

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

На этот раз, в отличие от раунда 415, я готовил задачи в одиночку. Большое спасибо координатору Алексею netman Вистяжу за помощь в подготовке раунда, Владиславу winger Исенбаеву, Александру AlexFetisov Фетисову, Николаю KAN Калинину и Ильдару gainullin.ildar Гайнуллину за прорешивание задач, а также Михаилу 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
  • Проголосовать: не нравится

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

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

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

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

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

Is it rated?

»
2 года назад, # |
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.

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

Hopefully this time it will be rated ;D

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

tourist is registered and everyone is excited!

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

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

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

Is it unrated?

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

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

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

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

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

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

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

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

I can only imagine the pressure on author.

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

Round #422=Registration x422

»
2 года назад, # |
  Проголосовать: нравится +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 !

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

I speak through memes.

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

No mistakes in jury's solutions, please

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

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

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

after the round :D

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

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

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

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

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

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

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

GL & HF ?

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

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

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

Hmmm.. This doesn't look legit :D

From today's contest registration:

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

Hopefully no more server slow problems.

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

Many thanks to coordinator Alex netman

Has KAN resigned?

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

Exciting score distribution :D

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

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

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

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

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

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

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

Problem A: I shed a tear :'

(no emoji)

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

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

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

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

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

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

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

Is there something wrong with hacks of A?

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

Pretest 2 D is killing everybody

»
2 года назад, # |
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?

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

    I used adjacency list + BS.

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

    EDIT: failed systests. two pointers

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

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

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

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

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

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

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

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

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

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

    I used array of priority queues

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

What is the hack for div2B?

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

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

How to solve E ??

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

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

  • »
    »
    2 года назад, # ^ |
    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...)

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

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

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

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

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

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

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

      Why is the smallest prime factor optimal ?

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

      • »
        »
        »
        »
        2 года назад, # ^ |
        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.

    • »
      »
      »
      2 года назад, # ^ |
      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.

  • »
    »
    2 года назад, # ^ |
    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)

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

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

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

как решать D?

»
2 года назад, # |
  Проголосовать: нравится 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)

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

Start system tests quickly this time please!

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

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

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

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

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

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

  • »
    »
    2 года назад, # ^ |
    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

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

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

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

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

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

    You should check for 32-bit integer overflow

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

    Have you done the operations MOD 1e9 + 7 ?

    • »
      »
      »
      2 года назад, # ^ |
      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.

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

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

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

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

  • »
    »
    2 года назад, # ^ |
    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.

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

Can anyone explain the solutions of E and F?

  • »
    »
    2 года назад, # ^ |
    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.

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

Is suffix array required in E?

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

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

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

Idea behind D ?

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

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

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

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

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

just in case Rank predictor

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

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


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

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

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

why are we not getting rating from last two rounds and the contests are also not added up in our graph

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

What a Thrilling Contest!

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

Anyone with O(n) solution for C?

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

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

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

»
2 года назад, # |
  Проголосовать: нравится 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?

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

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

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

what is the time needed to calculate the rate?

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

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

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

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

»
2 года назад, # |
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

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

»
2 года назад, # |
  Проголосовать: нравится 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)

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

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

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

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

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

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

    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.

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

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

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

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

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

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

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

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

    Please do :)

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +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.com/contest/822/submission/28235167

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

        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?

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

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

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

    Yes please!

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

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

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

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

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

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

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 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)?

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

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

Can somebody explain me E solution without hashes?

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

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!

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

Any help plz ? C solution

»
2 года назад, # |
  Проголосовать: нравится 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. :(

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

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

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

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

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

»
2 года назад, # |
  Проголосовать: нравится 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

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

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 !

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

unlucky contest ....

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

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

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

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

»
2 года назад, # |
  Проголосовать: нравится 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

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

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

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

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

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

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

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

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

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

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

»
2 года назад, # |
  Проголосовать: нравится 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

»
2 года назад, # |
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

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

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

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

regarding this submission:

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

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

  • »
    »
    2 года назад, # ^ |
    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

    • »
      »
      »
      2 года назад, # ^ |
      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.

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

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

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

  • »
    »
    2 года назад, # ^ |
    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

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

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

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

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

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

»
2 года назад, # |
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 ?

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

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

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

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

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