Автор MikeMirzayanov, 2 месяца назад, По-русски,

Добрый день, Codeforces!

Совсем скоро, в четверг 11 мая в 18:35 (московское время) начнется Playrix Codescapes Cup. Вас ждем рейтинговый комбинированный раунд, который открыт для всех и каждого!

Задачи для вас предложили и подготовили KAN, Al.Cash, MikeMirzayanov и fcspartakm. В раунде будут задачи как для участников из Div.2, так и для Div.1. Надеемся, вам будет интересно.

Мне всегда приятен интерес со стороны компаний к нашему сообществу. Вдвойне приятно, когда узнаешь, что российская компания находится в самом топе своей нише в мире. Вот только недавно я читал статью о Playrix, а сейчас они проводят соревнование на платформе Codeforces и ищут талантливых разработчиков на C++. В программе призы топ-5 и футболки топ-50 участникам раунда!

Слово руководителю московского офиса Playrix Алексею Трушкову.

Всем привет!

Компания Playrix и Codeforces объявляют о запуске первого Playrix Codescapes! На кону ценные призы, а лучшие 50 участников получат памятные футболки.

Призы:
- Топ 1: iPadPro 9,7 + PowerBank + футболка с логотипом
- Топ 2-5: PowerBank + футболка с логотипом
- Топ 6-50: футболка с логотипом
- (Новое!) Случайные 5 участников (не топ-50, сделали хотя бы одну попытку): футболка с логотипом

Playrix – это команда из более 500 профессионалов, которая занимает первое место среди разработчиков мобильных игр СНГ. Вы можете подумать: «Мобильные игры? Зачем им сложные алгоритмы?». Нашел, что три фишки одного цвета собрались в линию – вот и все. А вот и нет! Сделать игру, которая была бы одновременно красивой, быстрой, и укладывалась в жесткие ограничения объема памяти и быстродействия мобильных устройств – та еще задачка. Чтобы с этим справиться, нам часто приходится применять весьма сложные и нетривиальные алгоритмические решения. Мы публикуем о них статьи habrahabr: о тонкостях FSE кодирования и оптимизации игры с помощью полигональных атласов, например. А бывает, что конвертеры графических форматов, созданные именитыми фирмами, не устраивают нас ни по качеству, ни по быстродействию. И тогда нам приходится создавать свой. Это далеко не полный список сложных задач, возникающих при разработке наших игр.

Мы делаем все, чтобы наши программисты могли сосредоточиться на интересных задачах, и ничто не отвлекало их. Компания предлагает как удаленную работу, так и место в одном из 10 офисов. Вам предоставят всю необходимую технику и доступ к программам и сервисам. Также дважды в год проходит внутренняя конференция PlayrixCON, в рамках которой проходят встречи и круглые столы для программистов. Словом, в Playrix вы найдете интересные задачи, возможности для развития и комфортные условия работы.


Заинтересовались работой в Playrix?

Узнайте об актуальных вакансиях Playrix на job.playrix.ru

Поздравляем победителей!

  1. tourist
  2. LHiC
  3. subscriber
  4. W4yneb0t
  5. enot110

Опубликован разбор задач.

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

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

ого я взволнован
p.s. вот этими вот призами вы только народ дразните типа вот гроссы их возьмут а не вы азаз
p.p.s. вот этими рандомными призами вы ещё больше народ дразните, типа рандомные ноунеймы их возьмут а не вы азаз

upd. я вот не получил футболку сейчас и мне неприятно

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

    Мне кажется давать совсем случайным участникам странно. Я бы понял, если

    Случайные 5 участников (не топ-50, сделали хотя бы одну успешную попытку): футболка с логотипом

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

why all of the jobs in codeforces are for Russian-speaking contestants?

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

    I think it's a matter of the companies which hold contests on CF , not CF itself.

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

Register again. Previous registration has been cancelled.

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

How many problems?

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

Tourist winning another round ? Hope he participates.

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

Wow very awesome!!

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

Мне одному кажется, что у девушки на фото очень длинные руки?

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

    Побочный эффект от печатания на С++ с детских лет

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

tourist will complete his set of apple products.

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

Posted time: 15:35 UTC

Actual time: probably 15:45 UTC

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

Hi, everybody.

The offer to organizers from the company Playrix

Considering that the Playrix is engaged in development of games, I would advise to bring some spirit of surprise in a contest :) For example, to add 3-5 small prizes (or T-shirts) which by a randomly method will get to participants outside the first hundred, and maybe the first thousand. It would stimulate attraction to a contest of players.

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

    would be fantastic, no newbies got a tshirt before.

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

    Although I totally love the idea and also love to get a T-shirt, but I think keeping it for the first 50 is better. To encourage low-rate participants to do better and EARN the T-shirt.

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

      I don't urge to take away t-shirts at TOP-50 participants. ))) I suggest to give IN ADDITION 3-5 t-shirts for participants from the first thousand

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

    Great idea, thanks! Playrix will give 5 additional prizes to random participants not included in the top 50. I hope CF will help us with fair random algorithms )

    Best Regards, Trushkov Aleksey Playrix

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

      Thank you for understanding. P.S. Понадобятся идеи, обращайтесь, на кетайщине их хватает ))

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

It would be great if you will announce such events more than a day before. Thanks.

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

Problem prepared by MikeMirzayanov! I'm not gonna miss it.

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

I predict there will be an obscure Geometry problem.

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

T-shirt on girl is really great :D

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

I hope there won't be delay before the contest.

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

I am a Random winner.....

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

T-Shirt <3

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

Dafuq happened to the right hand of the t-shirt girl?..look at those veins :O

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

Hope it's easy to understand all the problems, And all participants will enjoy the contest. :)

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

Is her (t-shirt on girls) right hand > left hand :D ?

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

The T-Shirt Looks Nice

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

How does back of white T-shirt look?

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

а когда обьявят тех кто получил футболки рандомна ? после раунда или как ?

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

    "не топ-50, сделали хотя бы одну попытку". Значит после

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

Заметил ошибку во времени начала контеста. На странице соревнований начало контеста в 19:35 (по Москве), в анонсе начало в 18:35 и отсчет времени идет до 18:35.

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

Rating prediction,

Extensions:

Have fun & high rating:)

PS One guy wrote to me that he couldn't install extension. Does anybody else has the same problem?

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

    I have same problem :(

    "An error has occurred There was a problem adding the item to Chrome. Please refresh the page and try again."

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

      I think I got this message when I had slow internet speed

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

how many problems???

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

Футболки очень красивые!)))

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

T-shirts very well

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

Is my luck so poor?

I never get a random prize.

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

    Well considering that 4500 ppl will participate in this round 50 for them will get prizes for sure that leaves 4450 the probability that one will get a prize is 0.0011235955.

    Your luck is not poor it's just math.

    :)

    PS: if you work hard enough you won't need luck cause your probability will be 1.

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

      Actually, assuming 4500 people submit at least once, the probability that you win one of the 5 random T-Shirts is 0.003366496682134068.

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

      Still got a higher chance than finding our soulmate

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

    I wonder if the T-shirts in this contest will be distributed based on an adaption of the formula from the problem in the previous contest 807B - T-Shirt Hunt ...

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

i think that it will be a little bit tricky one and challenging too.....

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

What about scoring distribution?

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

The '#' took the perfect place in the picture.

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

Expecting a 10 minute delay. xD

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

How many problems? What's the scoring distribution?

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

waw ini sangat menyenangkan bagi saya saya suka dengan dengan artikel yang admin buat semoga sukses selalu salam dari kami obat bius cair

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

tourist registered. maybe he is going to be champion

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

Look at girl's right hand. What is that monster dude...?

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

wow.. no delays .. so unusual ..

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

hope to be in random 5 !!!

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

mikemirzayanov please give tourist a new color :O

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

is that "t-shrirt" is just layer? there also this picture with another t-shirt

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

Трудные однако задачи

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

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

how to solve D?

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

    Dp[h][w] in map

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

    Notice that for ai >= 3, you will need maximum of 11 items to increase alength from 1 to over 10**5. So you can brute over min(22, n) largest items to divide them into either Length/width. Incase the length is still less, then find how many no of 2's will satisfy Maintain a count of actual length increments done and find the minimum answer.

    Complexity: O(2**22 * 20)

    I thought this should pass. But this was very close to tle. 940ms first time for me. But after doing some bad optimizations, it passes pretest ins 499ms. (I lost around 400 points on this :|)

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

      If reverse sorted a[] is like five 6, five 5, five 4, five 3, five 2, you can brute over x '6' to width and 5-x '6' to height. And so on for the rest of the unique values in a[]. I think a binary search is required at the lowest level as you may not need all of 5-x 'smallest-digit'. And we must also consider inverted the rectangle by 90degree. The max time this will take is 2*( 2^(2*10 + 2*log11) ).

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

    if you sort in non-increasing order, you should not to skip some extension, answer is some prefix, so you can use dp[idx][pair(curW, curH)] with map 27034588

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

      It is also possible to memoize only one of the parameters (h or w). The other one may be derived from the current index of the dp if you precompute the prefix product of the sequence.

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

      what is the time complexity of this approach? how many elements in the worst case will be added to the map?

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

        In my solution , it's O(max(a,b)) — since there are sqrt(x) different x/y numbers for y belongs to integers. so sqrt(x)*sqrt(x) for the pair = O(x) = O(max(a,b)).

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

Congrats tourist , i was spectating whole round lol

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

How to solve C?

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

    Taking fountain with diamond + coin is easy. Then use two pointers\bin search for coin + coin, diamond + diamond pair.

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

      Then use two pointers\bin search for coin + coin, diamond + diamond pair.

      Could you, please, explain how to do that? It looks like a knapsack for me.

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

        When we buy fountain for x coins, we still have c — x coins. So you can sort and find max prefix that you can buy with c — x coins, and find max beauty in that prefix with prefix maximums.

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

        well,you have 2 cases:you take two of the same type(2 coins or 2 diamonds) or you take one fountain with diamonds and one with coins.

        1 diamond+1coin: you take the most beautifull fountain you can afford for each type

        2 diamonds/coins: you take fountain i,and search for another fountain j,such that their beauty is maximal for i,and their cost is small enough

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

          such that their beauty is maximal for i,and their cost is small enough

          I don't understand how to do that.

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

            you select a fountain i,and say "ok,i would like to buy this fountain and another one of the same type,but i would like to take the most beautifull one i can afford". so beauty[i]+beauty[j] is maximal,and cost[i]+cost[j]<=C(or D,depends on case)

            and res will be max of all this cases and case 1(1 diamond+1 coin)

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

              We do O(n) steps to choose fountain i. For each of i we do O(n) operations to find j'th fountain. Right?

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

                we find j in logN steps by sorting the array and binary searching after,but thats the tedious part,and its hard to explain.

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

                  ... logN steps by sorting the array and binary searching ...

                  So, we sort by beauty or by cost?

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

                  by cost

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

                  In this case, after sorting the array by cost and getting the position of the fountain with less or equal to (total coins — coins for selected fountain) coins, wouldn't one need to check for all fountains less than this found price as well? Then, will it still be logN?

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

                  yes,because it would be something like max(beauty[1],....beauty[j]),which can be precalculated with another array,where V[i]=max(beauty[1],beauty[2],....,beauty[i])

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

                  I have used the same approach but my solution is giving WA on test 4 .

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

                  Well,You did something wrong in the code than. Belive me,this approach is good,and i got accepted with it

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

              "ok,i would like to buy this fountain and another one of the same type,but i would like to take the most beautifull one i can afford"

              But can it be a situation like we can choose 2 fountains in one currency without that fountain we chose in the first time?

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

                Yes,thats why you take each fountain i from 1 to number_of_same_type,and after you do a max

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

      @Reol , I have done same thing as you are mentioning. But was getting WA for 4th testcase... can't figure out what is mistake,,,

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

        Exact same case with me. I did binary search and keep getting WA on 4th test case.

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

          @hrushikesht, binary search ???

          I thought it was simple knapsack problem... where picking up 2 fountains was compulsory :| ... Can't say for sure...

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

            well its pretty hard to do knapsack on this,considering you would end up with O(N*C*D) plus,you can choose a maximum of 2 elements,so that would be a costant of 2

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

              @georgerapeanu

              What I mean by knapsack is that.

              firts of all split fountains which can be bought by only diamonds , and only coins,,, then given list of fountains which can be bougth by only coins,,, use knapsack for them ,,, and DP table size will be ,,,

              (number_of_coin_fountains * 2) same goes for number_of_diamond_mountains*2 size for other process... Since costs of fountains are within the 10^5 ,,, that was most preferable approach(in my opinion),,,

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

                wouldnt it be O(C*number_of_coin*2)?

                because you should take care of the cost,and you are at index i,and you have selected k fountains so far

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

                  @georgerapeanu,,,

                  yeah , my bad,,,

                  it will be maximum 100000*2 ,,, and we can fill up the DP table in linear time...

                  but now, you must be getting an idea,,, which KNAPSACK I was talking about

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

    I used segment tree range maximum query to find the best pair

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

      Can you please elaborate more on the approach?

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

        There are 3 cases: 1. Get 1 fountain with diamonds and 1 with coins, 2. Get both with coins, 3. Get both with diamonds.

        Case 1 is easy: buy the most beautiful ones that you can afford.

        For cases 2 and 3 you can use 2 separate segment trees: st[0 or 1][i] = most beautiful fountain that costs i coins (0) or diamonds (1). Iterate through all fountains. If you take fountain i, you have c — cost[i] coins left. Let this amount be x. Use range max query on first segment tree to find the most beautiful fountain whose cost is in the range 1...x and take the sum of current one's beauty and this one's. Then, store current fountain in the segtree. The same applies for diamonds, just use another segtree.

        From each case you get a value, answer is the maximum of these. Be aware of the situations when you can't buy two fountains.

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

    Observe that you can either pay with coins only, diamonds only or both.

    Sort by Coins or Diamonds whatever the case and have a dp array such that dp[i] is the fountain with biggest beauty in the range [0..i].

    We can use binary search for any of the cases.

    In the last case, iterate through the coin array and use binary search on the corresponding Diamond array.

    I think all three cases should produce a best value.

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

      I was thinking about dp[i], but it can be that for some i1 and i2 that i1 + i2 <= d/c dp[i1] and dp[i2] will be the beauty of the same fountain, or did i misunderstood something?

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

        noeInadal states what I'm trying to say.

        So once you understand that there are three cases, you basically use binary search and sorting to achieve your aim.

        It is possible to code without duplicate creation.

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

    There are three ways of purchasing two fountains:

    • one of each type;
    • two of the first type;
    • two of the second type.

    In the first case, just consider, for every type, the maximum beauty among the fountains whose price is lower or equal to the number of coins of this type. Then, the maximum beauty is the sum of these two.

    Then, sort fountains separately according to their price, and precompute for every fountain the maximum beauty with a fountain whose price is lower of equal than this fountain. Then move from most expensive fountain to cheapest one and update the answer if you can.

    Complexity in O(nlog(n)).

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

    Unfortunately for me because I attempted and solved(pretest) C, I could not come back and solve my B on time. I hope my speed increases soon. :(

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

    I did not solve it but those who find segtree easier than bin search can try this for the cases coin+coin and diamond+diamond. For every cost x, maintain two values, the two maximum beauty available and call them b1 and b2. If there is only one, set b1 to -inf and if there is none, set b1 and b2 both to -inf. Now build a segtree over the costs and every leaf node stores the maximum beauty possible with the given cost. If you select a fountain with cost x, replace in segtree with the second maximum beauty and query the segtree. Repeat this for every possible cost.

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

    No binary search needed. Since the maximum possible price is not that big, it can be solved as follows.

    Let's compute fc[i] := (id1, id2) such that id1 is the index of the most beautiful fountain with the cost at most i coins, and id2 is the index of the second most beautiful fountains with the cost at most i coins.

    Similarly, fd[i] := (id1, id2) such that id1 is the index of the most beautiful fountain with the cost at most i diamonds, and id2 is the index of the second most beautiful fountains with the cost at most i diamonds.

    These two tables can be easily computed in O(n) starting from i = 1 (or O(n*log(n)) if someone is lazy) if you have fountains grouped initially by an exact price.

    After that, the only thing to do is to combine the results considering all the cases: you pay only with coins for both, you pay only with diamonds for both, you pay with coins for one and with diamonds for the other.

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

I think it's awesome how computational geometry problems can be so conceptually simple and yet so hard to solve in contest time (ok probably because it was the last question too).

What's the solution for E? (I get the strange feeling that some sort of clever gradual refinement might somehow pass, since it is almost a linear programming question.)

Edit: seems like modified mincost maxflow might work...

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

Great contest I liked the problems very much...C was a little bit tedious tho.

How to solve D ?

:)

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

    Since 2^18 > 1e5, you only need something like 60 items with best cost.

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

    What is 4th testcase bro ? (for C question)

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

    Sort the array a, and then try all possibilities by having last k elements in use? I used multiset array to store variantions of h and w, for some k and then go thru all of them in (k-1) array and try to multiply. As the multiplicator is at least 2 the multisets size might not explode :D

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

    C was easy to code using BIT. Not at all tedious. code

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

      ankububble can you please explain your concept behind your code .... thanks

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

        Sure.
        Let dp(i) denote the max beauty when you have to pick 2 fountains from first i fountains and you are selecting the ith fountain. When I am calculating dp(i) , I need to iterate over all j<i, and select the fountain that passes the budget and has the max beauty. This is O(n^2). BITs are used to speed this up.
        I used BIT to compute prefix max. For fountain of price p and beauty b, I set bit[p] = b. To compute fountain with max beauty within price range <= K, we can take max from bit for prefix of length K.
        Hope this helps. Have a good day!

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

    solved

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

I told you we have much confidence on tourist winning the round. Now see he has won it by huge huge margin. On your face who gave me downvotes on my previous comments.

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

There are random t-shirts again, so we will use a similar algorithm to the one used several months ago. We have a pseudo-random generator based on testlib.h. The seed will be the winner score in the Tinkoff Cnallenge Final Round on Saturday. The printed integers are the winning places, the ties are broken by the time of last AC.

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

I need help in Problem D.

I need to solve this Subproblem.

Given an array A = [a1, a2, a3, ..., an] and an Integer X.

Get a Sub Sequence B = [b1, b2, b3, ..., bm] from array A such that b1 * b2 * b3 * ... * bm is >= X and as minimum as possible.

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

    Hint: Note that bi >= 2. So you need at most 17 elements to make their product > 10^5.
    Hint2: Suppose you are kinking K numbers. You will sort them in descending order and pick the first K numbers.

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

Submitting problem A and passed pretest: YES! I did it! I'm the f**king genius! Let's check the dashboard. WTF?! tourist solved problem E already?

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

    We know he is a legend :) But he solved E after 41 minutes while you solved A after 22 minutes.

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

      22 minutes: Submitted. 22 minutes ~ about 26 minutes: In queue. I checked dashboard: he got '-1' on problem E So, you're right. It should be 'He has submitted problem E already' exactly.

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

Due to technical reasons the system testing and the rating update will probably be delayed a bit.

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

Hi:

I understand that the contest is finished, but is there a way to still submit my code, just to test for myself..?

Cheers

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

"В" было реально проще, чем "А".

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

The contest is over but I am not able to see the submissions of other users. Why is it so?

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

For C, I separated coins and diamonds. Applied knapsack on both of them individually. Then I just checked the maximum 2 values that can be generated taking care of if 2 fountains cannot be generated. Is this method wrong?

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

    TLE and MLE Unless you did one hell of an optimization.

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

    there are 3 choices :

    1) 1 cois + 1 diamond

    2) 2 coins

    3) 2 diamonds

    the first is easy , the second and the third are the same

    you have a vector of pair for each type { price , beauty } sorted in ascending order

    try the first fountain to be v[i] with price p1 and you have coins-p1 left

    the second one will be from range [ 0 , min(i-1, upper_bound(coins-p1)-1 ) ]

    now take the one with max beauty ( precalculation )

    something like that ...

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

In some last minutes, I used brute force way with O(n^2) for problem C and passed the pretest. So the pretest is weak and it is the chance for some cheater who passing it by this way, then open other solution in the same room to find the "real" solution.

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

    Well, it doesn't make a difference, does it? He/She cannot resubmit his/her solution. And it was more or less obvious from the constraints that an O(n^2) solution would time out, so he didn't necessarily have to look at an optimal solution to figure that out.

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

      Someone can have fake account and see others' solution with locking in fake account, then write in his real account.

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

Why was the memory limit so tight in C? I got memory limit exceeded with only 2 segment trees and total memory of around 12 * 105. My contest got ruined because of this :(

By the way, how much memory can I declare when 256 MB is the limit?

Edit: Nevermind, memory limit wasn't tight. I'm just stupid.

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

    I have the same problem )=

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

    No there will be a different issue. 12*10^5 easily fits 256 MB.

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

    I got same error, the problem was in my build function, say if count of 'C' is zero, u shld take care of this in ur build(1,1,count(C)) in the segment tree for C(Coins)

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

    Your contest got ruined because you are used to use segment trees everywhere, even if there is much simpler solution.

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

Hats off for strong pretests. Update: I meant in D mainly, and I didn't see many hacks in general.

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

Someone know why MLE here http://codeforces.com/contest/799/submission/27036789 I only use 10^6 integers or where am I wrong?

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

    You can't see others' submissions before systest. Can you pastebin it?

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

      Sure, it's a little ugly

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

Were there pretest on D that needed rotation before answering? Its sad that after trying optimization to fit into tle , i forgot this part and now i will get WA...

»
2 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
Why my solution Memory limit #4

I don't undertstand
About my memory MX=1e5; two (int,int)[4 * MX] = 2*4*4*4*MX = 128*MX two int MX = 2*MX all 128 * MX + 2 * MX = 130 * MX I think int array[1e6] = 4 Megabyte I tnink **** **** **** ******My memory about 50 Megabyte + (void with other) <= 256 Megabyte**

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

How to solve A? xd

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

    We can iterate through time and compute the number of cakes that we can do in that time.

    for (int time = 1; true; time++)
    {
      int cnt_cakes1 = ...; // Number of cakes WITHOUT second oven.
      if (cnt_cakes1 >= needed_cakes)
      {
        cout << "NO";
        return 0;
      }
       
      int cnt_cakes2 = cnt_cakes1 + ...; // Number of cakes WITH second oven.
      if (cnt_cakes2 >= needed_cakes)
      {
        cout << "YES";
        return 0;
      }
    }
    
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved it like this: First, I calculated time needed for oven 1 to bake all the cakes. t1 = ceil(n/k)*t

    Then I do t1 — t which is the time the last batch of cakes were put in the oven. If it is less than equal to d, there is no need to build another oven.

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

    if (d // t) * k + k >= n then answer is NO, else answer is YES

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

    if ( ceil ( n * 1. / k ) * t — t <= d ) cout << "NO" ; else cout << "YES";

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

Can someone tell me why my approach for C is wrong?

First, I try to match 1 fountain of C with 1 fountain of D. In that case it will be the most beautiful of each one that I can afford. The other case is to get 2 fountains of C or 2 fountains of D.

So I sort them by cost, and build a segment tree of maximum beauty within range. Then, for each fountain, I take its cost and binary search the most expensive fountain that I can afford (which will give me an index j in the array the segment tree was based on). Then I just query the segment tree for the range (i+1, j). Then take the maximum of every iteration on both types.

Code: https://ghostbin.com/paste/ogevq

Wrong Answer on pretest 4.

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

    What if the fountain of maximum beauty lays in the range from (0,i-1) ? It doesn't look like you account for that

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

      well, then it would have been found on an early iteration. I always take the fountain i with the fountain returned by the query. If the best fountain to pair with i (let's call it j) is before i itself, then in the iteration of j the query would have returned i.

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

Why aren't others solutions visible?

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

Just wish I am lucky enough to get a T-shirt, please :)

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

Any help in B please?

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

I solved B using set in O(mlogn) but my solution didn't care about number of colours, though it was limited to 3. So now I wonder whether it can be solved in linear time or not?

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

Great contest!

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

Why WA11 on E? Can somebody help me?

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

    Is the general solution to fit some 'both like' decorations + minheap on the rest of the decorations?

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

Why TLE on B 27019672. As far as i know the erase function returns number of elements deleted.

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

My solution to problem C got WA because I was comparing a price with a beauty by mistake, the idea was to compare two beauties. After the contest I fixed that and I got AC. How could the first solution have passed the damn pretests!?

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

WA on 27 in D. ARGHHHHH!

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

    Probably failure to consider rectangle rotation? I also WAed 27 of D by forgetting to swap variables: "if ((curr >= a && area/curr >= b) || (curr >= a && area/curr >= b))"

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

The Magic returns again Random_shuffle (: http://codeforces.com/contest/799/submission/27038984

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

    Sometimes I think maybe try random but never have enough confidence to really try it

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

    I believe this shit is the reason of KAN's comment about that the results are not final :D

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

So weak pretest on C. Jesus, there was only 10 tests and all of them were soooo simple. Nice trap)

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

Problem B-: link-: http://codeforces.com/contest/799/submission/27030194

Can any one please have a look at my code it gives Runtime error on pretest 9 ??. i can't figure it out why..??

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

    Your code assumes that front and back sides of a T-shirt are TWO DISTINCT T-shirts.

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

      No,not really that's why why i have deleted the price of current buyer from all color consist of set of price (ie v[i],i=1,2,3) here v[i] is the set of color i.

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

    I_hate_my_color please have a look at my code ?? got frustrated ..why got runtime error ??

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

    You should store (*it) in a variable then delete it from various sets. Consider x=1 and v[1].size()=1. You first delete it then use (*it) for i=2, and i=3 which is invalid and cause run-time error.

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

      Thanks it works...But both way of doing it is same but OH MY bad luck solution is correct but due to this error it got runtime on 9. Bad day..

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

You know you are legendary when you fail E on system tests but you are still the first

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

Кто-нибудь может объяснить нормальное решение D? У меня такое чувство, что я просто загнал лажу, жадно проверяя ответ от 40 до 0

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

    Наблюдение : достаточно первых 40 элементов в порядке убывания, т.к каждая сторона расширяется не более 17 раз. Более того, так как порядок использования нам не важен, разумно брать максимальные доступные значения.

    Тогда пишем dp[turns][width] -> max height

    Пересчеты примерно такие: можно либо расширить width в a[turns] раз, либо расширить max height в a[turns] раз. Если прямоугольник (width, dp[turns][width] * a[turns]) или прямоугольник (width * a[turns], dp[turns][width]) дает нам ответ, то ответ равен turns + 1.

    В противном случае релаксируем значения в turns + 1 :) Немного сумбурно, надеюсь, кодом будет понятнее. http://codeforces.com/contest/799/submission/27031985

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

27040141 should not this submission get wrong ans? giving -1 for this case

100000 100000 1 1 4 99999 99999 99999 99999

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

27040141

this submission should get wrong ans

printing -1 for this case

100000 100000 1 1 4

99999 99999 99999 99999

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

В D кроме дп заходил пребор по i (количество использованнных чисел (<= 34), к тому же понятно что надо использоватьтолько максимальные i чисел), если перебирать сколько копий какого-либо из максимальных чисел мы используем для увеличения h, и, соответственно остальное для увеличения w.

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

    Круче! Заходит перебор первых 19 чисел для одного из чисел и заполнение второго жадным образом. В минимальном тесте, который мог бы это сломать будет 19 троек и 2 двойки, а 3^10 * 2 > 10^5, поэтому всего можем поставить 9 троек и двойку так, чтобы взять всё. Что приводит к 18 тройкам и 2 двойкам в тесте и уже перебирается решением.

    Надо только поподставлять первым числом и w, и h. Типа все 4 возможных комбинации инпута чекнуть.

    // К сожалению, на контесте до такой идеи мне чутка не хватило) В дорешку уже закинул. http://codeforces.com/contest/799/submission/27039226

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

Кто-нибудь не подскажет когда разбор подъедет?

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

c 27040159

what is the problem with this?

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

The results (and rating change) are not final yet, the final results will be within several hours.

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

what is problem of this code

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

what is problem of this code

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

    First thing to do when you get RTE: Check the arrays bounds!!

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

      Thanks it works

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

      Hey I was also getting runtime error on Case 9 this but as soon as I did del = *it and then used this del to erase then it got passed this but I am unable to understand why this is so ??

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

Why they made pretest in D so that you don't need to swap(a, b) in no way ant it still passes pretests, when after real tests it fails :/ My solution

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

D was such an amazing problem indeed

I guess my solution is a bit odd but it takes 78ms to finish

My idea was to deal with the easiest two cases separately, that's when the answer is 0 or 1

For the general case:

We are told that the smallest ai value is not less than 2, which means that in worst case we need 17 elements for each side a = b = 100, 000, w = h = 1, n = 100, 000, that's 34 elements at most, cool isn't it

Well that number 34 makes it seems like it's dynamic programming with bitmasking, hmmm maybe but I couldn't utilize this fact much

Anyway let's take a look at the worst case, we have 34 elements and we need to choose a subset of these numbers, multiply them together with one of sides, then multiply the complements of said subset with the other side and check if we can enclose an a * b inside

But 34 is a big number, I would gladly do something like that if it was something like 17, but hey, what if split it into 2 halves, each of which is at most 17 elements, that's 217 subsets -- we can sort the second one in descending order and then loop over each subset in the first half, for each one I want to find the best match in the second sorted half, we may add with each subset the value of its compliment, do something like partial sums over them such that subcomplement[i] = Maxi: subcomplement[0..i]

Now we can do for each subset in first half a binary search over the range of subsets, if we can satisfy:

w * subleft[i] * subright[l...r] >  = a and check if h * subleftcomplement[i] * subrightcomplement[r] >  = b or when w,h are swapped and a,b are swapped i.e. four cases then there is a solution using 34 elements

We can try to reduce the count to the half and repeat the process around log2(34) times

Basically we are doing binary search over answer (count) and using meet in the middle technique to check it quickly

Not so sure about the big-O though, may be O(2m / 2 * log2(2m / 2) * log2(m)) and m <  = 34

Anyway here is the link

27042867(Submission link)

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

    I believe the expected solution was along these lines. I was trying to do something similar during the contest time. However, I am still not sure how many people got a simple bfs like solution to pass this constrains. It seems like they are actually exploring a tree with a branching factor of 2 (either multiply the current number to w o h) and the shallowest solution can be upto depth 34. Obviously many branches can be easily pruned but why was this optimization so significant?

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

      For a fixed set of extensions, let the final area of the field after applying all of them be A. Then if A/(a*b) > 100000, there must be a solution (Consider moving field extensions from the width to the height 1 at a time).

      So A < 1e15. Notice that all states we have are divisors of A, and that no number below 1e15 has too many factors (cannot remember how many, but it's way way less than 2^30). Thus pruning is very effective.

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

        Wont there be multiple states corresponding to one divisor of A.Could ou please elaborate on the proof.

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

          This is similar to the knapsack problem https://en.wikipedia.org/wiki/Knapsack_problem. Here the value and weights are the same. Consider the following solution:

          Number the items 1 to n. Consider the set S={0}. For 1 to n, do:

          Update S' to be S union {S*w_i}. That is, we add to the set S the new possible values that we could form with items up to n. To do this, we just need to add at most |S| values, i.e. the size of the already existing set. The pruning of repeated values keep the size of |S| small.

          If |S| is bounded by 100000, then we require at most 100000 operations per iteration of the for loop, which is still a lot less than 2^30, and hence runs in time.

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

    I have done the same. Forgot to swap h, w and perform it again. I used set for those 34 elements. When for a particular mask, I select some of those 34 elements, I remove them from mask and give it to h, then to make w >= b, I greedily reverse iterate on the set till I make w>=b. code

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

    I also thought subsets are 2 power 34 . So dynamic programming might time out. But if u observe states are not distinct unless all a[i] are distinct . The states will keep repeating(and 17 is possible only if all a[i] are two). So as 10! is less than 10^5 . Total states will be around 2^20 or so (this is just intuitive). So this is the reason why dp works

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

    please explain the part where we take complements of the sets .Suppose I choose a particular subset and then do binary search in the other set for the height.Then how do I do for the width.DO we have to try all complements of the chosen subset or one full complement of the chosen subset?

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

The contest dissapeared!

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

Problem C, any case just as test 4 but simpler ?

UPD: AC .. sorry for inconvenience.

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

How to solve problem E? Thanks.

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

    Denote set of decorations liked by both to be A, set liked by Arkady only to be B, set liked by Masha only to be C, and set liked by neither to be D. Sort these sets in ascending order by cost and keep their prefix sums.

    We fix the number of decorations we pick from set A to be x. Then we need at least (k-x) items from set B and set C, and (m-x-2*(k-x)) (call this number KK) remaining items from any set. The (k-x) items from set B and C we can just optimally pick the cheapest items. For the rest, we need to pick the cheapest KK items from any of the sets B,C,and D. Call this final optimal set of KK items to be S. We can binary search for the maximum value M in S (look for the minimum M such that the number of items <= to M in sets B,C,D sum up to more than KK). To do this for each set B,C,D we binary search again for number of items less than M and sum them up. If the minimum such M gives us L items that are <= M, then we subtract (L-K)*M from the prefix sum since all the over-counted items will have cost M.

    Loop through all possible values of x (0 to |A|) and get optimum answer.

    • »
      »
      »