Автор 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 случайных футболок, по причине того, что поиск читеров не завершен.

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

»
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?

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

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

    Yes, that's the plan! :) I hope we will delight you with our tasks

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

nvm, it changed

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

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

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

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

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

the prizes are really good

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

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

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

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

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

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

Time for SpeedForces.

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

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

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

I feel a little envious about the top three.

QQ图片20210512215006.gif

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

PS5 wow so good

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

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

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

to all testers whose list will appear very soon

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

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

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

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

third place be like

<3 place>

^

<3

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

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

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

how many bugaboos?

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

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

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

tourist can you don't give your PS5 to me?

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

Good Luck everyone for this round!!!

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

We have four purple questionsetters!

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

Excited!!

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

8 problems! Can you please increase the contest duration a little bit more?

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

Excited!!

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

slaves

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

Where is Anton when you need him?

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

Amazing prizes and I hope it's amazing contest Thanks :))

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

it is rated or not?

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

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

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

is this rated contest?

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

I think the contest's description should say here's a new ps5 to tourist and the rest of the things for the top 500

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

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

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

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

Is it rated???

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

:)

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

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

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

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

is it impossible to improve in codeforces without watching anime ?

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

hoping this will not be a div 1.5 round !

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

Score distribution looks sus

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

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

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

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

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

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

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

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

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

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

deltix round == bad round

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

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

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

What's wrong with B??

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

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

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

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

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

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

speedforces

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

D is too tough to even try

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

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

statement of C is shit

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

    I agree, I've given many rounds and i don't say they are bad just because I performed poorly but today's C problem statement was totally shit ;( they could've explained it in a better way.

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

Was it really prepared keeping in mind Div2 also?

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

Please, help understand problem E

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

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

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

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

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

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

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

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

how to solve the problem D ?

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

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

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

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

Thanks for the interesting problems!

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

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

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

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

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

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

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

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

My strategy after struggling for hours with C..

Just relax in the forthcoming Deltix Rounds. Peace.

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

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

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

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

    Wow, how do you do it without randomisation?

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

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

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

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

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

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

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

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

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

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

        Can you explain your approach?

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

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

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

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

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

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

        Hey Wielomian, I tried running your submission — https://codeforces.com/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.com/contest/1523/submission/118490042

        • »
          »
          »
          »
          »
          9 дней назад, # ^ |
          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.

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

    You motherfucker , go suck radewoosh dick and eat shit. You don't like cOmBiNeD round then why participated asshole ?

    Spoiler

    Radewoosh and you polish shit don't trigger me!

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

    How to solve D with randomisation (

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

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

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

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

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

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

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

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

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

why no bugaboo :(

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

Fine, finally a reading comprehension round.

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

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

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

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

Lol A was harder for me than B, For A i took 2 attempts and 1 hr and B only 30 mins in 1 attempt, didn't have enough time to solve C.anyways it was a good round xD...

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

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

what is wrong in my submission of C link

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

OOf just lacked a tiny bit of time for D lul

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

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

    OH NO

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

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

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

    +1. Frequency of codeforces contest has decreased compared to month back.

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

    They will probably put an educational round in between. It happened earlier that I thought the next contest is after 2 weeks and didnt check codeforces for 2 weeks. After 2 weeks, I saw an educatioal round was announced 5 days before happening 1 week later.

    My point is keep checking the contest schedule each day. Something might get added.

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

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

why so bad...

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

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

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

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

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

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

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

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

      Will the round still be rated?

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

        Yes.

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

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

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

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

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

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

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

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

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

      This is different. Using base 10 is an underlying assumption in all problems. The list being lexicographically sorted, however, isn't so clear. Also, the statement was editted 40 minutes into the contest to correct the mistake.

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

I take my words back.

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

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

Can anyone explain how to solve E?

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

Can someone please point out my mistake in today's C?

https://codeforces.com/contest/1523/problem/C

My own testcases passed.. and I feel pretty sure I have done right. Please help.

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

The problem statement of C is unreadable.

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

[. .

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

    omg, that must feel bad ;)

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

    omg!

    rating predictor is showing -213 OMFG

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

    So basically you participated but decided not to submit because didn't want to ruin you rating and as a result you did exactly that

    What irony

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

      I didn't even wanted to participate ( the biggest reason being I was busy in upsolving today's ABC's E) I started contest after a good amount of time , But that happened . leave it , I think nothing could be done .

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

I see a lot of specialists there, including me, failing sys tests in A lol guys.

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

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

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

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

    Not your fault, this round is shit.

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

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

      Imagine writing all problems in the same file, lol.

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

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

Weak pretests on D!

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

Asking for hack: my submission for D

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

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

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

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

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

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

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

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

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

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

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

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

    Yo bro me too, python is crap

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

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

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

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

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

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

      My implementation is crap, but it should have the same complexity as described in editorial. I looked at your impl. and it seems more effective than the editorial solution

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

What was the point on the weak pretests for A?

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

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

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

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

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

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

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

      Yes! Me too. This statement completely threw me off guard. I wish they had not kept such ambiguous statements and included more samples in the problem statement.

»
2 недели назад, # |
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. :(

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

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

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

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