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

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

Привет, Codeforces!

13 июля 2016 года в 19:00 MSK состоится четырнадцатый учебный раунд Educational Codeforces Round 14 для участников из первого и второго дивизионов.

<У меня уже накопился большой список задач, пожалуйста не расстраивайтесь, если ваша задача долго не попадает в раунд>

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

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

Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.

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

Благодарю их и всех кто присылает задачи! Количество, присланных, но ещё не использованных задач постепенно растёт. Если я нигде ничего не потерял, то я уже ответил всем кто прислал мне задачи более 5-6 дней назад. Прошу с пониманием отнестись в случае, если ваша задача долго не появляется.

</У меня уже накопился большой список задач, пожалуйста не расстраивайтесь, если ваша задача долго не попадает в раунд>

Комплект задач был предложен участниками сообщества. Задачу А предложил и подготовил Артур Яворски KingArthur. Задачу B прислал Никита Мельников nickmeller. Задачу C предложил пользователь blowUpTheStonySilence. Задачи D и E из большого комплекта задач присланных Zi Song Yeoh zscoder (он, кстати, сейчас участвует в IMO, пожелаем ему удачи). Задача F была предложена пользователем Michael Kirsche mkirsche.

Как я уже говорил задачу A подготовил Артур Яворски KingArthur, остальные задачи для вас подготовил я (Эдвард Давтян). Спасибо Татьяне Семёновой Tatiana_S за проверку английских текстов условий. Задачи вычитывали и тестировали пользователи, предложившие их, соответственно Артур Яворски KingArthur, Никита Мельников nickmeller, пользователь blowUpTheStonySilence и Michael Kirsche mkirsche. Большое им за это спасибо!

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

Good luck and have fun!

UPD 1: Все взломы по задаче D будут перетестированы.

UPD 2: Фаза открытых взломов будет продлена до завтра.

UPD 3: Прошу прощения за проблемы в задаче D. Решения получающие WA3 были перетестированы. Теперь все в порядке.

UPD 4: Соревнование завершено. Все решения протестированы на полном наборе тестов. Вскоре появится разбор задач.

UPD 5: Разбор задач опубликован.

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

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

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

I think I can solve with one or more problems in this test,good luck!

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

"TAK" and "NIE". So fun)

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

Codeforces website is very slow during the contest :/

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

Problem statement is not very clear. :( Also the website is so slow.

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

The english statements were not very clear in this contest :(

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

please check problem statement(english) before contest more than once. :(

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

The statement for problem A (in english) is horrible.

P.S.: I had to use google translate on the russian statement in order to understand the problem.

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

Half of round time could not connect. 'The connection has timed out'.

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

How can O(N^3 * Log(K) ) TLE in problem E ?

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

I am still loading problem A.

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

me reading problem A (before revision)

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

How can O(N^3 * Log(K) ) TLE in problem E?

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

How to solve E?

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

    I Have solved it with Matrix exponentiation.

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

    It looks like DP, but k is too big. So, you may use matrix exponentiation. Let's create matrix A[N][1], every A[i][0] = 1. Then let's create matrix B[N][N]. For every i and j: B[i][j] = 1 if the number of ones in the binary representation of the number (a[i] xor a[j]) is a multiple of 3, else B[i][j] = 0. So, answer is any element of matrix C = binpow(B, k - 1) * A. Complexity O(N * N * N * logK)

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

      Any element of matrix C??Does all element will be same?

      It does not fit with the given sample

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

Why am I getting a TLE in the Problem D?

My code

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

Why am I getting a TLE in the Problem D?

My code

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

    TRUST SCANF AND PRINTF!

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

    The main idea of your code is okay, but it has been implemented very inefficiently. First of all, when number of input >= 5*10^5, it is better to use scanf instead of cin. Also, you could improve your dfs function. It is better to check whether a node has been visited within the loop-this way, unnecessary function calls can be avoided. A lot more optimizations can be done; and I haven't looked at the code more deeply, but I think the logic is okay(as far as I have seen; apologies if I am mistaken).

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

D: UnionFind to find connected groups, sort each group separately

E: Let matrix , then the answer is sum of the elements of MK - 1. You can think of it as counting "paths" (sequences) in a graph with adjacency matrix M.

F: Compress and sort the array. Then we can enumerate all products of pairs which are not greater than max(p) and save counts for each product. There are at most max(p)log(max(p)) such products: (max(p) / 1 + max(p) / 2 + max(p) / 3 + ...). Then we need to count all products which are greater than max(p), using Fenwick Tree or partial sums (e.g. for each index i we find position where ai * aj > max(p) and then sum all counts on suffix starting from j). The latter count will always be added to the answer. Then to compute the answers we need to compute suffix sums on the array of counts per product. Special care needed for repeated elements.

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

Someone else tried to solve D using random selection of pairs for swapping? It was a funny idea but wrong, of course. :)

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

Why didn't they use a template type of definition to create __builtin_popcount() ?

I always get one WA for that!

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

I liked almost all the problems — I didn't have time to read F, as I spent too much time on C, which I didn't like.

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

Can someone explain problem e in more details??

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

    This is actually a graph problem. Vertices are the elements of a, and edges between them are present if number of 1-bits in their XOR is divisible by 3. The task is to find number of valid paths of length k.

    What you need to know is that if you multiply adjacency matrix of this graph k times by itself, you will get matrix that contains info about number of ways to get from one vertex to another in k hops (better explained here). After you get that matrix (this can be done in O(n^3*log k) via binary powering) you just need to sum up the values of the nodes and this sum will be the answer.

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

      I think, He said to explain the problem not solution.
      I also didn't get it, if a={1,1} and k=1 how is the answer 2? anyone explain please

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

        The sequence will be of just one element. You can pick either the first one or the second one. Hence, the answer is 2, and it doesn't matter whether they are equal or not.

        You should count the number of different valid index sequences, not sequences of their values.

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

          but 1 isn't a multiple of 3

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

            Question asks for xor b/w consecutive elements to have no of 1's in them as multiple of three.

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

Thanks a lot for such an interesting round, Edvard! And many thanks to authors for the efforts, it was definitely worth it!

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

Bonus for problem D: calculate the minimum number of swaps to achieve the maximum lexicographically permutation

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

    Other variant for problem D: given two permutations and the allowed swaps, it is possible to obtain one from the other by making a sequence of allowed swaps?

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

Problem D: So, one swap step can be used any number of times!!! Didn't realize that. Anyways, how to solve this when each swap step can be used at most once??

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

    When you found a connected group (with dfs or union-find), you have to put maximum element from that group to the first place and you can do it in only one way, e.g. if the group is 5 3 1 8 7 2 4 then you first put 8 to firstposition, and you have used all swaps between 5 and 8, so you repeat the idea on the rest, e.g. put 7, then put 4: 8 5 3 1 | 7 | 4 | 2.

    EDIT: I've realized that the connected components are not necessarily chains. There even may be loops and therefore multiple paths from the largest element to the smallest position. It is not clear how to choose optimally.

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

In problem B, How is the answer for "opo" is NIE when the answer for "oHo" is TAK?? :/

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

    The symmetric string is "oqo", which is not the same as "opo".

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

    s-palindrome is a string that can be mirrored. For example, oqpo — is TAK (q and p are mirrored to each other).

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

In C, could be there multiple answers?

E.g, 323.345 can be presented as 3.23345E2 and 323345E-3

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

Is unexpected verdict in hack 240056 (problem F) caused by load issues (too many B hacks) or something else?

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

How to solve D? Naive dfs will time out,so how to compute efficiently?

Edit : I understood the solution.

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


https://en.wikipedia.org/wiki/Mirror_image
Nice, thank you very much :P

BTW this is the first problem I see that requires checking for mirror reflections and doesn't clarify what is the reflection of each character. In my opinion doing things like not clarifying makes problems really annoying. Afterall this contest is "educational", it should not annoy us by wasting our time checking if there's a reflection for each of 52 characters

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

    I was hacked because i thought that i can be reflected to it self i.e string : iii does conut as s-palindrome but it turned out it shouldn't

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

    It should teach you that such problems exist. I encountered a reversible stepladder and rotatable calculator-style digits.

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

Was getting TLE on F until I put cin.tie(0) into code.

Then changed everything to scanf and it worked twice faster.

http://mirror.codeforces.com/contest/691/submission/19096778 — scanf version, 1200ms

http://mirror.codeforces.com/contest/691/submission/19096765 — cin version, 2324ms

So the answer is just to drop cin/cout and switch to scanf?

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

The problem statements were really ambiguous. Even if we ignore the mistake in English statement A that was wrong for whole 10 mins, and made the problem unsolvable for English reading coders, why did you feel the need to include: "but not necessarily it should be the last one". It adds no clarification or help to the problem, and only confuses the competitors.

And for problem B, you should've specified that we should use the pictured alphabet to determine what the mirror images of certain characters are. Since it really depends on the font we use. For example: the letter l in some fonts mirrors it self, but here it doesn't, the same happens with the letter i.

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

    I agree. The sentence "but not necessarily it should be the last one" made me think I was not understanding the problem as I could not see which kind of information was this sentence adding.

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

Hi, I want to join to these series rounds.
Why does it named "Educationl"?
Is there any plan for these rounds (e.g any discipline for problems and including subjects for a round)?
Is there any program of study the subjects?
Does it need to solve all the problems in previous rounds to join these series or not?

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

That moment when you hacked yourself :D

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

Can someone please explain Problem Dthat how to model it into a graph. Thanks.

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

    At first you notice that every position is node of our graph and swaps are our edges. Solution of this problem is to find connected components and then sort their elements. For every component we know values of initial permutation. Because we want maximum permutation, the highest value of component must be leftmost (of possible positions that are in current component). If we look at first example, we get 3 components. 1(1) — 4(4) — 7(7) 2(2) — 5(5) — 8(8) 3(3) — 6(6) — 9(9) () — value In first component the highest value is 7, so 7 should be at position 1, then second highest value is 4, so it is on position 4 and 1 is at position 7.

    You actually don't even need to model graph, all you have to do is use DSU.

    I hope this will help you.

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

A, B, C were "stringy" problems, here you can see some of mine solutions using regexes with Perl: A — 19090971, B — 19095540, C — 19089637 (or 19096070)

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

What's going on with D? Is it checker/validator bug somebody found? :)

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

    Yes. Unfortunately, someone else is figured it out too and unlike me, he/she is exploiting the bug instead of avoiding it.

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

    Unfortunately, this behavior blocks challenging submissions on the real bugs in this problem :( .

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

    The hacks for the problem D will be rejudged soon. Testing during the contest was correct.

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

For problem D, I have tried hacking my submission with such test

3 1

1 3 2

1 2

My output is

2 1 3

while the answer given by std is actually the same.

Obviously the correct answer is

3 1 2

so there must be sth wrong with std.

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

+112 hack... Awesome

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

Can someone explain problem A to me in english? I can't understand the description

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

    Every citizen should wear a jacket with exactly one unbuttoned stud (no matter what it's in order, first, last, etc.) except in the case when a stud on the jacket is alone, then it must be buttoned. So you have n studs and its statements (0 — unbuttoned, 1 — buttoned). Print "YES", if jacket buttoned right, or "NO" if didn't.

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

Problem B: Can any one please tell me why I'm getting error in test 14 http://mirror.codeforces.com/contest/691/submission/19109528 since the test case is not fully displayed and can't see it to correct or even trace the answer thanks, Emad

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

    In your mirror function if left == 'w' you are returning true if right == 'W' ( Capital). Here right should be 'w'.

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

For Problem D, my submission http://mirror.codeforces.com/contest/691/submission/19110524 failed on test case 3, it shows the answer for case 3 is "1 2", however I found a lot of other's submission that the answer for case 3 is "2 1". So my question is which is correct?

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

Will submissions for problem D for virtual participation be re-judged? because I still have this invalid hack.

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

    It was rejudged, you got OK.

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

      Only submissions are rejudged, right? Hacks are still shown with "Ignored" status.

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

      I am still hacked in the virtual participation submission.

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

      I see that final testing is complete but challenges are still not rejudged (have "ignored" status). Some wrong solutions are passed as a result. See http://mirror.codeforces.com/contest/691/submission/19091023 and its challenge 240335 for example. This solution doesn't use path compression and so needs O(n^2) time on average (in the set construction phase) on my test in the challenge. If you are not going to rejudge these challenges, could you please add tests from them?

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

        I can't do rejudges myself. I will add the test to the testset. And discuss possibility to rejudge the challenges.

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

Where is editorial for this contest ?

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

The runtime for problem E is not realistic at all. I have got TLE on test case 12 and tried it on my PC and it worked in less than 700 ms. I think something wrong is going on.

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

hi, I don't understand the problem D, principally this part: "p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so pk = qk for 1 ≤ k < i and pi < qi"(the core of the problem :) ). Could you please, explain me this. thanks

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

    Let p and q be 2 different permutations. Permutation p is lexicographically smaller than q if the first element that they differ at, is smaller in p than q.