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

Привет, Codeforces!

В 12.06.2022 17:35 (Московское время) состоится Educational Codeforces Round 130 (рейтинговый для Div. 2).

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

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

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

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас: Harbour.Space

Привет, Codeforces!

Мы рады сообщить о замечательной возможности работы и учебы с Vodafone.

Компания Vodafone Group в партнерстве с Harbour.Space University предлагает стипендии для получения степени бакалавра и магистра в области компьютерных наук, информатики, кибербезопасности и разработки программного обеспечения, а также магистра бизнес-администрирования, и опыт работы в одной из ведущих телекоммуникационных компаний Великобритании.

Vodafone Group открывает новый технологический центр в Малаге, международный центр передового опыта, посвященный исследованиям и разработке технических решений, таких как безопасные сети, разработка 5G и 6G, Open RAN, IoT, MPN & MEC и UCC для Vodafone Business, платформ и корпоративных решений.

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

  • Front-end разработка
  • Full-stack разработка
  • Backend разработка
  • Техническая архитектура
  • Архитектура предприятия

Harbour.Space

ТРЕБОВАНИЯ К ОБУЧЕНИЮ

Общие требования:

  • Аттестат о среднем общем образовании или диплом бакалавра (предыдущий опыт работы обязателен при подаче заявки на получение степени магистра)
  • Резюме или профиль LinkedIn (ваш рейтинг Codeforces должен быть внесен в ваше резюме)
  • Свободное владение английским языком (испанский приветствуется)

Требования для Frontend разработчика:

  • Опыт работы в Angular не менее 1-3 лет.
  • Опыт работы в React не менее 1-3 лет.
  • Уверенное знание основ веб-платформ: HTML, JavaScript и CSS.
  • Разработка и внедрение приложений с низкой задержкой, высокой доступностью и производительностью
  • Определение/построение конвейеров CI/CD с использованием таких инструментов, как Jenkins, Sonar, Kiuwan.

Требования для Full-Stack разработчика:

  • Минимум 3 года подтвержденного опыта разработки платформ (среда на основе CDI/DevOps). С одним или несколькими из следующих:
  • Java SE/ Javascript
  • Сценарные языки, то есть python, perl, shell scripts.
  • Подтвержденный опыт работы с backend и frontend программными системами и веб-приложениями.
  • Подтвержденный опыт работы с HTPP, MQTT, LwM2M, Kafka, различными базами данных (SQL и не-SQL).
  • Знание облачной разработки.
  • Практический опыт работы с инструментами CDI.

Требования для Java разработчика:

  • Отраслевой опыт работы с программными платформами в Linux, локально и в облаке
  • Хорошее понимание серверных технологий
  • Сильные академические знания и профессиональный опыт разработки программного обеспечения: Java Enterprise, Oracle, Linux, Windows
  • Хорошее понимание инструментов системного мониторинга и сред автоматизированного тестирования
  • Опыт работы с SQL, XML, JSON и CSV
  • Опыт предоставления и поддержки преобразований и API для клиентов и партнеров
  • Хорошее понимание баз данных — Oracle, MongoDB, ElasticSearch.
  • Хорошее понимание фреймворков Java, SpringBoot, Spring technologies
  • Хорошее понимание контейнерных систем (docker) и оркестраторов (docker compose, Kubernetes) и технологий обмена сообщениями, kafka, rabbitmq
  • Хорошее понимание оболочки Unix, Perl, python для выполнения задач автоматизации и обслуживания, а также среды CI/CD
  • Образование на уровне бакалавра в области телекоммуникаций или смежных дисциплин с опытом разработки программного обеспечения
Подать заявку →

Желаем удачи и до встречи в следующий раз!

Harbour.Space University

UPD: Разбор опубликован

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

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

Good luck for Everyone

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

Finally a Div2 Edu Round :)

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

    Sometimes the Codeforces community is crazy. Why is this normal comment being downvoted so many times? Can we stop this kind of "insane downvoting"?

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

      People just downvote / upvote like sheeps. If there is a single downvote they start downvoting it more. I dont care about Upvotes and Downvotes anymore :)

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

        Fun fact, a single downvote doesn't show. You need at least 5 for it to show, which is meant to deter sheep-like behavior. Ig your post just didn't resonate with a bunch of people, no clue why.

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

Maybe I am gonna be a pupil this time! Hope a nice problems.

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

I don't know why I like educational rounds so much.

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

    I tend to do worse on educational rounds for some reason, probably because I have trouble with 'classical' problems. I think edu is very high quality, and I'm impressed how many good problems they can come up with in such a short time frame.

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

hope for a good contest, not speedforces .

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

Good luck everyone! Удачи всем! Hemmäňize üstünlik!

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

All the best Everyone!

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

Good luck for Everyone

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

Geez, they don`t expect much out of the candidates, do they?

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

Hope to become BLUE at least today.

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

Do we get solutions of these questions after contest is over anywhere??

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

    Yeah! ...Editorial will be released after the end of contest where you can find the solutions to all the problems!

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

It's annoying when you passed the given test and it fails on some other test case which you can't even see!!!

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

problem A is very easy but B I can't solve it XD!

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

I'll die doing C

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

C was annoying

but D was very great and nice

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

    I got C Idea in 30 minutes, then I spent 1:15 hours thinking of D but In vain.

    Could you give me a hint?

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

        I've already calculated this during the contest, what is the next step?

        • »
          »
          »
          »
          »
          22 месяца назад, # ^ |
          Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
          for every index ask2(1,i-1)<ask2(1,i) you have to know what is this letter at index i ,so ask1(i)
          
          then you have a string like this 
          
          a??c????b???????d???????f?????n????
          123456789..........................
          what do you know about the letters between 2 and 3 ? 
          they are all a !
          
          what do you know about the letters between 5 and 8 ? 
          they are all either a or c !!
          
          and so on .. 
          
          • »
            »
            »
            »
            »
            »
            22 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Wouldn't this exceed the limit of questions if the string is like this?

            abcd...xyzabc...xyzabc....xyzabc...xyz..... and so on

            The generated string after the questions will be abc...xyz????????????.... and more '?' to n which will cause you to search for the 26 possibilities at each time of the n-26 letters.

            How did you overcome this problem?

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

              interactive = binary search

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

                I have used kind of similar approach but getting nlogn complexity that is around 9000 query of type 2 which is not allowed how you overcome that.

                160345223: My submission

                Thank you

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

                  I think he meant to binary search the 26 steps not the whole string

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

                  Just binary search on indices of already existing characters. (26). So take last index of each character, then your binary search will run with an upper bound of log(26)=4.7. so making (log(26)+1)*1000 == 5700 queries is enough. One extra query for checking if there is a non repeating character or not.

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

                  Oh okay thanks I don't know why but I have a bad habit that I just think of approach and implement if it works okay if not then I can't think more about the problem. I will try to improve it.

                  Once again thanks

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

    C is not annoying if solve it the right way:

    1) Initially drop all 'b' from both strings – if resulting strings are not equal then answer is NO.

    2) In initial strings find all occurrences of 'a' – k-th occurrence in first string should be less or equal to k-th occurrence of 'a' in second string. And similar to 'c' but it should be more or equal.

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

      I did exactly the same.

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

      My solution for C has O(Nlog(N)) complexity and it gives tle but some O(N^2) are also passing.

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

        I believe I can help you, I had the same problem on the last Div3 round. lower_bound(set.begin(), set.end(), sus_element) works in O(n) for some reason set.lower_bound(sus_element) works in O(log n)

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

          From what I could tell the reason that lower_bound(set.begin(), set.end(), sus_element) works in O(n) is because std::lower_bound uses iterators to find each pivot. Added up, it takes O(n/2 + n/4 + n/8 + ...) = O(n) time.

          I think they explain it better

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

          Oh it's very important I will remember it. Now it got AC with it.

    • »
      »
      »
      22 месяца назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
      can you explain more ....I solved it and got AC but my sol is not simple in implementation ....
      
      Complexity: O(NlogN)
      

      my solution

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

        Sure, the main idea is to consider operations as moving 'a' through 'b' to the right and moving 'c' through 'b' to the left.

        The logic of the first step is – we can't move 'a' through 'c' and vice versa. So we can initially check if the arrangement of a and c is correct.

        The second step – if there's a k-th occurrence of 'a' in first string that is righter than the k-th occurence of 'a' in the second string then we can't move that 'a' in the required position since we can't move 'a' to the left. Exactly same logic for 'c' and moving it to the right. If we see such occurrences then the answer is NO.

        If neither of 2 conditions above are true then answer is YES – it's because of the same logic from step 2 – we can move each 'a' and 'c' to the required position since we only need to move 'a' to the right and 'c' to the left and it's guaranteed from step 1 that 'a' and 'c' has the same arrangement as in the second string.

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

          Very nice implementation idea altgifted I thought same but was not able to implement it correctly. Had to go through a tough implementation :)

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

In normal Div.2 contests when I re-submit a problem that was previously accepted, I get penalty and the previous one gets skipped. But in this round it didn't happen when I re-submitted. Can someone tell me why?

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

    Because it's ICPC mode

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

      Does that mean the 2nd solution won't be considered? Sorry I'm not familiar with ICPC rules :(

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

        In ICPC mode contests all your accepted solutions will be judged, If for example you have submitted $$$k$$$ accepted submissions and the $$$i-th$$$ one gets accepted, you will get $$$(i - 1) × 10$$$ minutes penalties.

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

Is today's C related to : https://codeforces.com/contest/920/problem/C ? How to solve C? T_T

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

    First, remove all occurrence of '$$$b$$$' and check if they are same. Second, find each occurrence of each non-'$$$b$$$' character in both $$$s$$$ and $$$t$$$. If it is a '$$$a$$$', it must appear in $$$s$$$ no later than in $$$t$$$. If it is a '$$$c$$$', it must appear in $$$s$$$ no earlier than in $$$t$$$.

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

      What is the insight about deleting "b"'s?

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

        because '$$$a$$$' and '$$$c$$$' can't swap, so deleting '$$$b$$$'s can check if their number and order match.

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

          got this one, oh and b's could be simply removed from way either left or right, it's "proved by solution" I guess. Thank you!

          jnidv Thanks!

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

    It's more of a proof problem. I'm not sure tho.

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

      can you pls explain your approach?

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

        S--->T Because a cannot be swapped for c, each char 'a' in s and t must have the same number of char 'c' on the left and right sides ( sequence wise for every a in s & t) Second, we can't change ba to ab, thus for each a in s and t, no of b in left of a in s <= no. of b in left of a in t (sequence wise for every a in s & t). Finally, because we can't exchange cb to bc, thus for each b in s and t , no of c in left of b in s <= no. of c in left of b in t (sequence wise for every b in s & t).

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

        It's essentially the same with Aging1986's solution. But, I didn't think of deleting the $$$b$$$'s. Observe that $$$a$$$'s can only move to the right, while $$$c$$$'s can only move to the left. This means that when iterating from left to right, the number of $$$a$$$'s in $$$s$$$ must always be greater than or equal to the number of $$$a$$$'s in $$$t$$$. Similarly, the number of $$$c$$$'s in $$$t$$$ must always be greater than or equal to the number of $$$c$$$'s in $$$s$$$. Then, also notice that $$$a$$$'s and $$$c$$$'s cannot swap. Meaning, in between $$$c$$$'s, if they exist, there will always be the same number of $$$a$$$'s. Similarly, in between $$$a$$$'s, if they exist, there will always be the same number of $$$c$$$'s. That is why Aging1986 "deleted the $$$b$$$'s". I had a different way of checking that. Every time both the numbers of $$$a$$$'s or $$$c$$$'s, in $$$s$$$ and $$$t$$$, increases, I must check if the previous numbers of $$$c$$$'s or the previous numbers of $$$a$$$'s, respectively, is the same.

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

Can anyone help with C?

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

    There seem to be more solutions to C. I'll explain mine.

    First, we need to make a few observations:

    1. both strings s and t should have equal amounts of 'a', 'b', and 'c'
    2. 'c' cannot be moved towards right in string s (So, each 'c' in s should be present towards the right of its counterpart in string t)
    3. 'a' cannot be moved towards left in string s (So, each 'a' in s should be present towards the left of its counterpart in string t) by doing the given operations.

    Let's start with the observation#2:

    To move a 'c' towards the left from index i to j(j < i), the range [j, i-1] should have all 'b's. Try moving each 'c' in s to its correct position in t. If we cannot move a 'c', we cannot convert s to t.

    Now, all 'c's should be in their correct positions(if possible)

    Similarly, with the observation#3:

    To move a 'a' towards the right from index j to i(j < i), the range [j+1, i] should have all 'c's. Try moving each 'a' in s to its correct position in t. If we cannot move a 'a', we cannot convert s to t.

    Now all 'a's should be in their correct positions(if possible)

    Since all 'a's and 'c's are in their correct positions, now we just need to check if all b's are there in their correct positions and determine the answer.

    Implementation:

    To check if a range contains all b's and make point updates while moving a character from one index i to j(the move is a direct swap of s[i] and s[j] and not actual swaps between adjacent characters to reach the destination), we can use Segment Tree with range query and point updates.

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

    hope my implementation using stack give you some hint :-160349549

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

Worst round since last Month.

Upd. Change my mind:

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

Please explain the solution to the problem D; Thanks :)

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

    Double binary search. First binary search to find the point where a new alphabet first shows up in the string (counting from the left), and then, we iterate through the string from left to right. For each character of the string, we save the last occurrence of the letter, and to determine the unknown character, we do a binary search on the array of indexes of last occurrences to find the index at which the unknown character does not contribute to the number of distinct characters. This should yield a $$$O(26logn+nlog26)$$$

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

    We are going to use binary search.

    Imagine you are trying to figure out index ith, and imagine you already know all characters from 0th to (i — 1)th.

    you can add all the right most index of each character that you have found in an index array, this index size is at most 26. You are going to binary search on this index.

    let say you are considering index jth before ith. if from j to i — 1, the index at i already appears, then you have the same count from j to i — 1, and j to i, bc ith doesnt add anything new. So you can binary search the right most position where this is true, then you can find an index j that is the same with i. so each binary search check, you can check the count from mid to i — 1 and mid to i, mid to i — 1 can be updated after every ith, so it's free. If you can't find this then you can use the first query.

    the total used is at max 6 * 10, you only use 5 times in the binary search, at only use the first type when there's a new character.

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

    Shortly, you restore the characters of s from left to right. The first character is restored by query "? 1 1". For each of the next characters, let's ask if this character is new (by query "? 2 1 i"). If it's new, ask "? 1 i"; otherwise, find the previous occurrence of the i-th character with binary search.

    To run only 5 queries of type 2 in binary search, you can see that we are interested in segments of type $$$[last_c, i]$$$, where $$$last_c$$$ is the last occurrence of some character on the prefix we know.

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

    Keep track of known letters and their last positions. Build the string up from the front by querying the entire string up to that position to find out if its a new letter (if it is then use query type 1 to find out what it is) otherwise do a binary search with the array of last positions to work out which letter it is.

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

D << C

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

E was a nice question with 2 parts to it. How to solve F though?

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

    How to solve E?

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

      Connect a line between 2 points if you can possibly colour them as the same colour. Notice that this will result in a graph of disconnected cliques. The clique can either be colored with 1 colour or different colours for each point. Then, we can use DP to colour them.

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

    F is two sat . You can make some variable : (a[i]<=x) is true or false , (a[i]>=x) is true or false.

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

      Oh wow, I didn't think of it that way.

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

      I get that you could use $$$a_i <= x - 1$$$ or $$$a_i >= x + 1$$$ to deal with the first operation, but how do you go about the second and third operation?

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

How to solve F?

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

Since D requires stupid observations and E,F are unsolveable, todays edu was like speedforces.

Usual edu rounds where mostly implementation based problems, I liked that.

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

    What's the observation for D ?

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

      :v No observation at all! Find the all position such that $$$cnt(1, i - 1)$$$ < $$$cnt(1, i)$$$ and do query of type $$$1$$$ for that position $$$i$$$. After that, do a for loop from $$$1$$$ to $$$n$$$ and take all the last appearance of characters that occur before $$$i$$$ and binary search on it.

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

    A and B make this round somehow "speedforces". But D has a clean solution and I think it's a good problem. I have no idea whether C has a clean (and PROVED) solution because my solution for C was terrible.

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

How to solve D? was D binary search on last unique characters encountered so far?

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

    That is true, the total number of 2 Query will be less than log(26)*1000, Do you search the last 26 characters[a-z] instead of all the previous characters?

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

      For each character ch encountered, I stored its latest index, then binary searched on that vector indices by quering them. But I'm going wrong somewhere. the vector kind of vector<pair<int, char>> where v[i].second is unique. and v[i].first is latest index where v[i].second appears

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

What is test case 10 of E?

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

A and B are TOO EASY as Div.2 AB.

But for Div.2 level contests you don't expect this kind of easy problems so you will spend some time on thinking again about A and B before submitting them, but this will cause your ranking become low and it is VERY disturbing.

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

    Never downvote a post due to the reason "there are already many downvotes and I would like to add more". If you downvote a post you should really have a "good reason" otherwise it's only making this community crazy and unfriendly.

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

      I think this is more about just a lack of self confidence in your skill or a lack of contest experience to notice the problem is actually easy or a trick question imo.

      EDIT: I removed the joke.

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

        I somehow agree with your serious point but your first two sentences are a little bit offensive in my opinion.

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

          Hmm, it was supposed to be a joke and I didn't mean to encourage downvoting, but I suppose I could remove that bit if you find it offensive.

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

            Thanks. Maybe I shouldn't care about downvotes at all.

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

What's wrong with my sol of problem D. It's showing WA on tc 9 160357208

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

Is there a way to solve D without bsearching at every iteration? Feels like there should be an easier way to do it.

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

    I guess no, as the query limit is an obvious indication to do a binary search.

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

      How do you deduce this from query limit that binary search is to be used?

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

Problem C & D, Easy to come up with the solution but frustrating to implement it !!

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

Someone hack my C, https://codeforces.com/contest/1697/submission/160337496, I think it should give tle for large test case

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

This was a nice round, but what I don't understand completely is that my solution of Problem B passes in C++, but does not pass in Python (due to Time Limit). I think that in educational rounds it should not matter which language is used if the idea is correct. But, yes, probably, it is too difficult to check it for multiple languages.

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

    Probably due to slow I/O in python. It's better to load / write data at once.

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

What's the testcase 8 in problem D :(

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

Problem C & D, Easy to come up with the solution but frustrating to implement it !!!!!

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

solved

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

is problem D inspired from this ?

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

When and where can I get the solutions?

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

    Just wait until the announcement post gets updated. It should have a hyperlink "Editorial" by then.

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

Is there any way to increase the speed, it's TLE with Java on problem B ! 160296826

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

    I've replaced Arrays.sort with counting sort.

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

      I watched other's solution, now I know the reason, because the array is not good,so shuffle it first, then sort, just as:

          public static void ruffleLong(int a[]) {
      
              //shuffle, then sort
      
              int i,j,n=a.length;
              int temp;
      
              for (i=0; i<n; i++) {
                  j = random.nextInt(n);
                  temp = a[i];
                  a[i] = a[j];
                  a[j] = temp;
              }
      
              Arrays.sort(a);
          }
      
  • »
    »
    22 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You can also use boxing from int to Integer, 'cause objects (of class Integer, for example) are sorting with MergeSort (worst time NlogN), but primitives are sorting with QuickSort (medium time is better, but worst time is N^2).

    public static void sort(int[] a) {
        int n = a.length;
        Integer[] arr = new Integer[n];
        for(int i = 0; i < n; i++) arr[i] = a[i]; //copy int array to Integer array
        Arrays.sort(arr); //sort Integer array
        for(int i = 0; i < n; i++) a[i] = arr[i]; //copy Integer sorted array to int array
        //worst time is NlogN
    }
    
»
22 месяца назад, # |
  Проголосовать: нравится -54 Проголосовать: не нравится

I don't really see the benefit to require 6000 operations in D instead of 27000, from an algorithmic point of view it seems a bit weird to ask for a constant factor <10, as for the quality of the problem the answer is obviously binsearch, so it adds no more thinking but only risks of missing it, and potentially more time and WA spent for the same problem. That will either prevent you from ACing it or spending more time on more interesting problems.

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

    With 27000, you don't need binary search at all.

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

      That's what I'm saying, moving the constraint to 6000 only "artificially" adds an obvious binsearch which is a bit annoying to code

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

        This would make the problem too easy, perhaps easier than C, and the gap between D and E would be enormous.

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

          Well I think we should not balance problemsets by making implementation artificially harder but rather by finding problems that are harder to solve, but that's only my opinion. Plus I'm kinda bored with "obvious binsearch interactive problems" tbh

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

            But if the interactive problem is not a typical binary search, I feel like it tends to be very adhoc/implementation heavy

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

    (misunderstood the point, so deleted)

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

      binary search is actually "THE algorithm" here

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

      How is binary search not an algorithm?

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

        I never say "binary search is not an algorithm".

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

        I assume the solution is binary search and I would like to see how to optimize a naive binary search to make it fit in 6000 (or at least pay attention to some implementation details to avoid exceeding 6000). My "naive" binary search didn't pass.

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

          I thought the crux of this task seems to design a algorithm with query complexity $$$O(n \log |\Sigma|)$$$ instead of $$$O(n \log n)$$$, and the query limit makes great sense if so.

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

          You only need to run your binary search among the values $$$last_c$$$ as $$$l$$$, where $$$last_c$$$ is the last occurrence of some character you already have met, so there are only $$$26$$$ values to choose from.

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

Can anyone explain for Problem B ( PROMO ) , what happens if x == y? I am confused as if x == y then we need to purchase x+1 items as one purchase will be done and rest items sum will be answer. Can anyone clarify it.

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

    Think of it this way: you pay for the x most expensive items first, and then because of the offer, the store refunds you for the first y cheapest items of your purchase. because x = y, so you don't need to spend a penny after the refund.

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

Can C be solved by using this idea?

First I check if all frequency of some letters are not the same, then it's impossible to form $$$t$$$

Then, I try to move all c to the front. Assume that :

  • In original string $$$s$$$, we have c at position $$$c_1 < c_2 < ... < c_k$$$
  • In final string $$$t$$$, we have c at position $$$c'_1 < c'_2, ... < c'_k$$$

My claim : It's optimal to move c so that $$$c_i$$$ moved to $$$c'_i$$$

I just need to check that for each $$$i$$$ :

  • value of $$$c_i > c'_i$$$ (because we can only move c to the left)
  • there are no a between $$$c'_i$$$ to $$$c_i$$$ (since a cannot be swapped with c)

Then I do the same for a, but I try to move a to the back. I got WA but not sure what case breaks it

My implementation : 160335858

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

    Kind of easier C implementation

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

    I did not read your code but did the same. When you move 'c' don't forget to do the swap. Example : 4 abbc bcab My code https://codeforces.com/contest/1697/submission/160335317

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

Here is my submission for problem D https://codeforces.com/contest/1697/submission/160344339 . The problem states that: "In case you ask too many queries, or the jury program fails to recognize your query format, the answer to your query will be one integer 0. After receiving 0 as the answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer"." The jury program gave me verdict WA, but it also said (in the testcase 10) that i asked too many query type 2. This is unfair, I finished coding problem D when I still had more than an hour to debug.

Edit: actually less than an hour, my mistake xD

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

    same, make the round unrated

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

    This is how interactive problems work — not only on CF, but in official ICPC contests as well. There is no separate verdict for exceeding the number of queries (what should it be? RE, TL, something new?), so the WA verdict is used for it almost everywhere.

    Note that the phrasing in the problem is "you MAY receive some other verdict", not "you WILL receive". This is due to the fact that, in interactive problems, two separate programs are used to judge your submission, and in some occasions, their verdicts can be different (for example, the interactor says that you should get WA for sending too many queries, but then your solution crashes or spends too much time, so it's eligible for WA/RE/TL). That's why you should terminate your program immediately after receiving the response "your query is incorrect", which you don't do.

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

      please quote fully it says "you may receive some other verdict INSTEAD of wrong answer". It may be possible that my English is just bad but to me this statement means that you can receive any verdict on exceeding queries but not a WA.

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

        You can receive any verdict, period. You may receive something instead of WA, or you may receive WA.

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

          The problem did not say "or you may receive wa" or meant so. If it did really mean so, why did statement include "instead of wa"? It was unnecessary.

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

        It says you MAY receive any verdict instead or wrong answer. As BledDest said, it does not guarantee that you will not receive WA

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

          It was so easy to be misunderstood. Your viewpoint is true, some people will understand the problem in the way you did, but many other won't.

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

      Thanks for the informations. However, such things are beyond newbie's level for myself (and some other contestants too, I undertood it after reading your comment though). I mean yes those might be compulsive for highly-rated contestants. But contests are for everyone, I don't think every div2-D-solver should have already taken those into account, some of them might just take contests for fun and have a passion for problem-solving for instance. With all being said, I acknowledged that it was my fault for not checking the number of queries, and furtherly understood how computers work to a certain extent (I'm really thankful and appreciate those informations), but the contest organizer could have done better not to confuse a lot contestants, including myself (I had suffered a lot of emotional damage debuging my code for that problem ngl xD).

      That was just my opinion, also English is not my mother tongue langague so please excuse me for any grammar or spelling error.

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

        Usually it's best just to do what the problem statement says you should do. The problem says that you should terminate your program after getting a $$$0$$$ in response to the query, or otherwise some strange things may happen — so you wouldn't have experienced this issue if you handled this case in your solution.

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

          The word "should" might be used for illustration of meaning "the program will be like this like that" or something similar (I have experienced that while doing some cf problems ngl). Also it didn't say those verdicts are "strange things". As I have already said, contests are for everyone, not only for the experienced. So why wouldn't they make everything clear so that everyone can understand? Mistakes are inevitable, but they should be acknowledged. I am just telling my opinion, no offence here.

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

            Sometimes it's impossible to make everything clear for everyone, unfortunately. I used this exact wording in one of my previous interactive problems, and there were no issues about that. Maybe I'll change the wording for future interactive problems, considering the feedback from this contest.

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

              I believe that many other contestants would have had the same problem so I'm glad that you will consider it, thanks a lot.

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

          By the way, just for clarification, immediately terminating after getting response '0' will also lead to WA verdict, won't it?

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

            just do vector<int> a;a[784]=784; after getting response '0' and you will get Runtime Error instead of WA )

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

    I didn't see you check 0 as return value, so the verdict will be WA.

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

      I'm new to competitive progamming, so I haven't gotten what you mean yet. Please further explain it. Thanks a lot.

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

    yes exactly this statement is the reason why I spent ~1.5 hrs thinking that either my logic or my implementation was wrong. It literally says that you will get "Some other verdict instead of Wrong answer"

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

    I don't understand what you mean — this simply means that if your program is wrong you might get any verdict. You don't need to check 0 in case your program is correct

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

    Better count the queries in code, and put an assert statement in end to get RE instead of WA

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

how to do c?

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

    S--->T Because a cannot be swapped for c, each char 'a' in s and t must have the same number of char 'c' on the left and right sides ( sequence wise for every a in s & t) Second, we can't change ba to ab, thus for each a in s and t, no of b in left of a in s <= no. of b in left of a in t (sequence wise for every a in s & t). Finally, because we can't exchange cb to bc, thus for each b in s and t , no of c in left of b in s <= no. of c in left of b in t (sequence wise for every b in s & t).

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

Can someone please explain me why my solution 160333877 gives TLE? From the code the complexity seems like nlogn. Thanks

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

    I believe, it's because you're accessing st[3] which is out of bounds.

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

      Arghhhh! How did i miss this?! This contest was a nightmare for me. Thanks for taking the time to figure it out.

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

.

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

Wasted 30 mins on C because of a single "break". How careless I am! :(

Anyway,the problems are fantastic!

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

I got the solution idea for problem D from the constraints.

  • First, we can use the first type of query at most 26 times. That indicates that we will use it to know the indices of the first appearance of each character.

  • Second, we can use the second type of query at most 6000 times. After trying some calculations, I found that the nearest calculation to 6000 is 1000 * log_2(26) which is approximately equal to 5000 or smth like that. So, then I came up with solving it using binary search.

Honestly, I think this problem is very interesting!

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

I kept getting WA 7 in problem D so I though that i am not exceeding the number of allowed queries. (because the statement mentioned that I should get some verdict other than WA in this case)

so I was looking for a bug in my code instead of my idea I also added assert to the response to make sure ites not 0 as the question suggested which means not breaking the roles

and after the contest finished I found out that its wrong because it exceeded the allowed queries -_-

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

import java.util.*; public class PalinInd { public static void main(String args[]) { Scanner sc=new Scanner(System.in);

int n=sc.nextInt();
     long q=sc.nextInt();
     long arr[]=new long[n+1];
     arr[0]=Integer.MIN_VALUE;  
     for(int i=1;i<=n;i++)
       arr[i]=sc.nextInt();
     int arr1[]=new int[n+1];
     arr1[0]=0;
     int p=1;
    long s=0;
     Arrays.sort(arr); 
     for(int i=1;i<=n;i++)
     {
       // s=s+arr[i];
        arr1[i]+=arr1[i-1]+arr[i]; 
        //arr1[p++]=s;
     }  
     for(int j=1;j<=q;j++)
     {
         int x=sc.nextInt();
         int y=sc.nextInt();
         int val=n-x; 
         System.out.println((arr1[val+y])-(arr1[val]));
     }
  }

} why my code give tle in 3rd test case in java??please answer

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Arrays.sort is quick sort that is O(n^2) in worse case
    2. Scanner is slow. I used: new BufferedReader(new InputStreamReader(System.in))
»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A to D are good. Problem E seems interesting, will give a try later.

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

It seems like the observation of E is easier than D,but I dont have enough time..

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

What's the different between F and k-sat?

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

https://codeforces.com/contest/1697/submission/160338205 This is my submission for problem C. It fails on test case 407 of main test 2, which isn't visible (only the first 110 lines are visible on the page). Could anyone tell what test this solution fails on?

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

B task is almost similar to this one

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

I love getting rank 3000+ because i solved D and i was unable to solve C, and i am getting passed by people who solved C with O(n^2), feels great and fair :)

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

    You can always hack those who passed with n^2

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

      I tried hacking one and it goes up to 1.9s but it doesn't pass 2sec (i don't think there can be a more optimal hack) C++ is way too fast and O(n^2) solutions pass the time limit. Honestly, i believe that the TL for this problem is just way too big since optimal solutions in C++ pass in about 15ms.

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

        My C just got hacked

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

        Maybe limits for such problems should be reduced to 1.5s

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

        Your hacks were not good enough. You were attempting 10 tests of size N = 10^4. 1 test of size N = 10^5 would have crashed an N^2 solution. Not even C++ can handle ~ 10^10 operations in 2 seconds.

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

          I tried 2 different hacks, the last one (the one you describe) was a curiosity hack because I wanted to see what time difference it would make if I dropped the operations down to 10^4 and increased the number of tests. On my first hacking attempt, I tried the hack you describe — 1 test of size N = 10^5, and yet this didn't crash an N^2 solution. The link to the submission I tried to hack is 160337496 and it is still not hacked.

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

            Apologies. I was only able to find the smaller attempted hacks. You're right though; somewhat incredibly it passes. I'm indignant on your behalf as it doesn't deserve to pass, and also kind of in awe at C++.

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

              No worries, indeed it's insane how fast C++ is, in this submission in particular it loops around ~2.5*10^9 times, and finishes in under 2 seconds.

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

    Educational Rounds always weight each problem equally so solving F only and solving A only can have similar rankings. In a previous Education Round I solved A-D but then C got FST due to a stupid long long overflow and then I dropped to my lowest rating :).

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

Would like to see a great solution for C. My solution requires complicated proofs and cumbersome implementations. Not sure whether I was in a hard and stupid direction again.

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

    The simple solutions of C are based on two observations: the subseq of 'a's and 'c'c in both strings must be same. And the positions of the 'a's (and 'c's) must be so that they can be moved in the desired direction. That makes it possible to implement it with only simple loops.

    example 160322407

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

Anyone please tell me what is wrong with in my submission for C. It is giving WA on test 2. I can't even see that case

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

the guy's solution is weird 160366565
It seems to be written like this on purpose and then hacked by others.

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

For problem B, I used Arrays.sort() and got TLE but after only changing code to work with Collections.sort() it passed. Why is this?

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

good contest

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

I suspect a problem with problem B. Promo I made a very fast O(NlogN) solution using Java, and I got "TLE on test case 3". Since I knew for a fact it was fast enough, I wrote the exact same code logic using C++. It passed. I think the problem should have a second or 2 more, for non C++ users. Did anyone else encounter this problem?

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

    Arrays.sort in Java uses

    • quick-sort for primitives (with worst case O(n*n))
    • And merge-sort for wrapper objects.

    Instead of int[], if Integer[] is used, it passes.

    Check this blog to understand more.

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

      wow, this is extremely helpful, tysm! I never knew this — somehow I have solved many NlogN problems where N>=100k without knowing this haha.

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

Completely bricked C. Bye-bye rating :(

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

Hello, I found in the hacks that it appears as though a solution without prefix sums had passed the pretests on problem B (and then painfully got hacked). Is this intended, or did noone expect this passing the pretests? The submission of interest is as follows: 160341801

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

    difference between x and y could be 2*(10^5), and number of operations could be 2*(10^5). So, yeah prefix sum is expected solution.

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

Could someone say me where my 160349731 failed for problem C. I collected all those places where there is a mistake in string. They should be even in number because there if a letter could be corrected by swapping, then the other letter in pair of it should also be in wrong position. Now going from smallest index to largest index (in the collected indexes). Suppose if 2nd index letter is 'b' and 1st is 'a' without any c between them (I calculated it by prefix sum difference between these 2 positions is 0) then I'll swap them and remove those two indexes from my que. Similarly for c and b pair. Note: if 2nd element in que is 'a' then you can't swap element in 1st position to correct place.

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

Often struggle with constructive algorithm problems in div2 C. Any suggestion for improving in this category will be appreciated.

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

I have somewhat different idea for C, Some observations we can make:

1)In string s, if we have a 'c' at some position,then characters to left of it always remain left and characters to right of it always remain right.Similarly in string t, if we have 'a' at some position.

2)From 1 we can immediately say that if there is index i such that s[i]='c' & t[i]='a' ,then answer never exists.

3)strings should be anagram of each other

Now suppose that i is first index where a 'c'occurs in string s and j is first index where 'a' occurs in second string,and since i!=j(2nd condition) ,wlog suppose i>j ,then we can use first i-1 characters of s to match first j characters of t,this can easily checked if count a,b,c in s till i-1 is greater or equal to count of a,b,c in t till j,now we reduce frequency count of a,b,c in string s. This works because till i-1 we have only 'a' and 'b' in s and since they can cross each other i would be able to achieve any configuration of 'a'and 'b' to match first j characters of t.Now we move to next 'a' in t(because i>j) and disregard first j characters of both strings For example:

bcaabababc

cbbababaac

we start from left i=2 and j=4 count of a,b,c in s=0,1,1 till i and count of a,b,c in t=0,2,1 till j-1 and count in t is greater or equal we move to next 'c'(because i<j) and disregard first 2 characters now i=10 and j=4, count a,b,c in s=4,3,0 till i-1 and count of a,b,c in t=1,1,0 .Again condition is true,we move to next 'a' in t. i=10,j=6 count of a,b,c in s=3,2,0 till i-1 and count of a,b,c in t till j is 1,1,0.Again condition comes to be true. move to next 'a' in t. i=10 j=8 (a,b,c) in s is(2,1,0) and in t is(1,1,0). Again true. move to next 'a' in t .in s (1,0,0) and in t (1,0,0) .Again true and we dont have any more 'a' to move for . and hence we terminate and we can say it is possible to interconvert s and t

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

When will the rating change?

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

    How to check whether System testing is done or not?

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

      Just open your in-contest submission and see 'Sent' and 'Judged' time

      If they are 12-15 hrs apart then system testing is done else they are not.

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

When will Editorial out?

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

In Problem D , (Guess the string) while applying binary search , how you are deciding that whether you have to go left or right.

Can anyone please explain it ?

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

In problem D , (Guess the string) , while applying binary search how are you deciding that you have to go to left or right. Let's say: distinct characters(mid...i) == distinct characters(mid...i-1). Then we are sure that Str[i] = Str[mid]; Otherwise , you have to go left. (How can you say that you have to go left? ) Can anyone please explain it?

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

    You have to create a new temporary array where you store the index of last occurrence of all characters that you have encountered so far and then binary search on that array. if distinct characters(tempArr[mid],i)==(tempArr.size()-mid+1) then move left else you have find a potential character save it into variable (say fans) and move right in tempArray. Finally do ans+=fans;

    LINK->160405246

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

waiting for editorial.....

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

Почему мне, достоверному участнику, рейтинг до сих пор не начислен? (Сейчас у меня рейтинг — 1191)

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

    До сих пор идет системное тестирование. Рейтинг будет начислен в течение некоторого времени после системного тестирования

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

      Спасибо!!!

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

        Теперь понятно, почему ты так ждал обновление рейтинга :D

        Поздравляю с зеленым рейтингом!

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

          Спасибо!!! И тебя поздравляю с бирюзовым :)

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

Very slow system testing because most of people didn't use fast input. Please use it next time :)

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

    the long systests were not because of people not using fast IO, instead it was due to the very few people expanding the systests to a whopping 60+ testcases on problem B only, and still more on other problems

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

O(n^2) solution passing for C. Seriously guys, is this what this has come to?

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

Could someone please explain why the same code gives AC for C when compiled with GNU C++17 (64) but it gives Runtime error when compiled with GNU C++17 ??

Correct soln: https://codeforces.com/contest/1697/submission/160348230

Incorrect soln: https://codeforces.com/contest/1697/submission/160432316

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

    Lines 94 / 109 you dereference an erased iterator which is undefined behavior.

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

Why does my rank keep on increasing by a bit in the hacking phase?

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

Problem C was a nightmare. Tried so many things with "a" and "c" like counting inversions and removing "b" s and they did not work, ate so many penalties and finally went with valid parenthesis approach and still made more penalties because of forgetting edge cases

managed to solve it but ate 7 wrong answers. who else ?

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

I think my solution for problem C was cool. I turned s into a list of tuples by counting same characters in a row, i.e. aaabbaccb would turn into [('a',3),('b',2),('a',1),('c',2),('b',1)].

if there is a match I decrease 1 from current char, otherwise if there is mismatch and possible to fix, I would decrease 1 from the following tuple. i.e., if s=aaabb and t=babaa, Then [('a',3),('b',2)] would turn into [('a',3),('b',1)], then [('a',2),('b',1)], then [('a',2),('b',0)] (when zero I delete it) then [('a',1)], then [('a',0)] and done.

To check that a mismatch is possible to fix is easy. If the mismatch is a!=b, then I just check if the next tuple contains 'b'. Also, when I delete an element I merge two consecutive elements of same char. Also the listis actually reversed so I can pop() in O(1).

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

Why is it showing unrated for me?

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

Is it only me or the ratings for this round hasn't been updated yet for everyone?

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

Waiting for the rating to change.

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

the same code "copy & paste" :

TLE : 160442368

ACC : 160372033

How does this code get Acc with O(N ^ 2) where N is up to 1e5?

I see a lot of O(N^2) with Acc not only this

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

This is a more formal explanation of a solution to problem D.

Denote a query of type 2 by $$$ d(l, r) $$$, i.e. the number of distinct letters among $$$ s_{l..r} $$$.

First, find the first occurrence of every letter in the alphabet. They appear at index $$$ 1 $$$ and all $$$ i $$$ where $$$ d(1, i - 1) < d(1, i) $$$. Use queries of type 1 to find out the letters at these indices. There are at most $$$ d(1, n) \le 26 $$$ such indices.

Then, consider all prefixes of the string $$$ s $$$ in ascending order of length. Denote some prefix by $$$ p $$$ and its length by $$$ m $$$. Assume we know every letter in $$$ p $$$ already, now we will determine the next letter $$$ s_{m + 1} $$$. If we already know $$$ s_{m + 1} $$$ from the first step (because it is the first occurrence of a letter), we can move on to the next prefix.

Maintain $$$ c = $$$ set of letters in $$$ p $$$, and $$$ L $$$ = map of each letter in $$$ c $$$ to the index of its last occurrence in $$$ p $$$. Since $$$ s_{m+1} $$$ is not the first occurrence of a letter, $$$ s_{m+1} \in c $$$. Sort $$$ c $$$ by the value of $$$ L[c_i] $$$ in ascending order. We are looking for the last letter $$$ k $$$ in $$$ c $$$ where $$$ d(L[k], m) = d(L[k], m + 1) $$$, because it implies $$$ d(L[k] + 1, m) < d(L[k] + 1, m + 1) $$$ $$$ \implies s_{m+1} \not\in s_{L[k]+1..m} $$$ $$$ \implies s_{m+1} = k $$$. Note that we can compute $$$ d(L[k], m) $$$ instead of making a query. We can binary search for the required $$$ k $$$ in $$$ c $$$. Continue by setting $$$ p + s_{m+1} $$$ as the next prefix.

$$$ O(n \log 26) $$$ queries of type 2 are used.

I upsolved D here: 160441046

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Problem D was so great !!! Thanks for this nice round :)

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

Just did problem E. Awesome problem!

First I noticed that the sizes of equal distance groups can only be 4 at most.

Then I noticed that you just need to keep a list of all points of minimum distance from you.

Then I noticed that the only way to color a few points the same color, is if they are all minimum distance from each other.

Then I noticed that a group (of min dist from each other) has to either be colored the same color, or all different, and this type of coloring is completely independent from the other choices for other groups.

From there it's straight forward, a dynamic programming depending on how many colors remain, and if you choose to color the group in the same color or all different colors (no other options). i.e. dp[number_of_group][colors_remaining][color_same_or_all_different].

Don't yet know its rating, but might be the highest rated problem I solved!

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

Finally specialist!!

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

At problem C. Can anyone explain why I got TLE in the first submission and the other one doesn't?

Link 1: TLE submission Link 2: AC submission