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

Автор vovuh, история, 3 недели назад, По-русски,

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 за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье ZeroAmbition Степановой, Михаилу pikmike Пикляеву, Максиму Ne0n25 Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

</almost-copy-pasted-part>

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

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

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

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

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

Which contest coincided with the original timing?

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

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

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

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

Good luck everyone !!!

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

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

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

What does mean by ""?

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

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

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

So excited for first contest. Good luck everybody!

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

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

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

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

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

Good luck everyone. High Ratings.

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

Hope that I can solve A-B-C.

Good luck guys <3

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

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

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

Hope to become expert after this round

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

I hope to get blue in this contest

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

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

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

Hope problems will not be indirect like this

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

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

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

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

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

Good luck Everyone

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

Good luck Everyone

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

Hope i will be green after this round :))

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

I use this site during contest ;) Asoftmurmur

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

I use this site during contest :)

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

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

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

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

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

Good to see that vovuh is the writer.

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

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

»
3 недели назад, # |
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?

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

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

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

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

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

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

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

Thank you very much for the rating friendly contest

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

What is the 8 test case of problem D ?

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

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

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

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

    I used PBDS.

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

      how?

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

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

          Can u please explain — "st.order_of_key(mp(arr[i]-arr1[i]-1,inf))"--- In this part of your code,why you used inf?

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

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

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

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

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

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

    What is wrong with my approach ? ;-;

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

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

  • »
    »
    3 недели назад, # ^ |
    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)

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

      You have to sort array c as well, otherwise this 2 pointer technique will not work.

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

    thanks for taking your time to write an explanation.

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

There's no one later than me to solve A! I like playing with the tetris game,but I do not like this problem!

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

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

    Gradually sort?

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

    sorting them will change the order of the indices

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

    • »
      »
      »
      3 недели назад, # ^ |
      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$$$

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

    deduce condition ,suppose if ai-bi=di; then we need all di+dj>0 (j>i)pairs (counted once)

    for this make a array d=ai-bi you can divide array into three parts — positive(np) ,negative(nn) ,zero(n0); solve separately for zero , positive and negative;

    we can get our condition satisfied in three way , 1. positive di pairs 2. zero paired with any positive di 3. positive negative pairs where magnitude of positive is bigger than negative;

    a1=np(np-1)/2 (Ist cond); a2= n0*np(IInd cond) ; and for a3(IIIrd cond) ,you can loop in (O(nn+np)) time and at last ans=a1+a2+a3;

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

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

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

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

Lightning-fast system testing

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

What is the 8 test case for problem D?

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

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

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

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

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

    I believe it's called dynamic programming.

  • »
    »
    3 недели назад, # ^ |
    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$$$.

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

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

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

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

    state are index and modulo

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

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

»
3 недели назад, # |
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?

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

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

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

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

Appologize for the round, sorry.

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

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

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

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

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

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

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

    Speed is really need. lol

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

    vovuh made them easy to please div3 ppl

    here

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

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

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

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

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

        Don't coordinate anymore divs 3 rounds )

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

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

      • »
        »
        »
        »
        3 недели назад, # ^ |
        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.

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

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

Speedforces

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

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

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

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

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

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

can anyone please help me with the 4th problem

»
3 недели назад, # |
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

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

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

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

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

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

What's wrong with this submission for D? https://codeforces.com/contest/1324/submission/73081429

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

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

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

Hey guys Can anyone tell me

Why this submission fails :https://codeforces.com/contest/1324/submission/73068802

and this one passes: https://codeforces.com/contest/1324/submission/73082736

I'm not able to find the problem can anyone point this out with an example.

Thank you!

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

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

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

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

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

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

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

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

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

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

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

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

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

Hack for B?

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

»
3 недели назад, # |
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

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

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

    Yeah i mean i totally forgot about that test case.. I mean i knowingly did this when i should have not done it and it would have passed.

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

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

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

it is my first time to try in E

but i got WA on test 40

anyone can help why it is WA

73074570

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

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

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

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

73087070

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

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

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

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

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

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

          My main doubt was in the second DFS. Thanks !

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

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

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

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

  • »
    »
    3 недели назад, # ^ |
    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

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

»
3 недели назад, # |
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

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

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

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

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

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

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

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

    i think. YES, as n=5000

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

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

    Yes, since sum of all n is <= 5000.

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

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

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

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

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

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

»
3 недели назад, # |
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 :)

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

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

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

Are you guys mad? I have missed the contest due to change in timing, now I can't attend div1 challenges.

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

Vovuh you are great author your problems are amazing

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

Hack case of B . 1 3 2 2 2

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

[deleted]

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

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

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

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

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

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

    • »
      »
      »