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

deltix

Привет, Codeforces!

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

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

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

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

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

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

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

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

1 место: Самая желанная консоль 2021 года PlayStation 5!
2 место: Nintendo Switch
3 место: Nintendo Switch Lite
1-100 место: фирменные футболки соревнования

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

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

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

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

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

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

UPD: Разбалловка для задач: 500 — 1000 — 1500 — 2250 — 2250 — 3000 — 3250 — 3250.

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

Также хотим поздравить всех победителей раунда:
1. tourist
2. Radewoosh
3. Um_nik
4. maroonrk
5. ecnerwala
6. jiangly
7. SSRS_
8. Petr
9. scott_wu
10. Maksim1744

Особые поздравления хотим выразить первой тройке лидеров! Мы постараемся как можно скорей передать вам ваши заслуженные призы :) К сожалению, мы сейчас не можем отметить людей, получивших 100 случайных футболок, по причине того, что поиск читеров не завершен.

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

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

So Which game are you going to play tourist on your brand new Play Station 5?

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

Crossing my fingers that "we value skills like high-performance coding" doesn't mean "Anyone who uses java is going to have a concussion from banging their head against their desk because of how tight we made these time limits"

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

    If you think about it, screencasts are high-performance coding.

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

    Will it be better if time limits are according to the languages?

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

    Well, it's a finance/trading company. Taking the phrase "make really good decisions really fast" to a completely new level is the only chance they have to be profitable. Their limits are imposed by competitors, not arbitrarily chosen. (That also gives you all the more opportunity to fail in this industry.)

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

    Still not as tight as ur mom

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

The more different rounds, the better! I also really hope that the tasks will be good.

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

Nice T-shirt :)

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

"Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces." Wait, so we're gonna have one of these every 3ish months? :O

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

I would love to have that PS5.But I won't be able to achieve that this time.Maybe 5-6 years later in some div1 + div2 I will get PS6!!!

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

Best of luck to all the participants :)

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

Warning: This round will be slightly harder, because I will be on a plane instead of donating my rating.

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

Please make the pretests strong! That's all I ask.

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

Woah 8 problems? This one is big.

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

Nowadays codeforces is giving a lot of gap between two contests

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

Nice prizes !! Hope to win one of them in the future :))

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

8 problems in 2 hour and 15 minutes... are we going to face some easy questions!

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

Me being a 'specialist' calculating my probability of winning a PS5 in a combined round. But I forgot I'm bad at probabilities and even CP (-_-)

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

Can I have a T-shirts from the random generator :)))

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

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

    I actually disagree with my meme I don't want to enjoy my new color

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

Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces.

I'm excited to see that! Woahh, more div.1 + div.2 means more participating for me

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

Time for SpeedForces.

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

 when you know there are playstation 5! you must be ready for the contest

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

I feel a little envious about the top three.

QQ图片20210512215006.gif

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

I'm very excited for this one, since it's happening after a long time. All the best everyone.

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

to all testers whose list will appear very soon

Testers were probably excited to put their feedback comments. Don't delay it further.

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

I already knew that the PS5 is going to be one of LGM's. :)

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

Deletdd

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

Hope Bugaboos will be good. May random be on my favor (that doesn't mean i want t-shirts :p)

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

how many bugaboos?

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

As a tester, I can assure the problem set is fun, well atleast the first half surely is. Good luck!

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

Good Luck everyone for this round!!!

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

We have four purple questionsetters!

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

Where is Anton when you need him?

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

kindly don't put a super hard and unconventional div2 B problem.

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

The winner of the contest will be probably have no time to play PS5 otherwise he wouldn't be the winner in first place :D

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

what about scoring distribution? Also as a contributor i want some testing.

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

Is it rated???

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

:)

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

everyone talking about prizes, I'm thinking to become candidate master asap.

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

    bro, you improved a lot after the 17th or 18th contest that you gave. Can you tell what specifically did you do or how did you practice in that period

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

is it impossible to improve in codeforces without watching anime ?

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

hoping this will not be a div 1.5 round !

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

Score distribution looks sus

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

Can someone clarify that will it be rated for Div. 2 participants or not?

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

is it going to be a difficult or moderate one looking at the scoring distributions

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

Codeforces is broken on my PC but it's working fine on mobile. Is it only happening to me?

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

It will be my first contest as a specialist. Hoping for the best.

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

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

deltix round == bad round

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

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

Looking at the standings, it seems Tourist is in urgent need of another PS5 ! Oh by the way, is there going to be Bugatorial for this round?

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

What's wrong with B??

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

    Observation.. For any two pair you need to perform 1 1 2 1 1 2 or 2 1 1 2 1 1 or 1 2 1 2 1 2 or any valid formation ;)

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

      1 2 1 1 2 1 works also...Indeed a good observation problem

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

      Yeah... I got the hint just after I expressed my frustation here. It was my problem I read the question hastly. I think the basic step is how to swap two numbers without third variable logic.

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

    Just upvoting you because your name is Luffy
    \m/_(>_<)_\m/

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

And i thought the contest will be easy since it has 8 questions.LOL!!!!!!!!!

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

I really wish an easier problem was in place of D. Instead of writing this comment, I would have been solving a problem that was actually in my league. Contest would have been more enjoyable :(

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

Out of > 18 000 registered participants only 8 700 submitted anything after 90 minutes.

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

speedforces

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

D is too tough to even try

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

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

statement of C is shit

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

Please, help understand problem E

this bruteforce solution gives wa on 2-nd and 3-rd samples

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

    Different sequences of operations have may have different probabilities, so you can't just calculate sum and divide by their number.

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

Problem statements should have been more clearer.(also no need of that image in each ques) :(

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

Oh wow! Not only bugaboos were great, but also these beautiful pictures in every bugaboo! Awesome contest.

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

how to solve the problem D ?

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

    You would only need to test up to 2**p = 32768 bitmasks, and I think which can be optimised.

    I have yet to pass systests however.

    Edit: Failed systests, my solution is actually O(N * 2**(2*p))

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

      I came up with a solution, with complexity O(const * n * 2 ^ p) but it's TLE.

      how fast did you check is the mask good or no ?

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

        You don't need n, you can maintain a map with the number of each state. As for iterating subset it is 3^p. So total complexity is O(n + 3^p)

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

Thanks for the interesting problems!

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

Ok C is the worst problem I have ever seen. I spent about 40 minutes staring at it and I didn't understand the statement till now. How could this problem even got accepted by coordinators?

Apart from that the problems were great but this really ruined the contest for me.

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

Such a lousy statement on Problem C, it's a shame. Incomprehensible what this is about. The setters work hard to develop and work out great problems, and then ruin the result with an incomprehensible statement text. Why? I do not get it.

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

wasn't able to understand what the task C meant till end of the contest ;(

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

Pun Intended, tourist give me your old play station. :)

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

Am I the only stupid one who write about 100 lines for C and get 6 was??? It feels terrible (especially I notice other people in the same room pass this bugaboo neat and quickly :(

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

My strategy after struggling for hours with C..

Just relax in the forthcoming Deltix Rounds. Peace.

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

could someone provide counter case for this submission of problem c. Got 6 WA on this problem.

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

I hate combined rounds! I was sure that I would be able to hack a few people in D because my solution was randomized and usually, there are people who still don't seed their random number generators. However, because the round was combined and the room was mostly greens or cyans, there were only two solutions in my room, one of which had good random and the other didn't seem to have random at all.

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

    Wow, how do you do it without randomisation?

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

      I tried all possible subsets of (sensible) currencies (there is at most 2*p = ~30 of those) XD I implemented custom bitset and pruned execution if some subset yielded less than n/2 interested peoples. I doubt it will pass max tests, it passed pretest within 700ms though. For reference: Submission 117911694

      Edit: Systests passed in 750ms :D Hooray

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

        I did almost the same thing. Maybe you can continue the loop when this state's number of $$$1$$$ is less than or equal to the current answer.

        And it got TLE :(

        Then I tried to break at 2.8s, it passed again :((

        And my solution got hacked(WA) yet...Now I wonder whether there's a solution without random

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

          The main difference between our solutions is the presence / absence of prunning. What do I mean by that?

          Consider that you use some subset of currencies (for example currencies 100110) and you've concluded that it's impossible to satisfy at least $$$\frac{n}{2}$$$ people. This means that you don't have to evaluate all "super-masks" (supersets of currencies), for example 110110, 101110, 100111 and any other. And I see that you evaluate the satisfacion for those masks anyway. In my case, the reccurence does not "enter" any states corresponding to superset (which is hard to do with loop).

          The other difference is the computation of guests satisfaction. From what I see your logic is somewhat convoluted because of your data structure — you have bitset mapping which person likes what currency, and I have it the oposite way — which currency is liked by whom. It gives fast computation to check if enough guest will be satisfied (it allows for computing bitwise and in O(n/32)).

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

            You are right. I totally don't consider supersets of failed masks. But I remember bitset's time factor is divide by 32 or 64 too...

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

        I did similar thing and got TLE on test 112!!!

        Edit : It can be saved if I get a T-shirt!

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

        I tried to implement similar idea, but in python. Guess I had no chance

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

        Can you explain your approach?

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

          Yes.

          First, you start by selecting only currencies that interest at least n/2 friends. It can be shown, that there are at most $$$2p \leq 30$$$ such currencies. In my code I store their indices in vector relev (it contains only RELEVant currencies).

          Secondly, you create bitsets for your relevant currencies. In other words, you create around $$$2p$$$ bitsets of size $$$n$$$. We need those to be betsets because we need them to quickly compute bitwise and and number of ones (ie. popcount).

          Now we proceed to the reccurence. If you have some subset of first $$$idx$$$ currencies, you can either add the next one to the set or skip it and proceed with the same subset. If you added your currency, check if it satisfies at least $$$\frac{n}{2}$$$ people. If it doesn't — don't evaluate reccursive call (bitset zadowoleni, which means "satisfied" in Polish, stores the bitset of people satisfied with current currency subset; sklej method computes bitwise and). Now simply return the best of the two reccursive calls. In short, recurrence structure is as follows:

          solve(currencies subset S, int idx):
              if idx == all currencies count:
                  return S
              S' = S.union(currency number idx)
              if S' is liked by at least n/2 poeple:
                  solve(S', idx + 1)
              solve(S, idx + 1)
              return best of recurrence calls
          

          Finally you simply reconstruct the answer with all currencies based on relev vector.

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

            What would be the time complexity, O(2**(2p)) for the bitset, and O(N) for the comparison, leading to O(2**(2p)N)? Or am I missing something?

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

              Roughly speaking, yes. But note, that any solution can have at most $$$p$$$ currencies so we are quaranteed not to check all $$$2^{2p}$$$ sets even in the worst case, but only sets with size up to $$$p$$$. In the average case I believe it will compute much less currency subsets.

              Additionaly, comparison has a very low constant factor due to bitset ($$$O(N/32)$$$).

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

                Thanks, this is a nice solution, especially how it utilizes the powers of 2 to suppress the time complexity :D.

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

        Hey Wielomian, I tried running your submission — https://codeforces.net/contest/1523/submission/117911694 but it is now TLE'ing in TEST-131. Any workaround how to proceed with this?

        My submission with the same code — https://codeforces.net/contest/1523/submission/118490042

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

          I hacked it back in the day (You can see the hack at Submission 117911694). It seems that the system tests were simply weak and that there was no max test with $$$2p$$$ relevant currencies (which is weird). And thus allowed for such a solution to pass. Possibly this testcase was added after the hack for upsolvers.

          To me it seems that one must incorporate the $$$dp$$$ as described in the editorial rather then bitsets to have fast update of people counts for subsets, which I don't understand, honestly.

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

    How to solve D with randomisation (

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

      Select a random person. With probability $$$\frac{1}{2}$$$ they are in the $$$\frac{n}{2}$$$ chosen in the optimal solution.

      Then you can do bitmask DP over only the bits that they like.

      Repeat 30 times for $$$2^{-30}$$$ chance to fail.

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

        Hi, Suppose I select a person and I do all the bitmask, there are 2^p masks but in order to know how many members are there in that mask, I need to iterate all of n right ? Even with iterating only among the persons where the mask exists, I will still be needing 2^p instead of n, so the complexity becomes O(iters * (2^2p)) or (O(iters * n * 2^p) which is worse than the brute force O(n * 2^p) ). How to eliminate 'n' or another 2^p ?

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

          You count how many times each of the possible $$$2^p$$$ bitmasks appears in $$$\mathcal{O}(n)$$$ time. Then you do SOS dp in $$$p \cdot 2^p$$$ time to count for every bitmask how many times a bitmask containing all of its bits appears.

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

            Actually how to count each of the possible 2^p masks appear in O(n) time ? Wont it be O(n * 2^p) ? could you pls elaborate ?

            Also could you pls elaborate on what you are doing here ?

            for (int x = 0; x < k; ++x) {`
            `			for (int y = 0; y < (1 << k); ++y) {`
            `				if (y & (1 << x)) cou[y ^ (1 << x)] += cou[y];`
            `			}`
            `		}`...
            
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I reduced problem D into a bipartite graph problem where friends would be in one side and currencies would be in another side. Now, if we select x from friends and y from currencies, we need all x's to be connected with all y's and we gonna take maximum y such that x meets sufficient conditions.
Couldn't proceed further.

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

how will you know who will be included in the list of 100 random people who will receive t-shirts?

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

I'm so nervous that my D will get TLE. I just use something like bruteforce....

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

Fine, finally a reading comprehension round.

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

I made an assertion statement in C to check if the first character is 1 or not, I got a runtime error! I can't believe it has more than 3k AC.

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

how did testers approve C , the language was pathetic , wasn't able to get what the task meant till end...

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

Wait when you changed n upper bound to 1000 for B? I always think it should be 2000 and the requirement is 5000... i spent like 1 hour thinking about how to get better than a 3n solution but the question description :(

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

what is wrong in my submission of C link

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

OOf just lacked a tiny bit of time for D lul

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

    Tried Bruteforcing got TLE Tried Bitmasking + Bruteforcing got TLE Tried Further bitmasking + Bruteforcing contest finished

    OH NO

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

Why the next contest is after 2 weeks (⋟﹏⋞)

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

Randomised solution for D:

Randomly take a friend and assume it to be the part of the final subset now compare all other friends with this subset and use submask dp in the end to find maximum size subset. I took 25 random friends.

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

why so bad...

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

Does problem C's initial statement form a proper problem? Before the sentence 'then the sequence of items should always remain increasing in lexicographical order' was added, I couldn't found the operations like

1

2

1.1

are invalid from the initial statement.

The announcement of the addition of previous sentence was so late that it's hard to say that the impact of this problem was little.(actually, I've use so long time to debug my code which was doing something like the previous operation)

Hope for the appropriate response.

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

    It's not only "hard to read" or "hard to understand" but it's broken as a problem. I can't say it's enough to be unrated but should take into account whether making this round unrated or not. MikeMirzayanov Vladik

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

      I think this mistake is enough to be unrated.

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

        I agree. Making such a significant change to the problem statement 40 minutes into the contest is unacceptable. This contest should be unrated.

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

    I agree, the problem basically changed halfway through. I don't think this should happen.

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

      yes, the addition was not just the description. it fundamentally changed the problem.

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

    We are sorry for this issue in the statement. None of the testers and authors noticed that the formal definition of a multi-level list was not exactly correct. The statement was corrected and an announcement was made as soon as the issue was noticed. Fortunately, most of the participants followed the common sense about what a multi-level list is and authors meant exactly that.

    By the way, I think when a high-rated participant finds something strange in a problem, like statement does not match usual definitions, or some other mistake, they should report that to the authors (in any contest, not only here). It is much more probable that there is a mistake or that you misunderstood something rather than authors deliberately made a trap without mentioning it explicitly. Reporting that will help authors and save your time.

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

      Will the round still be rated?

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

        Yes.

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

          Nikolay, Is that somehow possible to retest all solutions for problem A in this contest? What I've noticed is that there are 5 lists of participants who got TL on this problem, whereas only 1 list of people passed system tests, and all of them had linear algorithm, but according to the editorial quadratic solution should pass. Thanks in advance

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

          Lost t-shirt by this shit problem, also lots of rating.

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

      so, you mean that the problems are still remain correctly even if it is mathematicaly wrong but can perdict it from some kind of fuzzy "common sense"?

      I don't so much care about whethere it is unrated or not, but the dealing with this issue to say "if youre high rated and found it strange, report it" is a question mark(as statement makes a sense without the order constraint, I have no idea but somewhere of my code is wrong.)

      Problems should have been established only by the problem itself. not depening on something lile "common sense".I hope the future rounds wont repeat and I can help it by reporting.

      I have one nice idea for preventing: let's totally get rid of STORIES :)

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

      I don't understand — there are so many problems — Anton coordinated ones especially, where the "definition" is the trick to the problem. By putting the pressure on these high rated participants, you are effectively scapegoating them to do the work that authors should have done — listen to tester feedback.

      Oh, and, "none of the testers noticed..." is just shifty phrasing. Testers complained about the statement of C saying it was confusing. You know that.

      I did not take this contest, but I am equally outraged about the way this matter was handled.

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

    I made the same mistake ,and I wasted at least one hour in it and get four WA :<

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

    Does problem C's initial statement form a proper problem? Before I got AC using the decimal numeral system, I couldn't found the operations like

    1
    2
    3
    4
    5
    6
    7
    8
    9
    A
    B

    are invalid from the initial statement.

    It was so late that it's hard to say that the impact of this problem was little.(actually, I've use so long time to debug my code which was doing something like the previous operation)

    Hope for the appropriate response.

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

who else got TLE in A? :d I think for big number of m and "1111...110111....1" this kind of solution was the main reason right?

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

Can anyone explain how to solve E?

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

The problem statement of C is unreadable.

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

[. .

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

I resolved the bug in my solution to problem C, but only 12 seconds were left. I couldn't submit it. I wish I had 1 more minute.....This is so saddening.

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

Didn't unterstand E correctly, FSTed in both C and D, bad day for me :(

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

    Not your fault, this round is shit.

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

    If you wonder how is it possible to FST in C, here's the answer:

    I stored the input in an array $$$a$$$.

    The array $$$a$$$ is an array of integers in my default source, but when I solve problem A, I changed it to char. And when doing problem C, I forgot to change it back:(

    And it passed pretests:(

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

can anyone of the testers , problem setters tell what was going through their mind when they approved the language of problem C , complete nuisance it was

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

Weak pretests on D!

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

Asking for hack: my submission for D

My solution is totally wrong but I can't hack it.

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

In problem A, I think it is immoral to write the constraints as such

t <= 1E3
n <= 1E3
.
.
.
The sum of n in all testcase does not exceed 1E4

When I read the top 2 lines I would think the intended solution to be O(n), while an O(n^2) solution would also pass.

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

I think problem C is different problem before and after the problem statement is changed.

before changing the problem statement,

1 1 2 2 1 3 3

is valid sequence(because you can make a list like below:

1
1.1
1.2
2
2.1
3
1.3

),but after changing the problem statement,this is invalid sequence.

I was very sad about this change.

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

    I've chosen the solution same as yours and get "Wrong answer on test 2."

    As allowing the "non lexicographical order" operations just extend the valid operations and the fact that "all testcases has solution", our solution have give a answer.

    but the verdict was "Wrong Answer" so I guess the output checker was checking is it lexicographical order or not.

    If the output checker was taking into consideration but forgotten to write in the statement, it's a so so FATAL MISS!!!!

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

    not gonna lie, I saw the first version of the problem. Didn't understand it at all. I only understood it from the image. I guess the image actually has better explanation that the statement its self Lol. But yeah, that is really sad :c

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

    You can provide solution with test case : 10 1 1 1 2 2 1 2 3 3 3 is it a correct test case ?

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

      with my (before the changing problem statement) solution (117891713 ),

      1
      1.1
      1.1.1
      2
      1.2
      1.1.1.1
      1.1.2
      3
      1.3
      1.1.3
      

      is provided.(after changing, this sequence is invalid.)

      You can solve (before the changing) this problem by listing all items that can appear next.

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

    I solved problems F and G after contest, and both were interesting. I also like problems D and E. Thanks for preparing this round.

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

In problem B, I realized that I needed to do 6 operations for a pair, but I multiplied 6 by 1000, although there are only 500 pairs( So I came to a more complex solution after an hour.

Maybe someone will be interested https://codeforces.net/contest/1523/submission/117914942

In this solution I am doing 14 operations for every four of numbers. If the number of numbers is not divisible by 4, then I do 6 operations for the remaining pair.

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

Hey, anyone else did not pass Problem A because they used Python??

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

    Yo bro me too, python is crap

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

      I think I will just have to stop using it. This is the second time this happened to me. I am sad cuz its just so comfortable to work with strings in python...

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

      If anything, with very few exceptions, Python's performance is more than enough for div2 participants

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

    I used Python 3 for problem A, B, and C with no issues. Maybe you just had a bad implementation.

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

What was the point on the weak pretests for A?

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

    What is the point of having 37 pretests for D and still I fsted ?

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

As a contestant, I want a t-shirt :v .. That T-shirt is so beautiful.. <3

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

Operation can only be applied if the list does not contain two identical items afterwards
Can someone explain what this statement means with respect to problem C ?

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

    It means you can't have duplicate items in the list, for example [1, 1.1, 1.1, 1.2] is not a valid nested list.

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

    This statement on tallying it with the sample explanation left me puzzled and blank!

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

The last second I found I just use rand()%n+1 to select a person randomly on problem D. That's why I got wrong answer 5 times on pretest 36. I will never forget this trap. :(

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

such a very good contest, many thanks for deltix !!!

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

This round was as good as the problem statement of C:)

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

chert

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

I misread E that he continues turning lights on until K consecutive lights are on.

Explanation of the example matches it :(

I think it is way harder than the original problem. Is there an easy way to the problem that I understood?

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

    I'm not sure if you wanted a subquadratic solution, but I think you can do it in $$$O(n^2)$$$ with the following lemma.

    Lemma: Let $$$X$$$ be a random variable that takes non-negative integer values. Then $$$\displaystyle E[X] = \sum_{i = 1}^{\infty} Pr[X \ge i]$$$.

    From the lemma, it is sufficient to find $$$\displaystyle \sum_{i=0}^{\infty} Pr[\text{There aren't k lights in a row after i steps}]$$$. This can be done with DP in $$$O(n^2)$$$ by finding the number of ways to pick $$$i$$$ lights from the first $$$j$$$ such that no $$$k$$$ of them are consecutive, for all $$$i,j$$$. Maybe there is some way to optimize this, idk.

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

abc were the most rubish problems I had ever seen

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

Finally a good round after back to back bad rounds for me.I do admit even I didn't like the problem statement of C. But that table at the bottom helped me a lot. :)

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

abc were the most rubish problems I had ever seen

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

    A and C was supposed to be non existent due to their bad quality. But I find B not that bad for a Div 2 A or an easy Div 2 B.

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

      Idk but I felt C statement was not clear enough ,add that midway change,I solved a whole of different version of it until I reread statement .Maybe I had to work upon my English:(

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

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

who else understood the statement for C because of the image?

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

Well, I was about to get purple, until my D FSTed. Do you guys know how it feels when you are about to purple for the first time and you end up losing rating instead cuz of FST ! :sob: :sob: :sob:

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

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

А все таки, как додуматься, что нужно 6 операций типа 1 2 1 2 1 2 в задаче В. But still, how do you figure out that you need 6 operations of type 1 2 1 2 1 2 in problem B.

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

    ну, в условии написано, что длина массива постоянно чётная, значит, возможно, надо одно с другим вычитать друг из друга, потом на листочке если посмотреть, то становится ясно, что нужно постепенно менять их местами, тем более, если элементов в массиве может быть 2.

    рассмотрим ситуацию, что нам нужно поменять местами a1 и a2, дальше на листочке смотрим, что нам лучше из чего вычитать и в каком порядке, лично у меня порядок был 1 1 2 1 1 2

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

after triggering it all items in the list were replaced by a single number: the last number originally written in the item number. f***, after looking at the test data I realized that I solved a completely different problem for C, I thought that the list was replaced by the last number i.e the digit written on the list. Also the sample test data contained all a[i]<=9. The problem statement just ruined it man. The writer should provide a concrete example of what he wants to convey.

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

The problem C itself was not bad
But the statement was crappy and if none of the testers noticed it, they did crappy job as testers.

I don't know what exactly is tested during preparation, but clarity of the problems statements should certainly be one of such things

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

About problem C. I read the problem sentences before the announcement and thought the answer is not always increasing in lexicographical order. So I was confused when I got the announcement. But I trust that the writers will not change the sentence in such a way that what the problem means will change and therefore I searched for what was wrong with my thought. Eventually, there prove to be nothing wrong with my thought (as there are mentions in other comments). Would I have been better not trusting the writer? I'm worried whether I can trust the writers in future contests :(

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

What a shame, there are 15 testers while none of them notice the problem in C

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

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

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

can anyone help in Problem A my same code got accepted in pypy while it got tle in python

my python submission https://codeforces.net/contest/1523/submission/117886063

my pypy submission https://codeforces.net/contest/1523/submission/117932947

Ps: I tried pypy after the contest

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

    Thats why you should consider pypy over cpython when the runtime is tight for your solution.

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

      in Pypy runtime is 200 ms only runtime is same as others n**2 is there anything cdeforces can do for this issue?

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

Большое спасибо за раунд! Задачи очень интересны в формулировке и было приятно над ними думать)

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

Now Radewoosh will be at the top of codeforces rating !!

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

I can already feel the breath of the wild.

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

After this round it is clear that why antontrygubO_o is the best coordinator on this platform.

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

ok

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

weak pretest on A!!!!

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

Weak system test on D .

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

Will there be a random distribution of other 100 t-shirts or will it be priority based like 50 to initial 1000s ,25 to next 1000s ,and likewise?

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

    T-shirts will be distributed completely randomly among the participants who have fulfilled the conditions.

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

      will the list of candidate be posted publicly or the lucky ones will get mails just curious to know?

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

        We will post all people in a comment. And also publish the script.

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

.

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

    If our analysis of the problem was not clear to you, then I recommend listening to the explanation of the solution from Errichto: https://youtu.be/2S19tjbu_48?t=270 . His reasoning completely coincides with ours when drawing up the problem.

    By the way, this problem could be presented formally, if we formulate it in terms of graphs. Then we would have got a tree, and the numbers denoted the ordinal number of the edge at the parent. As we understand now, in such a formulation, the task would be liked by a larger number of participants. But as the aforementioned Errichto notes, we wanted to make the task more interesting by connecting it with real life.

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

      Nothing bad of making the problem interesting, but what you did is just make it an unreadable piece of shit. That is NOT how one should prepare a problem.

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

        I sincerely do not understand why to show so much aggression. How would you write a statement for this task?

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

          Then why to give this task?

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

            As KAN mentioned above, the problem was read by a large number of testers, as well as by all authors. None of us found a problem in the formal definition of what a nested list is. If to answer your question briefly, the answer will sound like "we did not know that the task would be incomprehensible to some people because nothing indicated it." Of course, if we knew that the task will cause negative emotions, then we would not have added it to the round.

            We do not have an aim to hold a round just in order to hold a round. We wanted to make it good and memorable. Great efforts have been made to make the round a good one. There are people who did not want to be mentioned in the announcement, but put a lot of effort into preparation. For example, an illustrator and translator.

            I just want to point out that conclusions have been drawn regarding this situation and we will involve even more people in the next round so that such problems do not have a chance to exist.

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

              None of us found a problem in the formal definition of what a nested list is.

              That's a problem. I understood it pretty fast but I chalk it up to my experience and language skills and most importantly looking at the examples. Still, I instantly concluded that the definition is terribly written — people who don't have those language skills should struggle with it. The fact that nobody realised that when testing isn't an explanation, it's a problem by itself.

              1. Start with defining an item as a sequence of numbers (with '.' as separator). The first definition of an item looks vaguely like multiplication, the info that it's a sequence is buried in the middle of the statement.
              2. Cut out the "nested" part until you're giving an example, only then explain that it's a nested list. We're dealing with a sequence of "items" (as defined before) for a formal definition and a nested list for an informal one.
              3. The part with building it by inserting items is complicated by itself, but there's no good way around it and it can be viewed as part of figuring out the solution to rephrase it as defining a tree, so I guess that's ok.
              4. There's nothing formal about "starting a list of a deeper level" and "continuing the current level", especially considering that the word "level" doesn't appear in the statement ever again, so it doesn't provide any help connecting concepts. However, if it was obvious that an item is a sequence of integers, you can state outright that the 2 cases are a sequence with $$$1$$$ appended and a sequence with the same length but the last element incremented.
              5. "the last number originally written in the item number" — You really don't see what's wrong with a phrase "number in number"? Each item is replaced by a single integer — the last element of the item (already typedef'd as a sequence). There, done.
              6. On the output, you could've at least described what's getting printed in more detail than "print a nested list". On the $$$i$$$-th line, print the $$$i$$$-th item of your list — a sequence of integers separated by '.'.

              There are probably more details but I'm sure this would've helped a lot.

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

                Thank you very much for the detailed message! I think that everything you wrote makes sense.

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

          William is a huge fan of planning ahead. That is why he starts his morning routine by creating a nested list of upcoming errands.

          A nested list is a numbered list where a period indicates the outer list contains a nested sublist. For example,

          1
          1.1
          1.1.1
          1.1.2
          2
          2.1
          

          is a valid nested list.

          Formally, the following conditions must be met for a nested list to be valid.

          • A list and all its nested sublists must be lexicographically increasing.
          • A list can be nested inside another, if and only if, its lexicographically previous identifier exists and is nested in the same outer list.
          • No 2 list elements can have the same identifier. (Consider each row, for eg. 1.1.1 as an identifier in the list)

          Note: There may be any number of nested levels and the numbering of the lists follows base 10 (decimal system).

          Unfortunately, William has lost his original list, but he remembers the last number in each row. Help William find any valid nested list that matches the description given by William.

          Note 1:

          1
          1.1.1
          

          is not valid as 1.1 doesn't exist.

          Note 2:

          1
          1.2
          1.2
          3
          

          is not valid as it violates 2 rules

          • 1.1 does not exist, hence, 1.2 can't exist
          • 1.2 is repeated.
          • 2 is missing in the outermost list after 1, rather 3 is present.

          Hopefully, something like this could have made the task simpler to comprehend. At least I would easily get what is needed to be done if it was presented like this.

          The picture in the question is a hint to understand the question, but I don't suppose many would have bothered to look at it.

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

Thanks for the round! I enjoyed problems F and G, and the rest of the problems are nice too.

To everyone: please be respectful towards problem authors. If you're criticizing, do it in a constructive manner. It's disappointing to see a ton of comments with nothing but aggression.

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

I have never seen a round organizer answering each and every query of the participant which has been done by Vladik.Hats off man.It was a great contest .Ignore the idiots who are blaming you for tough language of the problem.You provided with pictures ,you did your best ignore the idiots.

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

Dibs on tourist's previous PS.

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

Vladik please make sure that the t-shirt reaches my address.

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

Today I received 2 messages from the system telling that my codes for problem B (117877311) and C (117883398) matches with the codes of aerfanr for problem for B (117886611) and C(117894142).

So please note that I do not share my codes to anyone and I have been using rextester.com to run my codes, which does not automatically publish any code. The match is a coincidence which has occured due to the simplicity of the solutions, For both of the submissions the main part is only 10-12 lines and the approaches are same as in the editorial. Also check that at any point, the implementations entirely different.

MikeMirzayanov Please help me and tell me if there is anything more I can do to prove the coincidence.

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

    Thanks, this issue has been resolved before you wrote. You can see that you both are official participants of the round.

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

      Thank you very much.

      It's great that you care so much that you resolved it even before I wrote.

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

Who created the question. There was a mistake in 1 problem where the range can go out

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

MikeMirzayanov,Vladik is the round declared unrated, or the ratings would be returned soon. please clarify.

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

Ratings are back

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

Will you publish a list of people who have won T-shirts or just let them know?

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

The search for cheaters is completed. Waiting for the list :)

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

For Problem C, Please anyone review my explanation.

  • We know that the sequence forms a valid list so the first element must be 1.
  • Whenever we are encountering 1 in the sequence we add it to the end of stack because all other previous depths must have encountered 1 already.
  • If we encounter any number other than 1 say x.We search from the end of stack for x-1 and replace x-1 with x.This is optimal because
  • Let's suppose the current stack is a,x-1,b,x-1,c
    Choosing the right most x-1, a,x-1,b,x -- state 1
    Choosing any x-1 other than rightmost a,x -- state 2
    It's not hard to see that state 1 gives us more choices and also includes the choices of state 2.Hence,It's fair to go with state 1.

  • Also,the sequence in stack will never repeat because
  • Suppose we got a sequence of length n .a1,a2,.......an
    In case of adding 1 It will increase the sequence length so It will change.
    In case of other than 1 It will definitely change some element of the sequence and decreases its length even though we might end up with length n again but its element will be different as It has already got changed.

P.S- I want to improve on proofs. Your review will be constructive for me.

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

Please don't downvote me, my contribution is turning negative :(

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

MikeMirzayanov, Vladik/ Guys, hurry up, please, I have been updating the site for 2 days in a row to find out the list ;(

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

Congratulations to tshirts winners! 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 1523 1 tourist
2 1523 2 Radewoosh
3 1523 3 Um_nik
4 1523 4 maroonrk
5 1523 5 ecnerwala
6 1523 6 jiangly
7 1523 7 SSRS_
8 1523 8 Petr
9 1523 9 scott_wu
10 1523 10 Maksim1744
11 1523 11 VivaciousAubergine
12 1523 12 qwerty787788
13 1523 13 aid
14 1523 14 kmjp
15 1523 15 yhx-12243
16 1523 16 LJC00118
17 1523 17 fedoseev.timofey
18 1523 18 duality
19 1523 19 never_giveup
20 1523 20 risujiroh
21 1523 21 frame233
22 1523 22 xay5421
23 1523 23 ksun48
24 1523 24 NotaMotuaQAQ
25 1523 25 oleh1421
26 1523 26 KK_Smiler
27 1523 27 neal
28 1523 28 Isonan
29 1523 29 JettyOller
30 1523 30 Ormlis
31 1523 31 Swistakk
32 1523 32 xtqqwq
33 1523 33 Rewinding
34 1523 34 mango_lassi
35 1523 35 Itst
36 1523 36 ainta
37 1523 37 Toxel
38 1523 38 dqa2021
39 1523 39 353cerega
40 1523 39 molamola.
41 1523 41 receed
42 1523 42 GyojunYoun
43 1523 43 sansen
44 1523 44 gamegame
45 1523 45 mnbvmar
46 1523 46 froggyzhang
47 1523 47 AutumnKite
48 1523 48 wlzhouzhuan
49 1523 49 Errichto
50 1523 50 Bredor
51 1523 51 ShimaRin
52 1523 52 Farhod
53 1523 53 Amoo_Safar
54 1523 54 saketh
55 1523 55 WeakestTopology
56 1523 56 kotamanegi
57 1523 57 MForest
58 1523 58 Anachor
59 1523 59 orzdevinwang
60 1523 60 hank55663
61 1523 61 starusc
62 1523 62 KrK
63 1523 63 uwi
64 1523 64 gmh77
65 1523 65 ilyakor
66 1523 66 20I6wudi
67 1523 67 kclee2172
68 1523 68 xpysss
69 1523 69 Rubikun
70 1523 70 AwakeAnay
71 1523 71 BigBag
72 1523 72 penguinman
73 1523 73 arzhantsev64
74 1523 74 enjapma
75 1523 75 Egor.Lifar
76 1523 76 leaf1415
77 1523 77 TeaPot
78 1523 77 RainAir
79 1523 79 Jatana
80 1523 80 tatyam
81 1523 81 LastDance
82 1523 82 yamunaku
83 1523 83 Monogon
84 1523 84 TadijaSebez
85 1523 85 gisp_zjz
86 1523 86 flashmt
87 1523 87 Mr_Wu
88 1523 88 haruki_K
89 1523 89 isaf
90 1523 90 dreamoon_love_AA
91 1523 91 -is-this-fft-
92 1523 92 dragonslayerintraining
93 1523 93 balbit
94 1523 94 vasilescu_mihai
95 1523 95 kshitij_sodani
96 1523 96 Isoeasy
97 1523 97 compute
98 1523 98 lucaperju
99 1523 99 dalt
100 1523 100 SSerxhs
114 1523 114 adamant
180 1523 180 BlueDiamond
227 1523 227 Ari
258 1523 259 knightL
290 1523 291 Grzmot
325 1523 326 Ahmadsm2005
508 1523 507 Agnimandur
552 1523 552 swapnil159
754 1523 755 bqq
913 1523 908 saptarshi1729
944 1523 940 smax
1029 1523 1031 rbrahul
1240 1523 1240 vkgainz
1287 1523 1287 Diana773
1291 1523 1287 the0dd1out
1341 1523 1335 SergiuS2003
1363 1523 1363 Abhi60
1425 1523 1424 kalp.s.vyas
1432 1523 1432 WAZXYY
1470 1523 1472 Nikhil_Kr
1547 1523 1551 aars
1622 1523 1625 BitmasKing
1731 1523 1738 AakashKr
1755 1523 1762 Mohaimin66
1822 1523 1828 Murtaza1112
1910 1523 1913 Hosea
2090 1523 2099 tdsb
2169 1523 2177 Abu_Musa_99
2177 1523 2187 samcpp
2185 1523 2196 abovhan
2192 1523 2201 Yanko_
2203 1523 2213 imagine7
2213 1523 2222 husain_box
2262 1523 2270 devansh05
2289 1523 2297 Crayon144
2409 1523 2422 YashShah
2422 1523 2431 7eZb_ElNa7o
2529 1523 2539 sam571128
2537 1523 2551 linbei
2544 1523 2556 hastidoshi36
2599 1523 2613 1459007298
2658 1523 2671 boogiep0p
2677 1523 2690 SpeedOfGangarians
2937 1523 2957 YazanAlattar
3111 1523 3131 DontLookBack
3164 1523 3182 AmanG247
3220 1523 3242 tokusakurai
3293 1523 3311 NEFU_Smith
3408 1523 3432 Beast_Within
3449 1523 3471 Ikwinder.ka.ur
3550 1523 3577 343_guilty_spark
3872 1523 3890 chronon
3981 1523 4010 MrArpit
3988 1523 4010 sgprsp
4008 1523 4040 Prostoegor239
4083 1523 4111 petertromso
4308 1523 4337 Harshit4u
4334 1523 4368 ojha_abhi
4544 1523 4573 shubham.gupta8416
4545 1523 4573 brahm
4781 1523 4820 aarya10
4803 1523 4840 coderfool
4833 1523 4875 SooN_
4873 1523 4914 AllINeed
4887 1523 4923 bekodeg
4937 1523 4976 Ceudan
5121 1523 5168 nish_ads
5135 1523 5178 shauryasinha020
5328 1523 5375 shreas
5385 1523 5442 AIM-9L
5387 1523 5442 dhruvinpatel1831
5410 1523 5466 hkmihir
5501 1523 5551 MindlessGoober
5600 1523 5649 Discardim
5630 1523 5691 coderrohan14
5662 1523 5723 VioletVal
5665 1523 5723 Sparkk
5723 1523 5782 go_ch
5760 1523 5803 tanjum
5875 1523 5944 iyangye
5938 1523 6005 adityateltia22
5947 1523 6020 abhishek2061a
5951 1523 6020 E404_Not_Found
5955 1523 6020 Blaze7
6034 1523 6112 Sunlet_orz
6111 1523 6187 Asif732
6156 1523 6225 Rajat02
6163 1523 6244 vishwas_26
6189 1523 6269 Palak_2109
6308 1523 6394 ayush_agrawal5
6340 1523 6422 learner101
6477 1523 6564 jainanshika193
6568 1523 6649 cj2021
6573 1523 6665 knuck_les
6581 1523 6665 pandey_2021
6602 1523 6691 harshant
6697 1523 6786 aman1606
6729 1523 6820 MayurK
6849 1523 6949 Prateek_Saini
7066 1523 7130 BitWiseOperator
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Hi ! How can i receive my t-shirt?

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

    Just my personal opinion. In general and not specially related to this contest. But, I think "You would accept the T-shirt if given" option just below Confirm Participation of contest.

    I'm sure many of Top people (say tourist for eg) would not want t-shirt. It would be waste for him and it could be really motivating and worthy for someone below him. I meant at least one person would be very happy if tourist didn't receive t-shirt.

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

    ohhhhhhhh~

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

    Sorry, I'd like to ask. I'm on the list, but there's no message informing me of my T-shirt.

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

    hii..! I haven't received my t-shirt yet. Could I get any update about this..

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

      Hello! T-shirts haven't been shipped yet, but are ready to go and should reach their owners shortly.

      Unfortunately, this is not as fast a process as we would like. We had to wait for all the participants to send the size of their T-shirts and only then start making them.

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

    I haven't received my t-shirts till now!

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

    Hi! I haven't received my t-shirt til now. Almost a year has passed. Could I get any update about it?

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

      Hi! Please contact Una_Shem via codeforces private messages. We sent all the T-shirts to the codeforces side, according to the latest information I have, the T-shirts for the first two rounds have already been sent.

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

When you send a mail that is you received tshirt Or not????