Автор deltixlab, 3 года назад, перевод, По-русски

deltix

Привет, Codeforces!

Вас приветствует компания DELTIX. Мы были основаны в 2005 году и являемся одним из лидеров в разработке программного обеспечения для исследований в финансовом домене и продуктов, решающих различные задачи системной и алгоритмической торговли. В 2020 году DELTIX присоединился к EPAM. Основной нашей задачей является быстрая и эффективная реализация перспективных идей в прорывные продукты.

Мы являемся экспертами по следующим направлениям:

  • сбор, хранение, обработка данных
  • моделирование данных
  • тестирование и внедрение математических моделей

Поэтому в нашей команде ценятся такие навыки, как

  • работа с алгоритмами
  • написание высокоэффективного кода
  • обработка потоков данных с минимальными задержками

Мы рады сообщить, что с июля 2021 года один из наших продуктов TimeBase Community Edition является частью open source сообщества FINOS.

TimeBase — это многофункциональная система потоковой передачи данных с открытым исходным кодом, сочетающая в себе базу данных по работе с временными рядами, брокера сообщений и фреймворк по моделированию данных и сериализации. Первоначально TimeBase был разработан для работы в финансовой сфере. Тем не менее, мы не останавливаемся на достигнутом и беремся за новые амбициозные задачи в других областях, таких как IoT, облачные вычисления, кластеризация, высокопроизводительные вычисления, параллельная обработка данных и big data.

Читайте больше о нас

Ближайший год, раз в сезон, мы будем рады приглашать вас участвовать в DELTIX раундах на Codeforces. Присоединяйтесь ко второму из серии наших раундов — объединенному раунду Div.1 и Div.2 Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2), который начнётся в 29.08.2021 17:35 (Московское время). Этот раунд будет рейтинговым и открытым для обоих дивизионов.

Призы, которые мы подготовили для вас:

1 место: MacBook Air
2 место: iPad Pro
3 место: iPad Air
1-100 место: фирменные футболки соревнования

А также 100 футболок достанутся случайным участникам (из тех, для кого этот раунд будет не первым рейтинговым соревнованием Codeforces), не вошедшим в топ-100, но попавшим в топ-1000.

Все задачи раунда, кроме последней, были подготовлены нашей командой: Vladik, netman и AleXman111.

Мы благодарим:

Участникам будет предложено 8 задач и 2 часа 30 минут на их решение. Желаем всем успешного раунда и повышения в рейтинге!

Заполните короткую анкету и расскажите о себе, если у Вас возникло желание пообщаться с рекрутерами или членами нашей команды.

Перейти к анкете →

UPD: После обработки всех отзывов тестировщиков мы решили продлить соревнование на 15 минут. Итоговая длительность — 2 часа 30 минут.

UPD2: Разбалловка для задач: 500 — 1000 — 15001500 — 2000 — 2500 — 3000 — 3500. Обратите внимание на равную сложность задачи C и D.

Спасибо всем за то что приняли участие. Желаем приятного дорешивания! (разбор)

Также хотим поздравить всех победителей раунда:
1. Rewinding
2. jiangly
3. Benq
4. Egor
5. TLE
6. ainta
7. Radewoosh
8. Golovanov399
9. ecnerwala
10. maroonrk

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

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

Another Mac Book for tourist? He has like 10 of those.

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

For me ,the blog looks really attractive and fascinating

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

Another Deltix round. Just really love these rounds. Quality problems, quality prizes.

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

Who else was surprised by looking at that waving hand gif.....

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

I am really looking forward to these prizes which I can never win.

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

100 T-shirts for the top 101 to 1000. There is 1/9 chance if I get in there :D

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

150 minutes or 135?

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

[deleted]

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

Loved your previous contest. It's great to see you back.

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

100 in (100,1000], probability=1/9=0.1111.... :)

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

Hope problems statement will be less confusing then the last time. ʕ•ᴥ•ʔっ

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

Div1 + Div2 is really good opportunity for anybody to develop programming skills

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

i hope i dont win nullptr again.

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

did anyone got those randomly distributed t-shirts ?

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

Visit the site guys, you won't regret. Also, good luck to everyone!

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

*Wind_Eagle's round announcement* Am I a joke for you?

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

    I am sure that soon it will appear above our announcement. By the way, I participated in testing and the round is cool :)

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

Tourist is going to open an apple store after this contest.you know why XD

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

Nice rewards but i don't think that I can reach top 1000th or less . :))

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

The animation that links to the main site is so cool

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

EDIT — Commented on this forum by mistake, wanted to comment on today's competition's forum

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

I might be wrong but I thought initially they offered 150 minutes and now I see 135 minutes now.

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

Probability of Me getting T shirt 100/1000=1/10 Probability of Me coming under 1000 rank 0.0000000000000000000000001

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

Tourist's Macbook has a update feature, he doesn't have to buy the lastest version.

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

Is it possible to get MacBook Air from Tourist?

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

To tell the truth, when opening codeforces, this moving arm is really scary.

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

    Oh no, he just wants to give you a big surprise.

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

the problem set of the last delix round was hard to me D:

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

I really want to reach CM in the last contest in my summer hoilday TAT

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

I love rotavirus

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

I'm curious about scoring distribution. Any predictions?

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

Please update the scoring distribution fast

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

    Ok

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

      Hello. We sent all the T-shirts to codeforces and I am sure they will be delivered to all the winners soon.

      We could not start printing T-shirts before all participants submitted their actual data.

      Sorry for the delay, but I don't know how to make this process faster.

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

        It's okay ,in fact thanks for interesting contests and interesting prizes.

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

    added, sorry for the delay

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

As a tester, I recommend you to solve all problems!

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

    Not everyone is a CM bro, I think you meant read all the problems :P

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

      actually for us even reading all the problems isn't recommended during contest understanding a problem will drain our small brain battery (small is for the battery not the brain XD) So that could affect our ability to solve a,b,c,d so read all the problems after the contest unless you see a problem being solved alot

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

As a tester, I confirm that problem statements are to the point, no long stories.

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

as a participant I couldn't even solve 2nd problem :"(

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

great contest !!

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

Being a noob, I don't know how people solve interactive problems like D... :(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

Problem D is effectively an easier version of 1451E1 - Bitwise Queries (Easy Version) (use sum = or + and to get other elements as well since we don't have xor here, it works since we have 2n queries anyway).

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

    Is that not the intended solution? If so, is there any other solution?

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

      I meant "easier" in the sense that without the xor that problem has its slightly more trivial. In that problem you have to make all the observations in this problem + another 2 xor observatioss (one to get it from 2n to n + 3, one to get it from n + 3 to n + 2).

      Also I should note that while that problem has $$$[0, 2^n - 1]$$$, the soln for E1 can solve arbitrary ranges like in this problem, only the E2 soln needs that exact range.

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

Thanks for the interesting problems! Really enjoyed problem E

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

Could only solve A, -91 incoming KEKW

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

Big dislike for Bs "funny" overflow twist.

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

Feedback on the problemset.

  • A: Cute cakewalk problem.
  • B: Ok standard easy problem (though a bit hard for its position). I don't see why you decided to consider parities instead of giving an array of zeroes and ones.
  • C: Amazing problem. The statement is clean and asks a very natural question. The difficulty is appropriate for its position. For some reason, I liked this one a lot (most likely, because the solution is just so clean and does not require any advanced technique). I was wondering if it can be solved in pseudo-linear time.
  • D: Nice problem. For me, this required some serious thinking, but the standings suggest that it is not as hard as I perceive. Maybe I perceived this one as hard because I did not realize for a long time that if I know $$$x, x\text{ and }y, x\text{ or }y$$$ then I know also $$$y$$$.
  • E: Nice problem (but a bit standard). I was pretty annoyed by the fact that the word "even" was not highlighted in the statement and the first pretest which catches the bug of allowing also sequences of odd length is the 17th. Moreover, I don't see how asking for answers on intervals makes the problem more interesting than asking just for the answer on the whole array.
  • F: Very nice problem. Knowing the chain-structure of the strongly-connected components of a tournament, this one felt easy for its position.
  • G: I just read the statement, which is amazing.
  • H: Not read.

Overall, there was not a single problem I disliked, and more than one that I really liked. The only complaint I have is that the difficulty-gap between F and G was huge, which made the contest a speed-contest for those with a rating similar to mine.

As a final remark, the images were awesome (it's the first time ever I appreciate images in statements). Whose the author of the images?

I really enjoyed taking part in the contest, which seemed to be really well-prepared. Thanks to the authors :)

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

    For C, I have a stack solution that should hopefully work in O(N).

    Solution — https://codeforces.me/contest/1556/submission/127374965

    The idea is that you keep track of open bracket sequences and completed ones in a stack and update accordingly. It works in O(N) because each value either adds a new entry in the stack or deletes a few.

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

    Hey, Is E that easy to solve ? Also there are so many people solved E. I thought of this way, we can take, if a[i] < b[i], then consider there are b[i] — a[i] opening brackets are there and else a[i] — b[i] closing brackets. So, for each i, we want to know what is the closest j, where if l = i and r >= j, then it becomes impossible to solve. But it seemed very tedious and on top of that the query is also asked on segments.

    If it is just the whole array, then it becomes very simple right ? as you can just do that above easily.

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

      The actual solution requires a few more observations but is easier to implement.

      If you take a range $$$[l, r]$$$ and toy around with the equations of what you need to add to balance elements in it from left to right, you'll see the addition requirement at a position $$$i (l \leq i \leq r)$$$ after fixing all positions $$$[l, i - 1]$$$ is just $$$\sum_{j = l}^{i} {b_j - a_j}$$$. This implies that $$$\sum_{j = l}^{r} {b_j - a_j} = 0$$$ must hold for the subarray to be fixable. Additionally we can notice that if $$$\sum_{j = l}^{i} {b_j - a_j} \lt 0$$$ for some $$$l \leq i \leq r$$$, then we can't fix this subarray as we can't fix the range $$$[i, l]$$$.

      The first can be checked with prefix sums, and the second with a range min query on the prefix sums.

      Otherwise we can notice that if we have a prefix of the subarray $$$[l, i]$$$ with $$$\sum_{j = l}^{i} {b_j - a_j} = x$$$, we have at least $$$x$$$ positions that will be the first position of some operation since there is no position with $$$b_j - a_j \lt 0$$$ which can appear before it in a chosen operation subsequence. So the answer is just the maximum value of $$$\sum_{j = l}^{i} {b_j - a_j}$$$, this can also be calculated using range max query on prefix sums.

      The implementation is pretty short except for the actual RMQ template.

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

    I missed the word "even" in the 5th question and was stuck on wa on test 17th. I think this should be highlighted given, they represented the sequences ending with dot. But, this is error from my side, have to be careful from next time :(

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

Problem C test 13. Couldn't debug my code.

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

The only prerequisite for D is this equation -> a + b = a&b + a|b

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

Also, is there any way to solve E if we can choose an integer $$$x$$$ and increase / decrease the specified elements by $$$x$$$ instead of using 1 each time? I misread the statement and tried to solve this for quite some time.

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

My solution to G (which passed pretests) runs in 4.5secs and takes 1130MB of memory in the worst case. Oh, woe is me!

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

C murdered my brain I felt I was so close :(

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

    Yup, here is the comment I was going to write. Weirdest problem for me as it looks so easy and still I don't have an approach I can have confidence in. I threw everything I had at it and it is still unsolvable, waiting for the editorial, yey.

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

https://codeforces.me/problemset/problem/727/C (same as today's D because a+b = a&b + a|b)

found this by googling and solved.

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

In Problem E, I didn't find that k is always even, so I wasted my time for meaningless debugging. sad.

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

Is 4^n meant to pass in F?

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

C and D are just boring standard problems.

E is yet another prefix sum transformation problem.

F is basically a rip-off of this.

0 interesting ideas out of the first 6 problems.

At least there is no problem which requires constant optimization.

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

how to solve C

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

    stack + dp

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

      Not really necesary, you can solve it easily in $$$O(n ^ 2)$$$ by taking all opening brackets associated with a certain position $$$l$$$, then iterating from $$$r=l+1$$$ onward as long as it can be a valid bracket sequence, eliminating matching ranges, it leads to a pretty simple and elegant solution.

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

    Hint 1: Take the number of closing brackets as negative. Сount the current amount.

    Hint 2: Start from every odd position (Open brakets)

    Hint 3: For each starting position, go through all the positions and try to remove some of its brackets (Do not use some opening and some closing ones for the current position).

    Hint 4: Remember that you may have a lot of opening brackets that you need to use (you have the right to remove only the starting ones)

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

Felt really good when I submitted B and C, only to have that feeling snatched away by pretests 2 and 9 respectively :(

Great problems though, interested in knowing the corner cases.

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

problem D is same as this problem.

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

Why is my problem B code giving run time error? Can anybody please help me? https://pastebin.pl/view/95d9737e

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

    For array 6 6 1, the j you are finding in the inner loop will be -1, resulting in runtime error.

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

For problem H, I think we need to fix the edges between the k special nodes (since there are at most 2^10 such ways) and then use min cost matroid intersection for the rest of the edges, thought about the solution, but couldn't implement it during the contest.

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

    I just coded that and it seems to be too slow for a big case.

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

    It works. Unfortunately, I was too dumb to realize that out of the edges connecting vertices $$$k+1\ldots n$$$, you only need to include those that are part of the MST of vertices $$$k+1\ldots n$$$, so I spent a lot of time optimizing (and eventually passing) my solution that was a factor of $$$n$$$ too slow (matroid intersection on $$$O(n^2)$$$ edges). :P

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

      It looks like I need to optimize my weighted matroid intersection code :(

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

      There are few AC submissions only adjusting the answer greedily, check these:

      127391319 and 127391995...

      The first one is just finding and applying the current optimal exchange operation repeatedly. And the second one is applying any cost-reducing exchange it finds (with random and time trick).

      I think if we can prove that there always exists a path from any non-optimal to optimal solution (similar to those k-maximum spanning trees or degree-restricted spanning trees algorithm), these solutions are correct. Since the maximum answer is n*maxw, and each time your answer will definitely decrease.

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

How to solve E, many people solved it ? I thought of this way, we can take, if a[i] < b[i], then consider there are b[i] — a[i] opening brackets are there and else a[i] — b[i] closing brackets. So, for each i, we want to know what is the closest j, where if l = i and r >= j, then it becomes impossible to solve. But it seemed very tedious and on top of that the query is also asked on segments.

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

    Construct a bracket sequence as you've described. It is impossible if the bracket sequence is not a correct bracket sequence. Otherwise, the answer is the maximum balance of open brackets and closed bracket on a prefix, since each operation corresponds to the removal of one or more adjacent open and closed pairs, e.g., xxxx()xxx()xxx()(), and we will always try to remove the adjacent pairs that reduce the maximum balance.

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

Edit: Somehow the wrong solution also passed system test

Weak pretests for E

I found a counter-example for my approach that passed pretests but I'm sure will fail system test because I forgot to handle one impossible case. (When there exists a negative prefix sum of $$$b[i]-a[i]$$$ starting from $$$l$$$ in a query)

Can't believe that there are 20 pretests yet none that there are none that targeted this rather common mistake

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

    Wow lol my code doesn't pass that case either since I had a typo in my segtree :\ also wondering why pretests didn't have anything similar to this.

    EDIT: Systests weak too lol it passed

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

    Same, my solution only uses a min RMQ and doesn't use a max RMQ to check the sum is always negative.

    The systests are weak so it passed LMAO.

    Counter example:

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

    Now I suspect the test generator generates $$$\sum_{1}^{i} b_i - a_i >= 0$$$ at all positions and just chooses $$$0$$$ positions for the queries. Now I'm curious if the author's soln even handles it (not that it matters since no correct soln got rejected and there is a provable soln).

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

Any hints for B?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Store the frequencies of parities If absolute difference between odd and even parities if greater than 1 then -1 Else either both parities are equal(n is even) or one parity is +1 of other (n is odd ) For n even ,you can place like odd even odd even.... or like even odd even odd For n odd ,you have to start with the parity which is in more frequency . Now for calculating swaps i just checked for 0 ,like what is the min ways to place a 0 at the desired position .if i do that for every 0 ,automatically 1 will get placed at proper positions My submission

    https://codeforces.me/contest/1556/submission/127355908

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

Anyone wants to share his thought process for problem B.

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

When you finally get an AC on problem C with a linear solution, then you find that the problem can be solved in quadratic. QQ

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

I have a doubt. Why is the value of n given as 1000 for C, As this can be easily solved in O(N) time, is it to keep the answer within 64 bits ?

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

    There is an easy $$$O(n^2)$$$ solution to this problem. However, both you and I use linear solution which requires two stacks.

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

      yeah I know but they could have easily increased the value of n, as a linear solution exist, I am confused why keep n small?

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

I hate weak pretests.

Look at my code for B and E the first time.
B:if (tot=n/2+1) cout<<chk(1)<<"\n";else {puts("-1");return;}
Noticed that there is only one = in the code,but it can passed the pretest!
It can be hacked by datas like 1 3 2 2 2 but it passed the pretests.

E:int Max=max(mx[l][k],mx[r-(1<<k)+1][k])-d[l-1];int Min=max(mx[l][k],mx[r-(1<<k)+1][k])-d[l-1]; Noticed that the Max and the Min are same!!!
it can be hacked by datas like 2 1 2 1 1 2 1 2 but it passed the pretests.

Luckily I noticed these mistakes and resubmitted them.

These mistakes will be only made by few people,but both of them are wrong obviously.
I wonder why the pretest are so weak that these two obviously wrong code can pass the pretests.

I can't imagine how mad will I be if I don't find these two mistakes and get FST!!!

I want to say,it's not funny to make weak pretest and see a lot of $$$\color{red}{\mathrm{-1}}$$$ on the standings.

update:It seems that my first code for E can pass not only the pretests but also the system tests!I don't know how the gen work.

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

    This means there are no queries in the system tests + hacks, for which the minimum suffix sum of the interval $$$(a[l] - b[l], \ldots, a[r] - b[r])$$$ is negative and the maximum suffix sum is positive? How is that possible even with random samples?

    I must have misunderstood something in your code.

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

      Actually that means in the system test, for each $$$[l_i,r_i]$$$ :

      • $$$\sum_{i=l}^r a_i\neq \sum_{i=l}^r b_i$$$ , or
      • $$$\min(b_l-a_l, ..., b_r-a_r) \ge 0$$$ or
      • $$$\max(b_l-a_l, ..., b_r-a_r) \le 0$$$

      I think that maybe possible when the data is taking randomly.

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

        there $$$a$$$ and $$$b$$$ means the prefix sum of the arrays $$$a$$$ and $$$b$$$ in this problem :D

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

      Your understand is right.And that's why I say the system tests for E are very weak.

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

    Weak Pretests and System Tests are like s**t

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

I spend so much time thinking the reason why I only need to output the k-th smallest element in Problem D. I thought it would be very important. However, it doesn't.

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

I literally hated D. I thaught my solution was wrong just because I was finding the whole array within 2*n queries and thaught it was impossible to do so. However, all the other problems were great!

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

Why are jiangly solutions not being judged are they suspecting he's cheating or something?

Edit: they did but they were so late

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

why this submission can pass Problem E? 2 1 2 1 1 2 1 2 the answer of this Sample should be -1,but the result of this code is 0

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

One of the best rounds in a while.

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

Even D has weak systest in this set. My code that only uses the information of ai & ai+1, ai | ai+1 passes systest

it cannot distinguish 0 3 0 3 and 1 2 1 2 so it should be wrong and it prints wrong answer, but the systest is passed.

I think the problem was really nice but not data sets :(

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

The pretests of Problem B is too weak lol.

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

Lucky to get to the top 1000,So hopefully get a T-shirt (laugh).

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

The system test for the problem E is very weak.

For example, the code that outputs 1 in

2 1

2 1

1 2

1 2

passes the system test.

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

An amazing fst about B

I submit ↓ get a fst T_T

void solve()
{
    int n;
    cin >> n;
    int a[maxn]{};
    vector<int> b, s;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] & 1)
            b.push_back(i);
        else
            s.push_back(i);
    }
    //...
}

then I find bug long time find:

void solve()
{
    int n;
    cin >> n;
    int a[maxn];
    vector<int> b, s;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] & 1)
            b.push_back(i);
        else
            s.push_back(i);
    }
    //...
}

can AC

I used to think that initializing with {} wasn't too slow . I was wrong.

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

    You may initilize an array of maxn elements for $$$10^4$$$ times, that will certainly cause TLE. Note that it is guaranteed that the sum of n over all test cases does not exceed $$$10^5$$$.

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

why tourist is not in top 20...after solving 1st 6 problems in 30 minuits :[

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

For problem B , i converted array in such a way that for odd numbers from left to right i took them as 1 , 3 , 5...so on and similarly for even i took them as 2 , 4 , 6 ,......(like coordinate compression) and then calculated minimum adjacent swaps to get sorted permutation.

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

When would be editorial out?

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

    you are wrong, TL receives a solution from one of the testers, which we marked as correct. Please try the hack again, I removed this solution.

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


      Thanks!

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

        Thank you for complementing our tasks with test cases! I am sure that the participants who will solve these problems in the future will appreciate this. Apparently, we missed some extreme cases.

        Thanks!

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

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

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

Great contest! Most problems are nice. I like G, and H is a good and typical 300iq problem.

Maybe I could blame on the weak tests though? :)

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

How my implementation bug accidentally got me a lucky AC in F:

for (int mask = 1; mask < 1 << n; mask++)
{
  int bit = __builtin_popcount(mask);
  for (int submask = ...)
  {
    ...
    if (__builtin_popcount(submask) % 2 == bit) f[mask] += curF; // <---- this line does nothing
    else f[mask] -= curF;
  }
}
»
3 года назад, # |
Rev. 2   Проголосовать: нравится -66 Проголосовать: не нравится

Hello,queueforces!:(

I used another account to take part in this contest,and in fact,I don't think this contest is of high quality.

Problem B 1556B - Take Your Places! is too hard for div2B(since its code is too long) and Problem D 1556D - Take a Guess and E 1556E - Equilibrium is too easy for div2DE.In fact, I think Problem D is very similar to a question in a CF contest before, and I will try to find the original question later.

In addition,for the first 10 minutes of this contest,I'm just waiting.In queue,In queue,In queue.This has seriously reduced my contest experience.

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

When will the list of random t-shirt winners be published?

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

tourist doesn't update his macbook, he gets a new updated one.....

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

Can anyone kindly help me to find the bug in my solution of problem C

at each index i maintain a list of open and close brackets using two arrays op and cl, ex.

A: 5 3 4 2
op: 5 0 4 0
cl: 0 3 0 2

Then I do the traversal in array from left to right and whenever I come to closing bracket index i, I do a traversal from i-1 to 0 where If I find the corresponding opening bracket I add it to my answer, and update op at that position and cl at position i, and during my traversal from i-1 to 0, all the j where cl[j] == 0, I add 1 to accomodate from cases like two regular bracket sequence besides one another [ ()() ]. I do this for all i from 0 to n-1 and output the answer

My Solution

Any help will be appreciated

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

Hi coders .. can you help me ? how can I begin in DP topics ?

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

    You can try Atcoder DP contest or CSES Dynamic Programming But I recommend you not to post this here , or you will get many downvotes , just like me

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

I'm sorry to ask this but when will the list of random t-shirt winners be published?Thank you very much!

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

    I made a list with seed = 12176 (Miracle03's score):

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 118 126 140 152 161 165 167 177 180 181 183 186 193 194 199 202 219 225 229 239 243 258 260 262 269 275 277 292 298 299 300 303 310 319 326 360 373 381 383 402 427 429 435 447 453 454 461 466 471 478 491 504 519 520 524 525 532 537 539 543 544 548 552 554 556 577 585 622 625 658 665 670 711 717 720 730 735 737 780 792 798 829 844 845 851 860 882 906 908 911 913 919 921 925 926 928 960 963 971 977
    
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +186 Проголосовать: не нравится

Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1556 1 Rewinding
2 1556 2 jiangly
3 1556 3 Benq
4 1556 4 Egor
5 1556 5 TLE
6 1556 6 ainta
7 1556 7 Radewoosh
8 1556 8 Golovanov399
9 1556 9 ecnerwala
10 1556 10 ugly2333
11 1556 10 maroonrk
12 1556 12 nick452
13 1556 13 BigBag
14 1556 14 Um_nik
15 1556 15 tatyam
16 1556 16 yhx-12243
17 1556 17 Subconscious
18 1556 18 Maksim1744
19 1556 19 Sugar_fan
20 1556 20 MonkeyKing
21 1556 21 Nyaan
22 1556 22 tourist
23 1556 23 ksun48
24 1556 24 VivaciousAubergine
25 1556 25 gamegame
26 1556 26 SSRS_
27 1556 27 zscoder
28 1556 28 xtqqwq
29 1556 29 LJC00118
30 1556 30 Isonan
31 1556 31 kobae964
32 1556 32 abc864197532
33 1556 33 JettyOller
34 1556 34 dlalswp25
35 1556 35 Rubikun
36 1556 36 Karry5307_AK_NOI2024
37 1556 37 hitonanode
38 1556 38 MoRanAirConditioner
39 1556 39 QAQAutoMaton
40 1556 40 aaaaawa
41 1556 40 receed
42 1556 42 cnoi
43 1556 43 endless-chase
44 1556 44 huhaoo
45 1556 45 risujiroh
46 1556 46 gop2024
47 1556 47 orzdevinwang
48 1556 48 mango_lassi
49 1556 49 Amoo_Safar
50 1556 49 pikel_rik
51 1556 51 feecIe6418
52 1556 52 maspy
53 1556 53 tute7627
54 1556 54 uwi
55 1556 55 PinkieRabbit
56 1556 56 oleh1421
57 1556 57 Tlatoani
58 1556 58 _h_
59 1556 59 never_giveup
60 1556 60 kmjp
61 1556 61 leaf1415
62 1556 62 moe.tsuki
63 1556 63 Toxel
64 1556 64 Noam13
65 1556 65 noimi
66 1556 66 Egor.Lifar
67 1556 67 tzc_wk
68 1556 68 turmax
69 1556 69 AliShahali1382
70 1556 70 Monogon
71 1556 71 lucaperju
72 1556 72 AlexLuchianov
73 1556 73 ezLadder
74 1556 73 nutella_waxberry
75 1556 75 vkgainz
76 1556 76 eecs
77 1556 77 Farhod
78 1556 78 nuip
79 1556 79 Noam527
80 1556 80 dfcmd
81 1556 81 KADR
82 1556 82 fanache99
83 1556 83 hank55663
84 1556 84 Froggay
85 1556 84 dl720125
86 1556 86 minakami
87 1556 86 starusc
88 1556 88 BurnedChicken
89 1556 89 AQT
90 1556 90 dorijanlendvaj
91 1556 91 Itst_boyfriend
92 1556 92 Imagine076
93 1556 93 yuyue
94 1556 94 Aleks5d
95 1556 95 SirShokoladina
96 1556 96 sd0061
97 1556 97 kotatsugame
98 1556 98 magnified
99 1556 99 yzc2005
100 1556 100 wangziji
108 1556 108 _wrz_
110 1556 110 jtnydv25
112 1556 111 Karuna
118 1556 118 conan1412yang99
121 1556 121 natsugiri
131 1556 131 Rafbill
133 1556 133 se1ka2
135 1556 135 maximumSHOT
145 1556 145 MAOoo_Love_Molly
151 1556 151 AK-Dream
157 1556 157 Ant_Man
163 1556 162 ShadowLight
176 1556 176 jovialll
177 1556 177 PaiGuLong
179 1556 179 bthero
182 1556 182 noshi91
183 1556 183 pealfrog
185 1556 185 aesKawaii
198 1556 198 Kite_kuma
204 1556 204 rembocoder
208 1556 208 est_stella
209 1556 209 torisasami
236 1556 236 Pub
253 1556 253 cn449
258 1556 258 HailHomura
271 1556 271 Seyaua
272 1556 272 egor_bb
276 1556 276 lavish315
301 1556 302 Hemose
320 1556 320 ne_deyan
360 1556 361 2little2late
379 1556 380 cscse
382 1556 383 Septimelon
397 1556 398 pb0207
400 1556 400 AceKing
413 1556 414 average_frog_enjoyer
421 1556 421 phocom
441 1556 441 Cadillac
453 1556 453 18Michael
454 1556 453 lgzhy12138
470 1556 471 Nson
471 1556 472 WA_King
479 1556 479 Emiso
480 1556 481 Bohun
484 1556 485 eggag32
504 1556 505 Wailydest
525 1556 526 geschmack_cr7
529 1556 530 ExplodingFreeze
530 1556 531 RBurgundy
540 1556 541 Maezra6
548 1556 549 DimaTomsk
553 1556 554 syksykCCC
561 1556 562 LoadinGG
563 1556 563 Teja-Smart
575 1556 576 dannyboy20031204
581 1556 581 _FireGhost_
588 1556 588 ljcleo
603 1556 603 yash.gupta224a
608 1556 609 pooty
613 1556 614 TKT_YI
633 1556 634 GGN_2015
634 1556 634 Alchemi5t
636 1556 637 Setsuna
639 1556 637 Zesty_Fox
641 1556 642 spy20051623
647 1556 648 TheBlackDog
658 1556 659 retawB
666 1556 667 __23333
673 1556 673 b3ng
684 1556 685 clyring
688 1556 689 TearsFreeze
718 1556 719 -14
723 1556 724 ShJ
746 1556 747 BSBandme
752 1556 753 emthrm
770 1556 771 ouqingliang
774 1556 775 DDima
778 1556 779 TsukikoTsutsukakushi
783 1556 784 Misaka23336
787 1556 788 Aeon
789 1556 790 PsephurusGladius
811 1556 811 Kniaz
813 1556 813 Satoru
819 1556 820 Dormi
823 1556 824 MahiruShiina
830 1556 830 MaddyBeltran
860 1556 860 YanLei
879 1556 879 sapphire15
880 1556 879 ikaurov
884 1556 885 YxqK
887 1556 888 LoneNut
894 1556 894 zhylj
895 1556 896 Osaaama
913 1556 913 Kuzey
914 1556 913 apilat
928 1556 929 vaibhavvg
939 1556 938 this_is_ami
944 1556 945 Yahli
948 1556 949 flashsonic
952 1556 950 tobias.glimmerfors