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

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

Привет, Codeforces!

13 ноября 2015 года в 18:00 MSK состоится первый учебный раунд Educational Codeforces Round #1 для участников из первого и второго дивизионов.

Учебные раунды Codefores — это новый формат соревнований основной целью, которого является помощь в развитии у участников базовых (и не только) навыков и знаний, которые необходимы при решении олимпиадных задач по программированию. В учебных раундах вы встретите не только старые добрые идеи и алгоритмы, которые многие знают, но также и некоторые расширенные темы, которые неизвестны многим участникам, в том числе и из первого дивизиона. Сложность задач будет сравнима с обычными раундами для участников из второго дивизиона, хотя многое может пригодиться и участникам из первого дивизиона. На мой взгляд первый раунд получился несколько проще того на что мы ориентировались.

Учебные раунды будут нерейтинговыми (мы продолжаем обсуждать этот вопрос). Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест. Подробнее об учебных раундах написано здесь.

Подготовкой учебных раундов занимаюсь я, Эдвард Давтян из команды Saratov SU Daemons. Идеи задач были придуманы совместно с MikeMirzayanov. Спасибо моему сокоманднику danilka.pro за тестирование и вычитывание условий и MikeMirzayanov за системы Codeforces, Polygon и идею учебных раундов.

На сегодняшнем раунде вам будет предложено пять задач. Надеюсь они вам понравятся. Если же они вам покажутся простыми приходите на второй учебный раунд там будет посложнее.

Good luck and have fun!

UPD: Первая часть раунда закончилась. Напоминаю, что результаты не являются окончательными и вы можете взламывать любые решения в течении суток.

UPD2: Пожалуйста не используйте недетерменированные генераторы. Например не стоит писать в языке С++ srand(time(NULL)) и потом использовать функцию rand(). Ваш генератор должен всегда генерировать один и тот же тест.

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

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

HAHA Edvard is wrote blog,but his blog till +1:)

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

Added problem F to the problemset. Now the contest will be interesting for nearly all Div 1 participants too. Let's have fun!

====

Добавил в контест задачу F — теперь даже Div 1 участникам будет интересно. Готовы?

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

After that you will have one day to hack any solution you want.

Can we also hack during the contest after locking a problem?

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

Please don't delay it today. I have a tight schedule today. Please!

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

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

How to solve E with DP?

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

There is a typo ... are (and would) be ... it should be ... are (and would be) ...

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

Damn, I wish this contest was a rated one :3

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

Again

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

what is unexpected verdict

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

Successful hacking attempt!

Now try to hack 14233270! ch_egor got it! Try 14242942. alexey.shchepin got it. Those were interesting puzzles — would make an okay problem I guess.

I guess the real impossible one would be the first one with a bigger input. Less brute force would work probably. Any other ideas?

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

    Sorry, but I don't understand what are you doing. Can you explain it?

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

      I originally thought there would be hacking during the round, and knew I wanted to try hacking a in-contest solution afterwards. The reasonable solution would be to submit in the last second, but I had class and could only get only at small times.

      I wanted to submit something that was hackable, but no one else would really be able to hack. The way I did this was by hashing the input, and if the hash is equal to a certain predefined value, the solution fails. For example this solution fails on "thisisahacktest".

      It didn't end up mattering since there was no contest hacking, but it was fun.

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

    you hacked your own solution :p that doesnt make any sense :/

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

    Easy. I made it with binary search.

    13
    1
    19
    31
    19
    19
    92
    74
    69
    32
    32
    91
    42
    73
    
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      I noticed. Nice job! Just random tries until it worked? (fix all but last couple)

      Try this one: 14242942. Hopefully more constrained. :)

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

        You know, that your MOD is 1016 + 60, not 1016 + 61?

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

          Oh what. I saw before on CF that it worked to do it that way. I guess not above 1e9. Okay that's a useful find. x.x

          Anyway probably doesn't make it much easier here.

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

            It's not allowed to hack not the latest submission for the problem. Anyway, here is your hack.

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

              Nice job! That's like the same as mine.

              Maybe you just make them all the same and express the difference in base 3 I guess.

              Okay that was fun; I'm done now :P

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

does unsuccessful hack reduce point????

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

i am getting unexpected verdict over and over again

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

I wonder why it takes the first accepted submission's time as penalty when you have more than one accepted submissions :O

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

А можно увидеть кто сколько взломов сделал?

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
  1. Две одинаковых посылки: 14239039 и 14238862

  2. При попытке взлома этих посылок обнаружил для себя интересную вещь. Тест http://ideone.com/7jFiGf в "запуске" работает 2427 мс, а при попытке взломать 858 мс. В связи с чем возникает вопрос: как узнать, сколько будет работать код при системном тестировании?

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

    Вероятно, ты запустил не с тем компилятором, нужно выбрать MS C++ в запуске.

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



The checker is evil. Check out the smileys.

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

Why is the source limit only 256 KB? I wanted to test a case for problem D, where n=1000,m=1000, and k=1. But, when I input my 1000*1000 grid, the file becomes 956 KB. Anything I can do to fit the memory?

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

почему-то страница со взломом не грузится, точнее код не грузится. приходиться ломать с планшета. браузер — mozilla (linux)

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

I think all that solutions for well-known problems stuff is good but the "24 hours hacking" is just a waste of time.

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

Liked this round very much.

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

E was nice w.r.t the way in which DP table had to be filled :D

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

Are we allowed to discuss the problems? I am really interested in problem C

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

    find every vectors angle with X axis and sort them and get the minimum value of distance(i , (i+1)% n)

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится -28 Проголосовать: не нравится
int main() {
      if (I get high standing)
return

our home;

return

your home;

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

What is atan2 in c++ ?!

i used atan! it was hard because of checking some conditions! is atan2 easier?

THANKS!

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

    atan returns a result in [-pi/2,+pi/2] while atan2 gives in [-pi,+pi]. You cannot determine the exact quadrant in atan. For example; given p1(1,0), p2(-1,0), atan gives 0 for both p1 and p2. You need to do extra work to see that they are not the same vectors. But atan2 gives 0 for p1 and PI for p2 which is what we are exactly looking for.

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

Why the resubmission after hack is not tested on the hack input?! I hacked the same person using the same case twice xD

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

    I think, the system doesn't test the successful hacks because all of them will be added to the main tests and will be retested after the hacking phase. xD

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

When showing the scoreboard with Div.2 only participants, It shows only users with 1700- rating only.

Looks like it is still working with old limit for div2 before colors revolution.

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

Можно показывать взломанные попытки другим цветом?(или просто добавить bold)

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

Wow, really learnt a lot from this round, especially problems E and F. Please keep more of these rounds in future. Very nice initiative :D

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

The checker for problem F seems incorrect. It is saying this case:

17 1
0 1
0 2
8 2
8 -2
0 -2
0 -1
1 -1
2 0
3 -1
4 -1
5 0
6 0
5 1
4 0
3 0
2 1
1 0
7.12 0 1 0

is 4.00, but manually drawing it out gives me 3.12. Can you double check your solution against this case?

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

    Firstly, we cross LINE with polygon not SEGMENT.

    So answer is 4 : 8-6 inside poly, 6-5 and 4-3 along side.

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

что значит "Неизвестный вердикт" при взломе?

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

    Скажи номер взлома? Или уже нормально?

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

      178630, 178629 и 178619. Сейчас на всех стоит "Игнорирован" (как я понял, из-за того, что до меня взломали)

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

        Да так и есть решение уже взломано, поэтому твои взломы проигнорированы.

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

          У меня тоже на 3 разных тестах неизвестный вердикт. Номера взломов 179603, 179610, 179614.

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

I am Curious about to ask you Guyz that " Will All the Submissions be Rejudged after adding the Hack Cases after 24 hours Hacking Phase . Let me Know .

Thanks in Advance .

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

i am got unexpected verdict when i hack problem F using n = 700, m = 100.

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

Successfully challenged myself :) :(

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

I am a Div 2 participant but why isn't my handle shown on the Div 2 Standings?

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

Problem C

Hard work, but finally I did it :|

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

    i have the same problem (WA on test 116 ). i didn't understand why!? can u help me :D submission id 30388279

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

Hello Edvard and MikeMirzayanov . I love the idea of educational rounds. I have a request. I am very bad at finding corner cases, and debugging. Can we have an educational round where the focus is on corner cases and debugging. If we have such a round in rated contest, I'll be scared to take part, and I don't like missing rounds. Besides, losing ratings because of one missed test case hurts real bad. If I practice such problems, then its not the same as solving in an actual contest. So, I request, that you prepare a round focussed on problems with lots of scope for Wrong Answer because of test cases. It will help me improve my debugging skills, because some times, I make silly errors, but give up on my solution thinking something's wrong with my approach, and I need to come out of that mindset. When I face this problem in practice, I procrastinate thinking I'll debug it later. As a result, if I code something in 15 minutes, I take 1.5hrs+ just to debug silly errors. I need to practice in contest environment and virtual contests are not the same. So, Please! Also, maybe 24hrs for hacks is maybe too much... but that's a secondary concern to me. :)

Thank you and have a wonderful day!

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

    I think it may be better if you can practice problems where there are a lot of hacks in virtual contests or mushups with your friends, which will make it much more interesting and motivational.Although I agree with your idea someway, frankly speaking, it’s hard for the organizers to meet the minority’s demond.

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

      But I can still see the test cases, and virtual contests are not as serious as real contests. This makes all the difference. I can sure, get all cases covered after 20 attempts and a bit of peeking at the test cases, but that is what I don't want to do, because it doesn't help at all during real contests. Besides, I am a lone coder, my friends not interested :(

      EDIT: If you don't make the whole contest case handling, then make the first three such, and the last two so hard, that I can't solve it :D . That way, I will be forced to try the first three.

      These are educational contests. Please help me learn the art of debugging :)

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

and now the time when hackers are more scary than system tests became ....

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

I was wrong(

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

Почему все контесты не делать такими? Кому будет неинтересно, пусть не решает. Но тут хотя бы прочитал задачу и знаешь, что с ней делать. Т.е. контест проверяет умение кодить, а не умение придумывать идеи. Так отлично! Раньше так всегда и было! Почему теперь у нас везде (в том числе и на 1/4, 1/2 финала АСМ) задачи пошли на ИДЕИ, ну ёпрст... где обычные контесты на технику, как было раньше?

Получается уже не контесты по ПРОГРАММИРОВАНИЮ, а контесты по ИДЕЕПРИДУМЫВАНИЮ. А это бред, извините уж.

P.S. Вот на своем примере говорю — 2 раза проходил в финал ACM-ICPС (2009 г. и 2011 г.), но при этом оба раза процентов 85 задач на 1/4 и на 1/2 были исключительно на технику, там не надо было ломать голову над ИДЕЯМИ, там надо было накодить и всё. Так у меня вопрос — какого фига мы уходим от программирования в идеи?

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

    Может, потому что умение думать полезнее умения программировать?

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

      Как показывает практика, без соответствующих навыков написания правильно работающего и надежного кода, у нас в ИТ компаниях нельзя разрабатывать серьезный и важный проект. И ты понимаешь в чем фишка, вот приходишь ты на работу, вокруг куча умных ребят, которые могут, как ты говоришь, "думать", открываешь код, а там идет что-то типо того:

      ... doubla a,b; ... if (a == b) { } ...

      После этого начинаешь объяснять им как сравниваются вещественные числа, что так делать нельзя и т.д. А откуда берутся навыки защищенного и правильного программирования? Из решения кучиииииищи чисто технических задач. А где набраться этого опыта, если сейчас решение задачи в первую очередь из придумывания идеи берется, а без идеи и неча садиться писать задачу?

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

        При чем здесь вообще IT-компании и работа? Я слышал, на олимпиадах надо олимпиадные задачи решать, а не крупные проекты проектировать. А если работодатель принимает на работу того, кто не умеет писать работающий и надежный код, здесь что, олимпиады виноваты?

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

        Хех, на олимпиадах вполне много техники бывает. На серьёзной олимпиаде никто же не будет делать задачу, где надо исключительно что-то придумать, а потом написать решение в две строчки. Олимпиады уже давно стали объединением умения думать, знания алгоритмов и техники написания кода. Часто встречается умение оптимизировать, люди, которые умеют писать хороший и простой код намного чаще добиваются успехов.

        Технике программирования может научится любой, а вот думать, увы, способны не все. Олимпиады ставят перед собой выявить способных и трудолюбивых людей.

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

          На серьёзной олимпиаде никто же не будет делать задачу, где надо исключительно что-то придумать, а потом написать решение в две строчки

          ))

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

            Что-то прошлогоднюю открытую олимпиаду вспомнил.

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

I'm not sure if this has been discussed yet, but since this is an educational round, the editorial will be much more detailed while teaching us the concepts right?

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

По-моему, идея открытой 24-часовой фазы взломов настолько прекрасна, что ее было бы полезно внедрить в обычные рейтинговые раунды. Разумеется, за взломы в течение этой фазы баллы не давать и не снимать, но успешные взломы добавить в "Системные тесты — 2".

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

    В некотором смысле для этого и делается. Обкатаем подход здесь.

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

For anyone wondering: Hacking E is pointless, testcase 4 enumerates all possible inputs.

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

Как изменится мое штрафное время, если мое решение взломали?

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

    Уменьшится. У вас исчезнет решенная задача, штраф теперь за нее вообще не будет учитываться.

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

Будет ли открыто дорешивание этого раунда? И если да, то будут ли решения, сдаваемые в дорешку, также тестироваться на взломах, совершённых за эти 24 часа?

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

    А разве дорешка не открыта? Перетестируем все решения по этому контесту и все успешные взломы будут добавлены в официальный набор тестов.

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

      А взломы дорешивания учитываются? Дорешивание будет перетестировано на официальном наборе тестов?

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

        Да, добавляем все успешные взломы, перетестируем все решения.

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

           прямо вообще все? Или там не так много различных?

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

Will the educational contest be rated?

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

Тесты на С реально оказались неполными, судя по тому, сколько было успешных взломов по ней. Многие, наверное, заметили, как в несколько раз упало количество верных решений по этой задаче (было 600, по моему, а осталось лишь 27), а решивших 5 задач осталось всего-то около 14 человек. Одна из проблем многих участников — надо было учесть один случай и добавить в конец массива с углами угол min_angle + 2 * PI, где min_angle обозначает минимальный угол. Контр-тест:

3
1 0
-1 0
1 -1

Этот тест и был моим взломом (я им взломал 5 человек, мог бы больше, если бы больше потратил времени :-) ). Интересно, какие взломы применяли другие участники?

UPD Кстати, я обнаружил свой взлом в списке тестов. Это тест №61 :-)

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

Umm, both mine and Jury's answers are the same. Why does the code fail at #119?

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

any idea why so many codes including mine fails on testcase 119 for C?

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

That moment when your solution is 2ms away from time-limit :D

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

Was problem C so difficult to get right because it required to use long double? Changed mine solution from double to long double and got AC: http://codeforces.com/contest/598/submission/14258763

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

Can somebody explain what is wrong with #127 testcase ?

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

    Two angles different by 2e-17 radians which is much smaller than double precision.

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

Edvard Is there an editorial for this round ?

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

Please share editorial for problem F.

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

Hi. Where I can find the tutorial for this educational round ?

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

Hi. Where I can find the tutorial for this educational round ??

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

can any one plz tell me how to solve problem E in less than O(n * m * k * k * (n+m)) time

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

    Essentially, you can remove one k factor by observing that, when you make a cut horizontally or vertically, it is always less costly to use one of the portions in full if possible, than further cutting both portions. Hence, now instead of looping over how much of the k to distribute into the two portions, you take the best of two options.