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

Автор NelsonMondialu, 3 года назад, перевод, По-русски,

Всем привет!

Приглашаю вам принять участие в двухчасовом Div2 раунде, который состоится в эту субботу 30-го августа в 11:30 по московскому времени. Как обычно, участники из первого дивизиона могут решать задачи вне конкурса.

Задачи были подготовлены мной и MirceaFF (задачи B и C). Хочу сказать спасибо Gerald за помощь в подговке раунда, MirceaFF за перевод задач на английский и MikeMirzayanov за создание Codeforces.

Главными героями задач сегодняшнего раунда будут Caisa и Gargari. Надеюсь задачи вам понравятся. Желаю удачи и удовольствия от контеста!

UPD: Будет использоваться стандартная разбалловка.

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

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

First time to take part out of competition :)

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

I think this is the first round made by someone from Vaslui (my hometown, too) :D My round is coming soon :P

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

The day is just to sign up for a new term, and it's afternoon in China! we happen to have much time for it ^_^ !

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

Very unusual contest time! :D

I think there will be a high decrease of the number of registrants!

Good Luck.

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

Please add time conversions :)

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

    You can check time conversion from contests -> current contest and click on the time given :).

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

    According to this comment, you are not a programming contest addict... :P

    You know you are a programming contest addict when : You have become the master of converting timezones to your country's standard time.

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

Very nice. I will do my best to do this round and get >1700 rating.

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

finally a chance to participate in a good time :D

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

Converted Time Washington DC, District of Columbia, U.S... 3:30 AM EDT http://fc02.deviantart.net/fs71/f/2013/281/0/0/sleep_is_overrated__by_austin_comix_inc-d6ps3kj.gif

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

There wasn't any hurry for posting the blog :D

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

alert("dsjgds");

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

Please link converted time

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

Всегда бы такое время =)

P.S. Я не садист и не мазахист, обычное время для контестов 19:30 для меня — это 2:30 ночи, а в это время мозги обычно уже не соображают совсем.

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

    Ну извини) ладно летом и в выходной такое время. То еще можно написать. А если в будни и для московского времени, кто-то работает, кто-то на учебе. Не особо подходящее).

    P.S. Хотя в этот раз для меня отлично вышло. В 19.30 не успел бы написать)

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

May be i will Miss this contest Due to My Exam

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

is there any contest for beginner problem solving to start practice with ?? HELP

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

    Take any previous contest in virtual mode, for beginners DIV 2 is the place. Why not try the last contest itself : Click here Simply register and familiarize yourself with how a codeforces round actually is.

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

very excited about contest. First time to unofficially participate!!! Hoping to solve ABCD for first time :)

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

    Since solving AB doesn't really give you anything and there's no rating to lose, you should start from D or E. These div2 contests are a true golden mine for trying out risky new approaches :D

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

      Good advice :). I'll probably start from C, try D+E, then go to AB

      Also, do you read all of the problem statements before starting to work on any problems?

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

I want have a good grades in this contest,bless all!

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

I hope the problems have something to do with elegant graphs/dp/trees/combinatorics problems and not some greedy approach with a lot of conditions and corner cases!

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

Hope the problems will be interesting. Let's enjoy it. :)

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

this is my first contest

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

Waiting for a nice problemset!!

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

good time for contest :) <3

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

А где же всеми любимый персонаж контестов Яблов?

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

Объясните пожалуйста, почему, когда я пытался открыть свой код на задачу С, который хакнули, у меня КФ сразу же зависал, и приходилось просто закрывать страницу.

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

условие задачи A. Один я понял, что виды это не обязательно 1 мешок сахара?

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

    я сначала также подумал, что можно купить не 1, а несколько пакетов сахара

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

    Нет, там ничто об этом не говорит, кроме 5 теста

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

    В супермаркете всего имеется n различных видов сахара

    Какое максимальное количество конфеток в качестве сдачи Caisa может получить, если купит ровно один вид сахара?

    Я здал задачу, но до сих пор не понимаю, можно купить только 1 мешок какого либо вида сахара?

    Если можно покупать много мешков, то на тест 1 10 2 30 у автора не правильное решение

    Уже понял, Каиса хочет купить только 1 сахар

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

    Я вообще сначала норм понял задачу, но одно лишнее условие написал, поэтому ВА3. Потом стал думать, что этот придурок таки хочет несколько пачек купить и ВА5. Успел решить Б, С (упала на частном случае) и Д, и только когда до конца оставалось 1-2 минуты — понял как должно быть.

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

What was the solution of problem D?

I starting taking the LCS of the first and seccond line. And then LCS the result with the third line and ... (LCS calculation was DP — But I called it recursively for the new check).

I got segmentation fault. Does anyone know the reason? Is my algorithm correct?

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

    My idea was same too, but this technique wouldn't pass the sample I/O. I mean if there is several subsequence with same length , which one would you consider ? For example

    between

    1 4 2 3
    4 1 2 3
    

    you have 1 2 3 and 4 2 3 , which one would you choose for 1 4 2 3 , here it is obviously 1 2 3 eventually you have to try all the sequences. I think there are some other technique.

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

    You must use suffix automat.(Sorry for mistakes ) :D

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

    This problem is as like as SPOJ: X-MEN
    Difference is in the problem of spoj, we have to find out LCS between only one pair. But In D of this round, we have to find out LCS between each pair. And it is possible, as maximum value of k can be 5.

    *** The problem of SPOJ(given above) can be converted into LIS... Then I solved it in nlog(n).

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

    Your algorithm is not correct, because there could be more than one LCS.

    The solution is quite simple — for every you make a vector Vx = {a1, ... ak}, where ai means position of x in i-th permutation. Now you create a directed graph — iff . Now an observation — if u1, u2, ..., um is a common subsequence, then u1, ... , um is a path in our graph. So now your problem is to find the longest path in a graph. But this is a DAG, so it is easy — you can either make a topological sort, or just brute it in O(n2).

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

      Can you explain the graph creating part a bit please , I mean this part   .

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

        Sure. Let's look at positions of numbers 1 and 2 in our permutations. {x1, ..., xk} are positions of 1 (i.e. in i-th permuation number 1 is on xi -th position) and {y1, ... , yk} are positions of 2.

        Now we create a graph with vertices labeled with 1,2,...,n.

        When x1 < y1, x2 < y2, ... xk < yk, then we create a directed edge from vertex 2 to vertex 1. In other words, we create such an edge when in each permutation 2 comes after 1.

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

          it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(

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

          Thank you , a little question though , if the array was not a permutation , i.e there was repeated numbers , could we have solved the problem using similar approach ? I mean can the normal lcs problem be solved like this?

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

          Thanks for nice explanation :)

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

      it seems we can't do bitmask DP over k. At least my code failed. Could you give me a hint why? I do not get why it fails. :(

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

    That will have problems in case of multiple LCSs. Eg, consider (1,2,3,4,5), (1,2,3,5,4) and (4,1,2,3,5). First two have two LCS : (1,2,3,4) and (1,2,3,5). If you took only one, and that was (1,2,3,4), then you will get final answer 3, whereas the final answer is 4.

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

    The trick here is that input is a permutation (no repeats). Hope this gives a hint to those who still want to think about D.

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

    i donot think u need all of that there is a very important observation which is for every sequence the numbers are found only once so u can save the index of every digit for every sequence and try to start with any of them but u will need to know the last digit taken so that the sequence in valid then u check if all the numbers are in valid position (after the last number) u add this digit in all the sequences to the solution so the state will be (last digit taken) and u will have a loop on the all the digits except the last one trying to choose any valid digit sorry if it seems a little bit messy or alot

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

Pretest 2 for problem E seems so strange...... So many people get WA or RE on this......

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

Div.2 B — find max?

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

What is the explanation of B seriously -_- . I first thought that it may be the maximum number . But I couldn't prove it. But at the last of the just before 3 min contest I see B was solved more than A , So , I just submitted by calculating the maximum number. I don't know if it is true though.

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

    It seems to be obvious that in each step the current energy is equal to h[0] — h[current_step], so you just need to increase h[0] (from 0 to max(h[]))

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

    Instead of increasing height of some pylons you can just increase on all your money height of the first pylon, answer would be the same because increasing height of the first pylon just increases your starting energy. So you calculate minimum energy on the way and then add this energy (or 0) as a height to the first pylon.

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

Problem C?

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

    make dp matrix for 4 diagonal you will need 4 dp arrays for that one to add dollars from up-left and from bottom-left , up-right , bottom-right.
    then make another dp matrix to collect all of them dp[i][j]=dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3*mat[i][j] --> mat[i][j] is original value we subtract 3 of them because we add the same cell 4 times and we need just once.
    one observation is that the one bishop will be on white cell and another will be on black one (like a chess board) because problem statement says that "there is no cell that is attacked by both of them" if you tried to put both on white cells you will see there is a cell attacked by two , try it
    so just loop on all i,j in dp and take maximum in black cells and maximum in white one and result is the sum.
    feel free to ask

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

When 1 hours remaining, then my father call me and come to eat pizza..:<

I solved A and B (for pretests) and I try to solve C, but I failed... and time was too short for me(I can use 1 hour..)

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

Скажите мне пожалуйста, как можно понять, что в задаче A можно покупать только одну единицу какого-либо вида сахара? Написали бы, что это какой-то товар в единственном экземпляре, чтобы не путать бедных участников. Такое неверное понимание не только проходит оба претеста, но и проходит еще два теста после них.

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

Скажите пожалуйста почему на первую задачу на тест

1 10 2 30

авторское решение выдает 70? Вроде бы должно 80

UPD Вопрос снят.

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

    Потому что сдача будет равна семи долларам и 70 конфетам

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

      а если взять 4 сахара, то выйдет 9.20, то есть здача 0 долларов и 80 конфет.

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

        Покупать можно только один раз

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

        увы, можно брать только 1 мешок сахара

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

    Вы за $10 покупаете сразу целый "вид" сахара, который стоет $2 30ct. Вам дают сдачу $7 и 70 конфеток.

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

Объясните, пожалуйста, почему это некорректный тест для Сшки?

http://pastebin.com/YWWKHb6y

хотел по TL завалить, отправил этот тест за 10 секунд до конца и получил "некорректный тест", а там решение за куб было, обидно.

Валидатор выдал "ожидался EOFL".

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

    у меня также было, решилось добавлением пробела в конец файла

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

      Странно, что написанный руками тест с таким же форматированием, но меньшим размером валидатор принимает.

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

    В конце вывода зачем убрали '\n' ?

    		if (i + 1 < N)
    			cout << endl;
    
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      До этого он был, но был еще в конце каждой строки пробел. После отправил без пробелов и пустой строки. Следующая попытка была бы без этих 2х строк кода, но времени уже не было. Не знал, что нужна пустая строка в конце. Спасибо! =)

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

Я упоролся, или в Е все-таки нужен персистентный массив?

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

    Если бы апдейтов было много, то, возможно, было бы так. С таким маленьким их количеством можно спокойно все перестраивать и чистить.

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

    Думаю можно запрос второго вида можно за линию делать(их не больше 50 по условию), то есть обновлять значения до корня.

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

    а как нужно решать задачу с помощью персистентного массива?

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

Как решать D и E?

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

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

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

      это C :)

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

        ахах)

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

        Сорри. D (настоящая): Динамика dp[i] — максимальная НОП, что в первой перестановке она заканчивается perm[0][i] элементом. Переберем предпоследний элемент в первой перестановке. Проверим, что в других перестановках он тоже идет раньше, чем perm[0][i], если это так, то срелаксируем динамику dp[i] = max(dp[i], dp[j] + 1), где j — индекс предпоследнего элемента в первой перестановке.

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

      Это С :)

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

    D — суффиксный автомат. Нa e-maxx.ru почитай, там в разделе суффиксный автомат в самом низу про наибольшую общую подпоследовательность нескольких строк.

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

      Можно и гвозди микроскопом забивать, но можно просто идти в порядке упоминания элементов в любой из перестановок и решать обычную задачу LCS за квадрат.

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

      Эм, задача решается сведением к задаче о нахождении наибольшей возрастающей подпоследовательности за O(n2), где элементы последовательности — вектора позиций элементов a0 в каждом ai.

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

      И, кажется, что суффавтомат тут не работает — он ищет подстроку, а не подпоследовательность.

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

    Я в D сделал так: сначала построил ориентированный граф по первой перестановке. От i - го элемента до всех, кто справа. Затем повычеркивал ребра, которые противоречат остальным перестановкам. А далее задача о максимальной подпоследовательности на полученном графе. Вроде работает =) O(K * N2 * logN)

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

Nice contest Narcis and Mircea! I'm a little bit surprised that there are more pretest passed submissions on B than on A (because B was trickier in my opinion). A was very good for Div2. About C I would like to say that it's nice. I liked D the most, because it's really beautiful despite its very simple input. Initially I thought that E is some kind of HLD with segment tree, so didn't try it for long. Got the right idea in the last 20 minutes (some kind of sorting + DFS). Not the most prolific round for hacking though. Anyway, keep up the good work.

P.S.: Caisa is a really nice name for a task hero. Don't you think? (image) I'm curios what does Gargari comes from.

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

Контест на реализацию. Скучно :\

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

    Тогда почему же Вы не реализовали D и E?

    UPD: да еще и С

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

      Я не умею писать суффиксный автомат(D). Алгоритм описан на e-maxx.ru. Тривиальная задача. UPD: сорри, тупанул) (я же говорил, что не разбираюсь в суф. автомате) :)

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

        Там не суффиксный автомат. Повторюсь, он ищет подстроку, а не подпоследовательность.

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

        там наибольшая общая подстрока находится

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

I missed a hack attempt in problem C. At 01:56 (4 minutes remaining), I saw a solution with overflow problem. I then wrote a code to generate worst case of 2000x2000 with all entries 10^9. Submitted at 01:59:57 ... It itself TLEd!... Then it striked that a 2x2 matrix would have been sufficient. LOL !! =(

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

What a contest! I hacked for the first time!

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

Does anyone know how to solve C?

I precomputed the sums for each position where a bishop could be placed in O(n^2), but I don't know how to find the pair of bishops without checking each possible pair.

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

    Find the best bishop for (i+j)%2=0 and the best bishop for (i+j)%2=1, then add them. Like the board for chess.

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

      Why is this necessary? What if two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other ?

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

        Give me example, please) (When two bishops are placed in squares who are equivalent modulo 2 and they don't attack each other)

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

          Oh sorry, Just realized that is not possible as as soon as you select a bishop , if you draw a line on the board along the square's diagonals , you have divided the board into two halves. Now if you place a bishop in another equivalent square (modulo 2) you have to cross this line which will have an intersection and that square will be attacked by both the bishops.

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

          I have to disagree with you here. Two Bishops attacking each other will have to be in the same diagonal. There is a difference between "two bishops attacking each other" and "two bishops attacking the same cell". The problem statement failed to differentiate between these two. Read this wolfram article. Cell (2,2) and (0,2) will both attack cell (1,3) but they are not directly attacking each other.

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

    colors of bishops should be different

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

    You don't need to check each and every combination of pairs. It is stated in the problem statement that "No position should be attacked by both the bishops", this made the problem simpler.

    Now you need to check the max for bishop on black positions and max for bishop on white position and add those. Thats it :)

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

    If you look carefully then you will see the board is bipartite.A white bishop cannot attack a black one. So find the max black diagonal and max white diagonal. answer is the summation.

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

    Oh, I missed that part. Thanks!

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

    Well , I think you know what a white cell and black cell in chess is. Now see , if you place a bishop in a black cell than you can't put the other in black too. because then they would attack atleast one common cell . try drawing it in paper. So , the problem is no bishop lines intersect each other. so you calculate for each one seperately like this

    //first bishop
    for(int i=1;i<=n;++i)
      int j;
      if(i%1)
         j=1 // for second bishop , j=2
      else
         j=2 // for second bishop, j=1
      for(;j<=n;j+=2)
        // calculate sum from fourcorners
      if(sum>bishop1Max)
         //change max value and position
    
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why so many people get wrong answer on pretest 5 in DIV 2 A problem ?

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

Отдавайте переводить условия лучше Маше.

"Какое максимальное количество конфеток в качестве сдачи Caisa может получить, если купит ровно один вид сахара? Обратите внимание, что Caisa не старается минимизировать стоимость покупки, она хочет получить как можно больше конфет."

Как из этого я должен был понять что нужно покупать всего один пакет?

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

    если купит ровно один вид сахара

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

      Вы имеете ввиду несколько пакетов одного и того же?

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

        да, я так и делал. От куда я должен был узнать что количество ОДНОГО ВИДА, тоже один?

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

          Да, обидно вышло. Хорошо, что участие вне конкурса)

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

            Для кого то коркусный тур) я вот зделал кучу попыток) а вторую здал через 13 минут после первой

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

          Я и в С подумал что

          "Gargari хочет разместить на шахматной доске два слона таким образом,

          что не существует клетки, которая находится под ударом обоих слонов."

          означает лишь то, что не надо учитывать клетку, когда ее бьют двое.

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

Hi, I am a newbie for Codeforces. I found that I was unable to view the results of pretest of my submissions. Everytime I clicked the number linking to the submissions which failed on pretest, the popup was just displaying my source code but no pretest results. And in the direct link of the submission was also just displaying the source. Any can help? Thanks in advance.

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

    this is only possible during practice. In contest You have to figure out by yourself :)

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

    You can't see your output.. You have to figure it out yourself

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

    That is the intended behavior during a codeforces round. You do not get to see the pretest that caused your program to fail.

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

    You can not see pretests during the round. You must find a wrong test and mistake in your solution yourself.

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

    You cannot see pretests during the contest ;)

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

Does anyone know the second test case of C?

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

This is very good contest that I participate first time but I could not solve any problems :D

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

in problem C
change
ll mx1=0,mx2=0;
to
ll mx1=-1,mx2=-1;

Accepted :( :(

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

Too fast systest!!

When I saw my ranking it was at 30% testing. In a few (~30) seconds, after I again checked the dashboard, it was 100%. I was expecting it to be around 40 — 60 at that time.

this is unbelievably fast!

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

Как посмотреть тесты по С? Они у меня не высвечиваются.

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

Подскажите, пожалуйста, почему мое решение (http://codeforces.ru/contest/463/submission/7638490) словило ТЛ?

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

    cin'ом считывать долго, напиши в начале main'на ios_base::sync_with_stdio(0) и получишь accepted.

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

      Да что ж за лажа такая... Не думал, что настолько долго. Все понял, спасибо.

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

Please, could you tell how to count the sum that gives the black bishop using dynamic programming

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

    The better solution is to use array sum[2][N*2]. sum[0] — sums of LT-RB diagonals, sum[1] — sum of LB-RT diagonals. To calculate such array you need only two formulas:

    sum[0][i+n-j-1] += a[i][j]
    sum[1][i+j] += a[i][j]
    

    Then the answer for (i,j) is sum[0][i+n-j-1] + sum[1][i+j] - a[i][j]. That's all.

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

    Just like Prefix sum

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

cin/cout gets TLE for problem C and scanf/printf AC ? Seriously ? Nice...

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

Did anyone else too misread problem C as placing bishops such that they do not attack each other, rather than placing bishops such that they do not attack any common cell. I wasted an hour on this before realizing I had misread the problem.

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

    I wasted half an hour because i thought that they were rocks and i don't know how :D then i wasted another half thinking that they mustn't attack each other :D

    strange contest time leads to weird results :D

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

    Exactly I even coded that to realise at 1:42 the insane thing i did.

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

    I calculated that max cost is 4n-4, only to realize that weights of the cells were input based. (i assumed 1!)

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

    Same here. The problem becomes much harder with this "new" statement.

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

Please publish a complete editorial and update ratings fast :)

Thanks

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

in problem B wouldn't it be sufficient to find the maximum pylon and print it out ?

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

For Prob A, if the input is

1 6
2 80

then, he can either buy just one for 2$ 80cents, and get 20 candies in return or, he can buy 2 worth 5$ 60cents, and get 40 candies in return. So, the answer should be 40 candies, and not 20.

I interpreted the problem in the above mentioned way. It was mentioned that he can purchase only one type of sugar, but it was not mentioned that he can purchase only one quantity of that type. I ended up wasting over an hour over this ambiguity.

Am I correct?

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

    Same with me,

    I think for 1 10 0 70, answer should be 90 (because 3 times of same type can be taken) but for all the AC solutions, the answer gives 30...

    WTH?!?!?

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

    I made the same mistake and cost me 2 WAs. however, maybe the problem setter wrote this line there are n types of sugar in the supermarket, maybe he able to buy one. to inform us that he can buy only one pocket of sugar.

    I think the problem statement should've been clearer .

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

    Same here. The problem statement was not clear. I did the same and ultimately was not able to solve this. I do think due to ambiguity of problem A . More people solved problem B.

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

    Same with me! He can buy several kilos of sugar and get more candies for some cases. Problem has incorrect description I think.

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

Weak test cases for problem E. Even brutes are accepted.

TLE by cin and AC using scanf.

very upset by the contest.

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

:( Just changed cin to scanf on problem C an got AC, it's ok to get TLE because of reading method or the most important part is the algorithm and it complexity ??

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

As a Chinese I do not think there's no difference between "type" and "number".

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

Походу через 2-3 контеста, worse станет белым) (Там видна белая полоса))

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

Problem C got TLE just because of cin\cout.Without it I can become candidate master.Such a bad contest

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

Why this solution is wrong? I used DP over bitmaks of set of sequences and looked for the longest common subsequence.

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

can anyone tell me why i am getting TLE in problem C my complexity is O(n*n) solution code LINK.

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

Nice Round!

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

Stop ZLD! Why you create so many accounts for div.2!

ZLD1 ZLD2 ZLD3 ZLD4 ZLD5

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

TLE code ::: http://codeforces.com/contest/463/submission/7635306

AC code ::: http://codeforces.com/contest/463/submission/7642386

Difference is only a cin function :( too much pathetic :'(

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

nice round! +169 expert again! hoho!

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

Впервые во время раунда решил 4 задачи... Впервые во время раунда решил задачу D... и как назло упала С...

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

Where is tutorial?!!

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

Country Wise Standings has been updated.

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

The E's system test may be too weak.

If the tree is a long link with all nodes is 2 with the deepest node is 3. And I query the last node every time. There seems many AC solutions cannot pass this case.

The data maker by python:

n = 100000
print n, n

for i in range(n - 1):
    print 2,
print 3

for i in range(n - 1):
    print i + 1, i + 2

for i in range(n):
    print 1, n

Maybe I am wrong. Please reply to point it out.

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

Stats about hacks can be found here.

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

how can i solve C in O(n^2)? the number of black and white cells can be up to (n^2)/2

so.. for white_x for white_y for black_x for black_y

i thought O(n^4) but it seems wrong.. sorry for dumb question and bad english

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

    Compute the value for each rightwards diagonal and leftwards diagonal . Now iterate through the whole 2D array , Find the value for that particular cell as (leftDiagVal(cell) + rightDiagVal(cell) — X[cell] ) and greedily update the answer for Odd(i+j) and Even(i+j) . //X[cell] is the value input in that cell Answer = Answer_Odd + Answer_Even

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

      Just got AC, Thanks

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

      How about the following algorithm for C -- (I have not implemented or submitted it because I am way too sleepy and I just can't think, but I would be glad if someone validated this)

      1) Pre-compute the sum of all diagonals.

      2) For every diagonal, there will be exactly at most 2 diagonals where you cannot place another bishop. Except for these (potentially 2 diagonals) calculate the diagonal which will give you the maximum sum by iterating through all the favourable diagonals.

      3) After doing this, simply iterate through all diagonals, and find sum(diagonal) + sum(max_diagonal_calculated_in_(2)). Output the maximum sum found here.

      This is O(n^2). Will this work?

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

Не подскажите как Е решать? Никак разбора не дождусь.

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

The data of Problem E is too weak 7644499 The time complexity of his algorithm is O(q*height) Why can he accept?

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

У вас есть Да! У вас +128 к рейтингу! символично)

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

Задачи очень понравились, спасибо авторам!

(хотя и вчитываться в задачи пришлось больше, чем обычно, что, вообще говоря, странно :)

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

In problem A Div 2, i got wrong answer because i do not see anywhere written that you cannot buy more that one unit of same sugar. I still do not see that, can someone please point out where it is mentioned in the problem A Div 2.

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

I really appreciated with fast turtorial bcz some problem seems hard for me to understand. After understanding the div2(ABCD) problems, I wrote the why and how here.

wrote in chinese. Hope useful for the guys like me^_^

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

In the Div2. C question, I get a TLE when I use cin to scan numbers which is understandable. But when I use fast io for cin, cout; precisely this :ios_base::sync_with_stdio(false);cin.tie(NULL); I get a WA on test1, which runs correctly on my shell though. However, using scanf my answer gets accepted. I have always ignored such fumble. Can anybody please explain me how I can use cin, cout in this case and still not get a tle?

TIA.

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

    Here you can find information about sync_with_stdio function. The reason, why you are getting WA is you unsync your streams, so if you are using scanf and cin in one program (as you're using in yours), then you will get undefined result.

    To use cin/cout with sync_with_stdio, you should not use scanf/printf. In this case it will work properly.