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

Автор vovuh, история, 4 года назад, По-русски

UPD: Обратите внимание на перенос времени начала соревнования.

<almost-copy-pasted-part>

Привет! В 12.03.2020 16:05 (Московское время) начнётся Codeforces Round 627 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

</almost-copy-pasted-part>

Спасибо Артему Rox Плоткину и Дмитрию _overrated_ Умнову за помощь с тестированием раунда!

UPD2: Разбор опубликован!

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

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

"You will be given 6 or 7 (or 8) problems and 2 hours to solve them."

Does this means that the problems haven't been decided ?

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

Which contest coincided with the original timing?

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

Обратите внимание на перенос времени начала соревнования

Чёртов коронавирус

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

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

Who else is hyped for Div 3 because can't get good rating from Div 2?

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

What does mean by "almost-copy-pasted-part"?

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

So excited for first contest. Good luck everybody!

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

How was your Holi celebration ? Was anyone not able to play due to coronavirus threat?

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

2 hours in Div 3 and 4 hours in Reply Code Challenge, it's going to be an exhaustive day.

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

Good luck everyone. High Ratings.

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

Hope that I can solve A-B-C.

Good luck guys <3

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

well,is there anyone know what's the name of the other contest(1.5hours later) after this contest?

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

Hope to become expert after this round

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

I hope to get blue in this contest

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

I don't think i can solve over two problems...

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

    if you think you can't, so you can't.

    Believing in yourself is the first step to success.

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

Hope problems will not be indirect like this

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

Bad luck for me becoz i can't attend this contest.

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

Good luck Everyone

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

.

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

Hope i will be green after this round :))

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

I use this site during contest ;) Asoftmurmur

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

I use this site during contest :)

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

I got logged out 2-3 times during contest. Did it happen to anybody else or problem at my end?

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

I feel it difficult to understand some of the problem statements,does anyone feel the same?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится
  • A Done
  • B Done
  • C Done
  • Me Done
  • Nice Contest
»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Good to see that vovuh is the writer.

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

The problems are too easy so that more than 500 participants solved all the problems

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

Guys,I have a problem! do not have a point of 1900 or higher in the rating Is that means standings in contest is different from your rank which is the final standings?

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

    The contest will be rated for those participants who have a rating below 1600. However, participants with rating greater than or equal to 1600 can participate unofficially. Separate standings are available for official and unofficial+official participants.

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

During the contest, I automatically got logged out from codeforces. I had two tabs of codeforces open in firefox. When I tried to submit I got to know I am not logged in. This has happened thrice. Is it normal/minor bug or there is some other problem ?

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

I think there's no one later than me to solve A!

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

For those who cannot understand what is subgraph and subtree. Click :(

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

Thank you very much for the rating friendly contest

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

How to solve D ;-;

My approach
My source code

Found Mistake: (wrong formula) cout << 1LL * n * (n + 1) / 2; -> cout << 1LL * n * (n - 1) / 2; Found Mistake: (integer overflow) ll res = q * (q - 1) / 2 + q * zero; -> ll res = 1LL * q * (q - 1) / 2 + 1LL * q * zero;

AC Code (Spoiler warning)
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    You can use binary search. create a diff array such that diff[i] = teacher[i]-student[i]. sort this array. at a particular point i calculate how much you'll need to compensate for when you choose j. e.g if teacher[i]-student[i] = -2. then we know we need diff[j] >= 3, so as to make teacher[i]+teacher[j] > student[i] + student[j].

    you can easily binary search this value in diff array.

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

    Let $$$c_i = a_i - b_i$$$. Now you have to count the number of pairs of $$$c_i$$$ with the positive sum. It can be done in $$$O(n log n)$$$ with binary search.

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

    Create an array of differences of a[i]-b[i] then use lower bound to find good pairs for negative numbers and zero numbers and for positive use binomial coefficient (ncr).

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

    I used PBDS.

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

      how?

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

        Let's just iterate over the array from the start, and since we need to find unordered pairs, so for a particular i, we need all elements before it such that: ai — bi > bj — aj or Let's denote bj — aj as val, then we need all such elements where : val < ai — bi So PBDS on pair of elements acts like a multiset with additional feature ,giving count of elements less than x too.So use that function for each i and get count of elements less than {ai-bi-1,inf}, and add it to answer and insert pair {bi-ai,i} to the pbds.

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

        Use PBDS as a multiset (comparator less_equal). Traverse from the end of the array and for each index, increment answer by order_of_key of $$$a[i]-b[i]$$$ (basically index of upper bound). Then insert $$$b[i]-a[i]$$$ in the PBDS.

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

      Can you share your code? I tried using pbds, but it gave wa on test 6.

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

        You can look it up in my submissions and if are not permitted, then add me as a friend and then look it up in standings submission. Sharing code here will scribble the comment section.

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

    It can also be done with sorting; if you have a sorted array $$$c$$$ and you want to know for particular $$$i$$$, how many $$$j$$$ satisfy $$$c[i]+c[j]>0$$$, then you can decrement $$$j$$$ from $$$n$$$ down to the first index where $$$c[i]-c[j]<=0$$$, and count $$$n-j$$$. Then if you iterate over increasing $$$i$$$, this $$$j$$$ can only decrease.

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

    What is wrong with my approach ? ;-;

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

    problem is similar to inversion count, so used BIT tree to solve it, after compression.

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

    Let c[i] = a[i] — b[i]. Now we have to count the number of pairs with positive sum. Sort array c.

    Set two pointers, one at index 0 (pointer j) and the other at index n-1 (pointer k). In each iteration decrease k by 1 and find the corresponding index j, by running a separate loop within the previous loop. Exit when j >= k.

    Initialize ans = 0, and keep adding (k — j) in each iteration, i.e. ans += k — j

    Note that j keeps on increasing in each iteration. We do not restart j from 0 each time.

    Time Complexity: O(n)

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

    thanks for taking your time to write an explanation.

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

Can any one give a hack on the following approach for D?

Sort them by $$$a_i-b_i$$$, then use binary search to find last okay one.

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

    Gradually sort?

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

    sorting them will change the order of the indices

    and in the problem you need $$$j$$$ to be $$$>$$$ $$$i$$$

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

      That doesn't matter, if you are counting all distinct pairs $$$(i,j)$$$ which satisfy some property, then this will equal the number of distinct pairs $$$(\sigma(i),\sigma(j))$$$ which satisfy the same property, for any permutation $$$\sigma$$$

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

    Make an array of Ai — Bi, sort it and binary search the right one for each. That's the solution I think.

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

    Maybe you can use the Binary Indexed Tree in value.

    First discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$.

    Then for every $$$i \in [2, n]$$$, calculate all for $$$j \in [1, i)$$$ which $$$b_j - a_j < a_i - b_i$$$

    The time complexity will be $$$O(n \log n)$$$.

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

Lightning-fast system testing

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

Why, i kept logging out after few intervals ,throughout the contest??

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

How to solve E? Also, what is the name of the concept used in E?

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

    I believe it's called dynamic programming.

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

    Dynamic programming. $$$dp_{i, j}$$$ is the number of good times when we consider the first $$$i$$$ times ($$$0$$$-indexed) and did this $$$-1$$$ "operation" $$$j$$$ times. The answer is $$$\max\limits_{j=0}^{n} dp_n$$$.

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

      what's the meaning of the first $$$i$$$ times,I can't get it

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

        More correctly, $$$dp_{i, j}$$$ is the number of "good times" when we consider first $$$i$$$ values $$$a_i$$$ and used $$$-1$$$ $$$j$$$ times. Transitions are also pretty easy: if the sum of the first $$$i$$$ values $$$a_i$$$ is $$$s$$$ then $$$dp_{i + 1, j} = max(dp_{i + 1, j}, dp_{i, j} + [(s - j) \% h \in [l; r]])$$$ and $$$dp_{i + 1, j + 1} = max(dp_{i + 1, j + 1}, dp_{i, j} + [(s - j - 1) \% h \in [l; r]])$$$. $$$\%$$$ is modulo operation ofc.

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

    state are index and modulo

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

in problem D , solution of 10^10 was giving TLE for test case 12,althought time limit was 2 seconds, http://codeforces.com/contest/1324/submission/73076815 i thought 10^10 solutions can run in 2 sec

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

Downvoted because the sentence in problem E is completely unreadable.

The sentence "The i-th time he will sleep exactly after ai hours from the time he woke up" and "Vova can control himself and before the i-th time can choose between two options: go to sleep after ai hours or after ai−1 hours." sounds inconsistent.

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

for problem D, i Stored two arrays one array has (ai-bi) values and the other has (bi-ai) values and i ran a nested loop from i to n-1 & j=i+1 to n-1 and counted the number of elements that are greater than current element. what could i have done better?

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

    In fact, you can first discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$.

    Then use a Binary Indexed Tree to count all the values.

    The time complexity will be $$$O(n \log n)$$$.

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

    Use a binary indexed tree.

    Insert $$$a_i - b_i$$$ into it after checking how many elements there are before $$$i$$$ which satisfies $$$a_j - b_j > b_i - a_i$$$. Discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$ first thing first.

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

UPD: Sorry for the comment. I didn't think much, it's my bad.

Appologize for the round, sorry.

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

    Do you write is serious? The "subSTRING" problem, as you say, is not "more interesting" and can be solved in $$$O(n)$$$ considering $$$3$$$ or $$$4$$$ consecutive characters.

    D — data structure problem? The problem "sort the array and do (lower bound or binary search)" is data structure problem?

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

    Can't the substring problem be solved in O(N)?, I did that only after I misread the problem! :( Just check all "3 consecutive characters substring" and "4 consecutive characters substring".

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

Interesting fact for myself: Everytime people celebrate a rating-friendly contest, I lose ratings; Everytime people complain about toxic problems, I gain ratings.

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

You did not think that the tasks are too simple even for div 3 ?)

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

    Speed is really need. lol

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

    vovuh made them easy to please div3 ppl

    here

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

      Haha, that's funny. I don't know how to prepare "good" round. I prepare slightly hard round, people say "omg that's div.1, not div.3!". I prepare slightly easy round, people say "loool 2ez4me that was not even a round". I don't know what to do.

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

        Lol. You should ignore comments made by candidate masters on div3 rounds. A candidate master saying div3 is easy is like a pupil / grey guy saying div1 is hard.

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

        actually, vovuh, you did well, i really appreciate as most of div.3 contests are made of you

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

        Don't coordinate anymore divs 3 rounds )

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

        Actually, vovuh, you are the best. You prepare quality Div 3 contests, and I enjoy participating in your contests. Also, I participating out of the contest; I get to learn new concepts and techniques from your contests. I hope you keep up this great work and keep contributing to more such awesome contests.

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

        I really liked D problem of this contest. I've been focusing on pbds/fenwick last 2 weeks and this problem really put my knowledge to test. I like how I saw 3 different approaches on this problem(bin search, pbds, fenwick and treap). The problem really managed to capture the creativity of the community. Well done, our Div.3 King

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

        Great job vovuh, don't give in to the hate. As it is, it's hard and time consuming to create problems and test cases, let alone deal with criticism such as this.

        Personally, I think this is a good level of difficulty, otherwise how do we differentiate between Div 2 and Div 3 problems. Once in a while, problems in Div 3 are easier compared to other Div 3 contests — but I think many people in Div 2/Div 3 enjoy the opportunity to solve a few problems (that are in reach and where we can apply what we've learnt recently) and then learn from the other unsolved problems.

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

    I think that this is the perfect difficulty level for Div 3. Myself being an Expert (Rating: 1734), I was only able to solve A, B, C, D. So, I believe that it justifies my claim.

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

Speedforces

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

_overrated_ после ваших див3 фиолом стал vovuh беги пока не ебнуло!

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

Tried E for the first time in my life. Got wrong answer test 40! I think I made a silly mistake but couldn't figure out yet. My submission: 73079617

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

    It failed for me as well, test case is involving l = 0 I guesss, and I had counted t = 0 case, which is wrong. Removing that gave me AC.

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

Why these two submissions using PBDS for problem D got different verdicts vovuh please look into the matter.

Correct SOlution:-73082017 Rejected Submission:-73079109

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

During contest I was logged out several times. Does someone know why?

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

It's quite easy. Even my i got more rating, but i think i wouldn't satisfy with those.

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

Why I am getting ILLEGAL CONTEST error while pushing "hack it"? Please fix

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

Hello? I'm a bit curious about how to solve F, can someone help me? Thanks

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

can someone please explain the reason for TLE in my submission of E my code -link

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

    Because at last where you have done dp[id][sum][f]=ans, your value of sum is changed, but your dp[id][sum][f] should use original value of sum not the updated one.

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

1 5 2 2 2 2 4 why this will give yes in A?

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

    NO, since all elements must have same parity (either odd or even), then only answer can be "YES"

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

    Is it a full test or a single case? If it is a full test(i.e. 1 represents number of cases,5 represents number of columns) then simply put blocks in column 1-4 If it is a case(i.e. there are 7 columns),the answer is NO.

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

+104 -> +8, thx for B pretests, goodbye expert:(

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

Hack for B?

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

!!NEED HELP!! My solution for problem-D : https://codeforces.com/contest/1324/submission/73076688 According to me,it's complexity nlogn, but i m getting time limit. Can anyone explain why it is happening or where m i wrong?? TIA

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

!!NEED HELP!!

My solution for problem-D : 73076688

According to me,it's complexity nlogn, but i m getting time limit. Can anyone explain why it is happening or where m i wrong??

TIA

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

quite sad that my solution for B got accepted in the first place , was it intentional to make the test cases all weak for only an odd length palindrome / 2 different numbers only? would've solved 5 problems in one contest for the first time.

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

Will my rank improve if I hack someone's solution ? pls help

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

Hi, can anyone explain why this solution 73084554 is giving WA. While this solution works 73037149 by tmwilliamlin168. Thanks in Advance!

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

Problem B $$$O(N)$$$

73087070

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

I liked this contest vovuh. Good job. I'm interested to know your thoughts on the difficulty levels of $$$D$$$ and $$$E$$$ if this was a Div $$$2$$$ contest. Do you think $$$D$$$ is harder than $$$E$$$ ?

How to solve $$$F$$$ ?

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

    I think D is between the div2B and the div2C, while E is between the div2C and the div2D.

    However, you may just wait until when these problems are recorded in PROBLEMSET and the difficulty of them will be visble for you.

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

      I think segment trees are too difficult to be asked for $$$B$$$. It might be a $$$C$$$.

      Can you please tell me how to solve $$$F$$$ ?

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

        In fact, you don't need segment tree for D since the binary search is enough for it.

        For problem F, I apply DFS twice on the trees.

        In the first DFS, I regarded no.1 node as root and regarded the trees as a rooted trees. In this DFS, I get the correct answer for no.1 node.

        In the second DFS, I started my DFS from no.1 node and calculated the answer of other nodes in my traversal.

        For more details ( since I'm poor in English but good at C++ ), you can look up my code.

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

          Nice ! I never thought of binary search for counting inversions ! :)

          My main doubt was in the second DFS. Thanks !

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

          I implemented the same algorithm in Java, but failed test case 3. I couldn't figure out why it fails. Can you help me? My submission is: 73110580

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

            It seems like ts3 is just a random tree whose node is all black. So you can just make a small test to see what happens in your program.

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

              My tree building logic was wrong, I need to build a 0-rooted tree recursively, thanks anyway!

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

    Root the tree arbitrarily and let $$$dp_x$$$ be the answer for $$$x$$$'s subtree. We can do this with a single dfs.

    But then $$$dp_x$$$ won't necessarily have its full answer (because we didn't consider the path through $$$x$$$'s parent). So do a second dfs and for each parent node $$$y$$$ update each of $$$y$$$'s child's $$$dp$$$, (child may benefit from path via their parent $$$y$$$), but be careful to not to over count that child's contribution from $$$dp_y$$$.

    for clarity you can see my submission: 73067648

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

      Ah ! The overcounting is tricky ! We should subtract only if $$$f(c) > 0$$$. The reason is that if $$$f(c) > 0$$$, then we never added $$$f(c)$$$ to $$$f(v)$$$

      Thanks !

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

it is the first time i tried in E

but i got WA on 40

any one can help me why it is wrong

https://codeforces.com/contest/1324/submission/73078402

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

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

Can someone please explain to me the DP state for problem E?

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

    Before considering sleeps #$$$i,i+1,\ldots,n$$$, suppose you last slept at time t. Then under these conditions, dp[i][t] is the maximum number of good sleeps among $$$i,i+1,\ldots,n$$$. The question asks to find dp[1][0].

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

Can B be solved in O($$$n^2$$$) will it pass?

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

    i think. YES, as n=5000

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

    Yes, but if you have a constant factor $$$a$$$ you will have runtime $$$O(a * n^2)$$$, which may TLE because worst case scenario you will do something like $$$a * 5000 * 5000$$$ operations which may not be executed in time (I hacked a couple ppl with this idea)

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

Can someone explain why the order won't matter in problem D (i<j) ??

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

Can someone explain why the order (i<j) won't matter in problem D ??

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

    i<j simply means that pair (i,j) and (j,i) are same. so you can ignore this statement and divide it by 2 at last to consider it only once.

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

    It is another way of telling that pairs (i,j) and (j,i) are the same. And they have to be counted as 1.

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

Is problem F a classic problem? Because i notice that many people write similar code in their dfs. If it is, please tell me. Thanks is advance :)

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

Could someone help me figure out my mistake in Problem E 73091842. Thanks in advance.

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

vovuh you are great author your problems are amazing

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

Hack case of B . 1 3 2 2 2

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

[deleted]

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

how is this O(n^2) solution timing out on B for 2 secs??.Link

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

    It seems like you are using map<int, int> which takes $$$O(\log n)$$$ time for adding and looking for element. Also, std::map is especially slow (big constant factor) so your solution has time complexity $$$O(n^2 \log n)$$$ with big constant factor.

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

      Ah, wow. i always thought map was constant access and insertion. thanks btw

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

        I think what you want is unordered map which uses hash. It has constant access time on average (but can be up to $$$O(n)$$$ worst case). It also is quite slow since internal structure is somewhat complicated. I mean, don't expect something like a array-access speed.

        Also, since it uses random, it can be hacked if some experienced coder tries to craft specific testcase to kill unordered map.

        I think there was a good blog on CF about this (and also how not to get hacked from that) but I can't find it now.

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

      So this should time out too? 73028508

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

        I don't think so. Your code is performing $$$n$$$ map access operations which make the whole complexity like $$$n \log n$$$. The code originally asked was using about $$$n^2$$$ map access.

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

    I think map takes O(log n) time for searching thus complexity goes to O(n^2logn)

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

When it's my first time to solve 4 problems and I've a new high rank:

HACKS:

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

Nice Contest! My solutions: A. Check the parity of all elements. If the parity is same, then the answer is YES, else NO B. Its always enough to check for palindrome sequences of length 3. So considering each element as center, check if the right and left parts contain atleast 1 element in common. C. its always beneficial to use R and not L. (why? bcoz with L you can only reach back to reach some R, which anyway you would have reached before reach the cell with L). so find the largest gap in reaching a R. D. Compute ci = bi-ai and sort this array. Then for each ai and bi count the number of elements in array c less than ai-bi. Also make sure to consider the edge cases where you have counted the same element again. E. Use dp. The state is (i, time), where i is the day (or the ith sleep) and time is the current time. Write transitions to each of ai and ai-1. F. Assuming you run bfs from some initial root node, Compute max(wi-bi) for each node i in its subtree rooted at i. Now we need to compute the value in parent part. This can be done using tree rerooting technique.

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

Nice Contest! My solutions: A. Check the parity of all elements. If the parity is same, then the answer is YES, else NO B. Its always enough to check for palindrome sequences of length 3. So considering each element as center, check if the right and left parts contain atleast 1 element in common. C. its always beneficial to use R and not L. (why? bcoz with L you can only reach back to reach some R, which anyway you would have reached before reach the cell with L). so find the largest gap in reaching a R. D. Compute ci = bi-ai and sort this array. Then for each ai and bi count the number of elements in array c less than ai-bi. Also make sure to consider the edge cases where you have counted the same element again. E. Use dp. The state is (i, time), where i is the day (or the ith sleep) and time is the current time. Write transitions to each of ai and ai-1. F. Assuming you run bfs from some initial root node, Compute max(wi-bi) for each node i in its subtree rooted at i. Now we need to compute the value in parent part. This can be done using tree rerooting technique.

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

Could someone help me with my problem E submission. I am not able to figure out the mistake.Thanks in advance[submission:73096035]

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

    Corrected code 73127806

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

Can anyone tell me why this 73097950 passes and this 73098017 does not ?

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

![ ](2-24510-trollface-deal-with-it-troll-face-png)

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

I got TLE error during contest instead of WA! even after the contest when I was submitting correct answer I was getting TLE. I got frustrated and then copy pasted solution of another user then also I got TLE. Also, I was logged out multiple times automatically during the contest!! solution link: https://codeforces.com/contest/1324/submission/73104474

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

Will there be any system testing after the hacking round is finished

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

Will there be any system testing after the hacking round is finished??

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

    Yes

    All of the AC solutions will be rejudged with original tests and successful hacks once the hacking phase is over.

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

Why I want to hack a solution and it shows Illegal contest ID ?

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

Can Somebody please explain why this solution is not giving compile time error on pretest cases and arbitrary cases on offline compiler Solution for Problem 2

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

When system test will start?

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

What's wrong with my solution for E problem? 73075794

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

I am wonder that when the system test will begin.

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

Anyone who solved problem D using two pointers? Please explain your approach

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

Why did it keep on logging out during the entire contest? It was so irritating whenever I was to submit my solution It logged out :(

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

Each time Vova sleeps exactly one day (in other words, h hours).

What a lousy problem statement for E.

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

When will the ratings change?

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

I have a solution on F that seems to be different from everyone: Let's hang the tree at vertex 1 and calculate dp[v] — the maximum answer for the subtree of v. This DP solves the problem for the vertex v if the root is the vertex v. How do we fix this? Let us remember when recalculating the DP for root 1 which vertices we included in the answer. Then we’ll introduce a push push that will push dp[v] into dp[u] depending on the benefits. That is, if our vertex u was included in the answer, then we push dp[u] = max(dp[u], dp[v]) into it, otherwise dp[u] = max(dp[u], dp[u] + dp[v]) The answer for vertex v is dp[v]

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

    I did this too (submission towards the bottom) but I think it is more or less the same as everyone else. It just condensed the if/else that others used into a smaller form.

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

      I do not completely agree, because the majority (70-90%) passed the "resuspension" technique for O (1)

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

When will the rating be changed?

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

I kept getting logged out of my account. Did this happen to anyone else ? Why did it occur ?

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

Is it rated?

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

Is the contest is rated or not

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

Is the system testing done??

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

when will our rating change?

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

Hacking phase finished more than 6 hours ago but no system testing till now!

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

How long does it take to give rating????

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

When will the ratings change?

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

Maybe they are thinking to do system testing together with round 628. It happened once afaik.

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

waiting for the rating change...

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

Why tooo silly test cases in problem B?! Please, be care what you do!

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

Why another system testing?

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

Testing is stuck at 78%

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

Is system testing stuck? The status has been "System Testing 78%" for at least the last half hour.

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

Is there something happen with the site...? Because system testing stuck at 78%.

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

Even corona virus is faster than system testing

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

great now stuck at 79!!

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

Cooper after returning to earth: Did system testing crossed 79%....??

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

The rate of system testing is prolly 1% per hour XD

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

Python runs faster than this system testing :(

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

Codeforces definitely needs a better hardware. :/

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

how to solve D? help help help!

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

I think codeforces is going through their ever slowest system test.

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

their slowest system testing in the history

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

Hopefully this system testing will end in 2020. :D

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

reached 100%, then went back to 91% :3 .

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

Contrary to your speculations, I assure you everything is alright. The system testing is progressing very rapidly. It only took 2 minutes to go from 98% to 91%.

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

Recursive testing. :D

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

wtf systest rolled back 100% -> 91%

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

What's wrong with the system testing? Does anyone knows?

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

Did I just travelled back in time or what? system testing was 100 just a few mins ago and it's 92 now!!

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

Why are D and E being tested again??

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

looks like they are testing problems D and E again as the count for rest of the problems is not changing

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

Finally system test has finished !!

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

when will the ratings come?

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

Almost e qual time distribution for open hacking and system testing phase.

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

Why is final standings fluctuating , some kind of superposition???

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

Where is our rating?

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

It has been a day since the contest ended. And 12 hours since the hacking phase ended. There has been no change in ratings. Is this a usual occurrence?

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

https://www.youtube.com/playlist?list=PLl4Y2XuUavmtjmxnbqOAb_UNyRK1soQZw

Will be uploading solution videos of all questions on this link.

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

.

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

I am getting runtime error for problem 6 on testcase 36, even if my logic is correct: https://codeforces.com/contest/1324/submission/74307112 Can someone help me regarding this? Thanks!!!

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

Can anyone help me understand why my solution to Problem E is wrong?

solution

I used DP[n][h]. Passed 39 test cases. Failing on 40.