Из-за пересечений с другими соревнованиями Codeforces Round #416 (Div. 2) перенесен на 27.05.2017 12:35 (московское время). ×

Автор BledDest, 12 дней назад, По-русски,

Привет, Codeforces!

15 мая в 18:05 MSK состоится Educational Codeforces Round 21.

Продолжается серия образовательных раундов в рамках инициативы университета Harbour.Space! Подробности о сотрудничестве Harbour.Space и Codeforces можно прочитать в посте.

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

Вам будет предложено 7 задач на 2 часа 30 минут. Мы надеемся, что каждый найдёт для себя что-то интересное в этом раунде.

Раунд вместе со мной готовили Михаил PikMike Пикляев и Михаил MikeMirzayanov Мирзаянов.

Анонс раунда — это не единственная новость к этому часу. Передаю слово Игорю Максимову, представителю Harbour.Space.

Мы рады анонсировать второй Hello Barcelona ACM-ICPC Bootcamp, который пройдет с 27-го сентября по 5-е октября 2017 г. в Барселоне. Мероприятие организовано совместно с Центром развития ИТ-образования МФТИ, хорошо известным по сборам в Москве и первым сборам Hello Barcelona ACM-ICPC Bootcamp.

Основная цель Hello Barcelona ACM-ICPC Bootcamp — помочь командам подготовиться к новому сезону ACM-ICPC. Учебная программа рассчитана как на начинающие команды, так и на профессионалов. Сборы будут проведены по двум дивизионам:

  • Дивизион A: для команд, претендендующих на медали финала чемпионата мира ACM-ICPC;
  • Дивизион B: для команд, которые готовятся к участию в полуфиналах ACM-ICPC. В этом дивизионе участников ждет интересная объемная учебная программа.

Примите участие во втором Hello Barcelona ACM-ICPC Bootcamp!

Подробнее →

Желаем удачи в Раунде!

UPD: Разбор задач.

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

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

is it rated?

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

Problem E is something interesting...

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

    Maybe just servers are too busy or simply too slow... Of course I am kidding!

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

    You are downvoting me badly implying the task is actually EASY. But see, even DIV1 coder did not solved it by his/her own, but just COPYPASTED solution http://codeforces.com/contest/808/submission/27140269

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

      Honestly I am surprised more people didn't do this. It was linked to in the first result I found for "knapsack with small weights", link.

      But also the code is super sketchy, it didn't work until I added a bunch of dummy elements so that there were always 200,000 elements.

      So I guess most D1 coders are too smart to try this :)

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

C problem, I'ts either I'm not understanding the problem or I'm making an erroneous assumption in my thinking that is making me get WA. I'm happy to learn about my mistake once the contest is over.

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

How to solve E ?

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

    Lets pick K souvenirs with W=3, so we can take souvenirs with sumW <= m — k * 3 (if negative, skip this K). Lets store souvenirs with w=1,2 in one array sorted by decreasing value c / w. So, if we should choose some souvenirs from this array with sumW = x, we greedily takes souvenirs until sumW <= x (after that sumW == x or x — sumW == 1 — in this case we should take largest souvenir with w=1 or remove smallest souvenir with cost w=1 and take with w=2). So, if we iterates over K in decreasing order, we can maintain second value by two pointers technique.

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

Where is option to hack a solution.

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

how to solve D??

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

    Not sure if my solution is the best, but it worked: So left part is 0, right is whole sum. Go through the array subtracting from right and adding to left. Add current element to set. Check if left is equal to right — solution is YES. When left is greater than right, check if difference between them is even. If yes, check if difference / 2 is in the set. If yes — we have the solution. (I also made the same thing moving right to left, but I guess it may be unnecessary)

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

    Lets store two multisets(left, right). sum(set) — sum of the all elements in set. Lets add [1, 1] to the left and [2, n] to the right. On the next step there a 2 main cases:
    1. sum(left) = sum(right) -> YES
    2. sum(left) > sum(right) (if opposite swap the sets). if left set containse value (sum(left) — sum(right)) / 2 -> YES

    After this step we remove a[i + 1] from right set and add it to left set.

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

    First of all, maintain for each element y the first and last appearance in the array. Now fix the position i where array will be split.

    If sum(1, i) = sum(i + 1, n), we are done.

    Else, if sum(1, i) > sum(i + 1, n) we need to remove a element x from (1, i) and add it to (i + 1, n). We will have that sum(1, i) — x = sum(i + 1, n) + x <=> sum(1, i) — sum(i + 1, n) = 2 * x, x = (sum(1, i) — sum(i + 1, n)) / 2. Also x must be integer, so sum(1, i) — sum(i + 1, n) must be divisible by 2. To check if x appears in (1, i), just check if first appearance of x is <= i.

    If sum(i + 1, n) > sum(1, i) we use same idea, but now x = (sum(i + 1, n) — sum(1, i)) / 2 must appear in (i + 1, n).

    Also check that after moving an element, both parts will be non-empty.

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

I have never hacked solutions. Tell me please, where to start?

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

    On top of the window with accepted solution source code there is link "hack it!".

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

      I found it) The question is "In what ways I can find weak spots of solutions?"

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

        Hacking is code analysing. You can find weaknesses in usage of data structures, e.g. see thread http://codeforces.com/blog/entry/51989?#comment-360480 kunparekh18 at first for problem D used (just like me) set instead of multiset. I managed to hack mine and his (second) solution with input 6 19 6 5 13 6 13 He uses multiset in his second solution, but it was hacked, because of wrong .erase() function usage (see my comment above). There are known hacks on certain algorithms, e.g. I got hacked http://codeforces.com/contest/792/submission/25847128 because of quicksort. You can probably find generator that generates an array corresponding to the worst case for quicksort (I got TLE on such array). During that contest there were participants intentionally looking for quicksort in solutions and hacking them. You can also observe some rare cases that solution doesn't cover (solution weaknesses). To do that you have to clearly undestand the problem and the code of analysed solution. So hacking skills come with experience.

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

Problem D

t.case 6 5 5 4 4 3 3

Here My output is NO I tried to hack my code, it shows unsuccessful. Also another codes output is YES, I tried and also Unsuccessful! what is this?!

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

In problem A,Can someone suggest why this is wrong. Its giving correct answer on my system but wrong on codeforces custom invocation. Code HERE

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

How to solve B?

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

what is the solution of E?

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

Editorial is published.

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

any suggestions how this solutions for D was hacked?
http://codeforces.com/contest/808/submission/27138172

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

Did anybody else notice that problem E was exactly this problem?

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

Output 1E10 for problem 808B - Average Sleep Time is acceptable?

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

How was this hacked for 808D - Array Division ? Is there some test case I missed? Please help. 27143749

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

    you need to use a map or multiset

    because when you insert some element in a set 5 times for example and then erasing it once

    you are erasing it completely , not decreasing it's frequency

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

      Thanks a lot... I totally missed this!

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

        Function erase(val) of multiset erases all the entries of the element val. To delete an elemnt you have to specify its position, i.e. use iterator.

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

I am facing a problem ... http://codeforces.com/contest/808/submission/27151049 -- C++ 11 http://codeforces.com/contest/808/submission/27151003 -- C++ 14 Same code, gives WA on case 3 and case 2 respectively, but on my PC, both cases give correct answer.

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

Hacking STL Hash set/map is ridiculous: even if this time unordered_set/multiset/map receives TLE (because of collision), next time in a normal CF round I'll continue using unordered_map/set. It's ~4-5 times faster than ordinary map/set (in normal cases — test data is generated before I submit my program.)

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

    I haven't read the problems but surely most of the time, whether or not you use unordered_set/map is largely orthogonal to the main point of solving the actual problem. So if you choose to use a data structure which is known to have a bad worst case, you really have no one to blame but yourself (and yes, even normal CF rounds have anti-hashing cases).

    But if for some reason you need the extra speed, you can just generate a random number and xor your usages of the unordered_set/map with it to prevent it from breaking on specific known cases.

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

My O(N) solution for the problem B failed with TLE... Apparently reading from 'cin' into a double variable is slow enough to make it potentially fail even on 2*10^5 reads.

Reading from 'cin' into an integer took 124ms: 27174013

Reading from 'cin' into a double took 842ms: 27174024

Also my solution 27126612 failed on system tests with TLE. Exactly the same code 27174040 got accepted later in the practice mode.

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

Why there is no Contest materials box in Educational Round 21 page? (http://codeforces.com/contest/808)

UPD : fixed

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

I want to hide myself so that no one can see me in online.

is there any system to do this??????? How??????