Автор BYN, 12 лет назад, перевод, По-русски

Всем привет!

Совсем скоро начнется Bayan Programming Contest 2012/13 — Elimination Round.

Комплект задач был подготовлен сотрудниками компании Bayan. Мы постарались сделать его как можно более интресным, а также немного необычным! Мы выражаем свою благодарность Михаилу Мирзаянову (MikeMirzayanov) и Геральду Агапову (Gerald) за помощь в подговке задач.

Данное соревнование индивидуальное, оно будет проходить по правилам ACM-ICPC. Условия будут доступны только на английском языке. Также, оно будет рейтинговым только для участников из Div-1, но участники из Div-2 также могут поучаствовать в соревновании.

Соревнование будет длиться 3 часа, участникам будут предоставлены 7 задач. Как и на большинстве ACM-ICPC соревнованиях, задачи будут располагаться в произвольном порядке, то есть не обязательно в порядке увеличения сложности. Не забывайте, регистрироваться на соревнование можно вплоть до конца соревнования.

Лучшие 20 участников будут приглашены на финал соревнования — Участники из Тегерана и лучшие 100 участников получат суверирные футболки. Детальнее про призы можно прочитать в нашем предыдущем посте.

Будьте честными! Во время соревнования запрещается использовать несколько аккаунтов. Также вы не должны обсуждать с кем-либо задачи до конца соревнования.

Удачи!

Геральд: Из-за необычного расчета рейтинга для данного соревнования. Рейтинг будет обновлен с задержкой.

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

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

what??????????? Why is it not rated for div-2 competitors?.what is it???

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

I hope you can make it rated for div.2 participants, it can make div.2 participants more interesting, so they can solve the problems better (because all of the participants want to make their rating higher).

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

what's the problem if the contest will be rated for both div. I think if they put each Div in separated rooms ,it will be fair like any contest each div has it's own standing and rooms but this time will be the same problems. I think also some div2 blue coders have ability to compete with div1 thanks

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

It's not a very good decision to make it unrated for the 2nd division. I destroys competitiveness, contest will become usual training.

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

    Do you think CF-admins didn't think about making some slightly different problemset for div.2 competitors? Obviously, there's some problem about it — too much people competing (compare to middle-crowded Codeforces round) or some trouble with native (i mean, Iranian) organizers or so. Don't cry and get ready for Codeforces Round #148 (Div. 2)!!

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

Could you please explain your reasoning for making the contest unrated for div. 2?

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

    Do you really want to hear the answer on your question? Maybe, you won't like it ;-) ... or maybe it's too complicated to understand (and forgive, either) for div.2 competitors:-)

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

      I'll be frank: I don't like it no matter what the reason.

      But I still want to know, because if I do know the reason, it won't make me feel any worse and at least I'll be able to understand better.

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

        I think the problems are too hard for Div 2, so there would be many contestants who solved 0 problems.

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

        I don't get it. It seems to me that your better understanding is the reaction on getting the answer you wanted. But you say, this is the cause. Makes my head go round, really.

        UPD Besides, here you could see some people giving you two good reasons for that: 1) overcrowded server. 2) hard problems.

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

          Why would my better understanding be the reaction on the answer I want? I don't want a specific answer, I wouldn't ask if I did!

          And what I want to know is the responsible ones' reason. If it's like saying "div. 2 guys, this ain't for most of you".

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

Once again — is prewritten code allowed just as in a typical Codeforces round?

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

input/output will be standard or files? I'm sorry, if this is written somewhere, I didn't find it :) thanks

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

Unable to parse markup [type=CF_TEX] I get that when i try to open problem A. What's the problem? ///EDIT : It got fixed atleast for me

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

when i try to open problem A:

Unable to parse markup [type=CF_TEX]

UPD: just fixed

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

in problem C, can i shoot to the edge of mirror? will i give points and will the beam be reflected?

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

It seems not a good idea to make it unrated for div-2.it is 2’clock in china..and now it seems a wasting -time night for me..

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

    Don't be all about rating, the main idea is to learn something after all + it would've been quite unfair to make it rated because most of the div2 participants would've get their rating decreased, the tasks are too hard for div2.

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

Не знаю, задумано так или нет. Но за ошибку на первом тесте в задаче G не дается штрафа. А он ведь единственный. С этим ничего делать не планируется?

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

    Это не баг, это фича)

    А если серьезно, то сейчас уже поздно что-то менять. Хотя, как мне кажется, было бы лучше сделать WA1 для неверного формата аутпута и WA2 для верного формата, который все же не валит код из условия.

    В том коде, который в условии, есть еще какие-то принципиальные баги, кроме глупой константы 300? Если нету, то там довольно сложно пихнуть рэндом.

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

      Я внимательно прочитал код, других багов там явно нет.

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

      Вроде нет. Там конструктивчик. Первый радиус большой, скажем 1000000, следущие 300 равны 300, 299, ..., 1. x[i] для i=2,...,301 подбираем, чтобы все радиусы сработали, а последний 302-й берем (1000000, 1000000). Тогда в S будет 301 элемент и именно на 301 сработает RELAX

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

        Собственно говоря, я так и сделал.

        Мне уже тоже стал интересен ответ от кого-то из админов на вопрос Павла.

        Я вот сначала отправил "немного неправильное решение" (с промежуточными радиусами 1..300, а не 300..1), потом увидел, что минуса в таблице нету, и решил на приколе послать рэндом несколько раз:) И только потом исправил решение.

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

        А если не менять ничего... С одной стороны, если логично подумать, то о наличии такой лазейки можно догадаться. С другой — а много ли таких людей было, которые догадались до того, как послали первое бревно?

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

    Кстати, действительно серьезная проблема. Если всем дадут штрафные очки по G, я поднимусь мест на 20, и я явно не один такой.

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

    Мда... Ничего исправлять не стали и уже рейтинг пересчитали. Идиотизм какой-то.

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

      По-моему пересчитывать штраф было бы еще большим идиотизмом. Хотя да, весьма странно было, что про такое не подумали. (Подумали, но забили?)

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

      самое хреновое, что такой прокол уже был, правда в тренировке, и все равно не учли это

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

      Если начнут исправлять, то пострадают такие люди, как я. Я когда увидела, что не считается ВА1, начала спокойно засылать различные варианты. А если бы они считались, я бы сделала сабмитов на 20 меньше.

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

        Вообще пофиг кто пострадает, надо исправлять, чтоб все по правилам было. Аргументы типа "Я не получил минус и подумал что теперь все можно" по-моему просто детский сад. Что-то типа я пошел в магазин, украл жувачку, меня за руку не поймали, ну я и подумал, что теперь можно так всегда отовариваться...

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

          по правилам не считать ва1, не?

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

          В ЧАВО написано, что

          Все сомнительные вердикты ("Ошибка тестирования" и др.) не учитываются при подведении результатов, равно как и решения, упавшие на тесте 1 (в задачах, где более одного теста).

          Означает ли это, что в этом случае должны были учитываться? Я, по крайней мере, так понимаю написанное.

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

What's test #8 in problem F?

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

    You are not allowed to go through other junctions when you is travelling between two on the list

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

      And what's the problem? If I travel along shortest path between two junctions, it's a straight line. Obviously, if there are junctions on it, it's impossible to travel between these junctions.

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

        Well, at least for me that fixed problem (I assigned weights for edges based on time)

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

        a9999999b

        1#######1

        c1111111d

        It's better to go from junction "a" to "b" througth "c" and "d".

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

        Go to brom b to c.

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

        There is an ambiguity in the problem statement. Let k be 4 in the last sample. Then in 4-th minute we are in the process of traveling from one block to another and it is unclear what to output. I have WA9 when output the final position and get AC in other case. Maybe this may helps.

        UPD. All above examples are wrong since the junctions in the input are exactly those junctions that we meet during travel.

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

      Can authors tell me, where exactly in the problem statement it's said that you have to pass only these junctions.

      I think, that path abc, goes through ac too.

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

        "We know the initial position of the Old Peykan and the sequence of junctions that it passes to reach its destination"

        It hints that all junctions Peykan passed are in this sequence.

        And I absolutely agree that it's strange to write about shortest path when mentioning the only permitted path.

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

          This sentence sounds closer to the one, that we were supposed to understand, but anyway it's not formal enough.

          Your expression "it hints" is good one, yes it just hints.

          I asked about ambiguity in shortest paths, but I was answered that input is so, that there is unique shortest path.

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

    Maybe the test, where the shortest path between some pair of junctions lies across another junction. I solved this test by replacing Floyd matrix with the original one.

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

      Ok, then consider the following example:

      3 3 3 a1b 1#1 d1c 2 1 ac 3 2

      The path goes from 2 1 to 1 1 and then it has two options — go through 'b' or go through 'c'. So there are two different answers.

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

        Such test is prohibited. They say that string contains ALL junctions in order that the hero passes.

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

          In this case, such test is invalid too and I see no reason for WA8.

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

            This test is correct because we have an edge between "a" and "b". And according to the problem statement you must use this very edge and not any shortest path between these nodes.

            So, although we could get from "a" to "b" by "acdb" path we should use "ab" directly.

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

    I found the problem, but I got wrong answer at #9 all the time.:(

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

Полчаса где-то пытался понять, почему не 110 на втором тесте С (если убрать стену с ценой 120). Печаль...

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

How to solve E?

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

    In E we have a system of inequalities d[j] — d[i] <= 2 and d[i] — d[j] <= -1, if there is an edge (i, j). It can be solved by the standard method with Ford-Bellman algorithm.

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

      Yeah, I've already read some AC codes and understood the solution. Thanks anyway!

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

По поводу задачи С — я убил почти час, пытаясь решить такую же задачу, но заменив отверстия "в точках на стенках" на отверстия "от низу стенки до высоты hl/hr". И все удивлялся, что задачу сдают за 0.03 с нолем памяти.

Задача в моей формулировке решается как-то более-менее адекватно? В моей формулировке получается, что луч выпускают из любой точки левой стенки, которая не выше hl, и он долен попасть в любую точку правой стенки, которая не выше hr. Остальное — как в правильном условии.

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

    Она-то решается, только кодить намного больше и сложность больше. Если размножить нашу полоску, то получится O(N2) отрезков в сумме. Рассмотрим множество всех концов отрезков, а также добавим туда концы изначальных вертикальных отрезков. Тогда у нас есть множество из O(N2) точек.

    Понятно, что оптимальная прямая проходит через какие-то 2 точки из этого набора. Получаем решение за O(N6): перебираем пару точек и для пары проверяем все отрезки. Довольно просто это можно ускорить до O(N4·log(N)): переберем точку, затем отсортируем остальные по полярному углу относительно нее и сделаем заметание по углу. Наверное, можно еще ускорить.

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

How to solve problem C?

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

    I want to know ,too

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

    According to the Dirichlet principle, a laser ray can be reflected only N times, so you can just naively trace it to the position, where it'll get after [0; N] reflections (I mean: you should "unroll" the box vertically).

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

    Let 1<=C<=N is number of intersected mirrors. You may reflect all picture a lot of times.

    So the ray is the straight line with finish r +/- 100 * C or 100-r +/- 100*C. (depends of parity C)

    Then check if line intersect mirrors.

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

I'm disappointed with Problem F (Races) statement. I may be missing something in the text, but:

First, it is not stated that the shortest path is unique, and if it is not, which of the paths should be considered.

Second, it is not obvious what is the exact position of Old Peykan while he moves between two consecutive blocks for several seconds.

So I had to submit two clarification requests to figure that out.

However, if these are indeed ambiguities in the problem statement (and not my fault of not noticing the answers to the above points), I believe the best judges' action would be to broadcast these answers and not just reply to me.

Well, in the end, I didn't accept the problem, and being unsure whether it's my bug or another statement ambiguity is a bad feeling for a contestant.

Nevertheless, thank you for the contest! I liked the problems.

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

    UPD: I found out the third point I missed in the statement, and I consider it's poorly formulated, too.

    It should be emphasized that we can not pass other junctions when moving between two consecutive junctions from the string. Otherwise, it could be understood the other way: we are given the sequence of junctions, and we should visit these junctions in this sequence; however, it is not prohibited to visit other junctions between the junctions of the required sequence.

    For now, I don't see any direct contradiction with this understanding in the problem statement. If there is indeed no such contradiction, please consider rejudging the problem so that both understandings can pass.

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

      As I think, this condition doesn't really matter, does it? Well, if there is path between junctions that does not pass through others, it's a straight line. So, it's the shortest path and solution which looks for it (without condition) should work perfectly.

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

        As moving through different blocks takes different time, it is natural to consider a path to be shortest if it takes the least time to travel, not the least number of blocks.

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

        It would be true if all transfer times were same. Unfortunately, time needed for moving from one cell to another can vary.

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

      If he can pass another junction there are tests like

      c1d
      1#1
      a1b
      

      with multiple solutions when moving from a to d. As there is no sentences like "if there are multiple solutions ...", I thought that the junctions list is full.

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

        If you see the ambiguity, that is, ask yourself "can we visit other junctions while traveling between two consecutive points of the given route?", there are indeed a few hints in the statement that the answer is "No".

        The problematic case is when you see only the "Yes" alternative: there seems to be nothing that contradicts it and forces you to invent that question. I read it like "some points are to be visited in the given order, and the path should be the shortest", and the statement didn't help me to figure out that there are additional restrictions on the path.

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

          My contradiction was described above. Actually, I thought that I've just missed this in statement.

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

            Well, I also thought "can there be multiple solutions", submitted a clarification request, and the judges answered "No". They perhaps thought "No, it is obvious from the problem statement", but with my understanding, I misinterpreted it as "No, we guarantee that there are no such test cases".

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

Problems are interesting, especially the last one (Problem G). I hope someday I can create some problems like this and then make a contest here.

Today I'm a bit luck, my randomized solution passed problem D. (Though I don't know why it can pass.) And then I become red again. :)

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

Great and interesting problems.

But there is a bug in penalty time calculation for problem G.

No matter how many times you WA on G, you got 0 penalty time.

Can we get this fixed?

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

    In codeforces if you fail test 1 you don't get penalty (to avoid submission mistake). No one got penalty for G because G has only one testcase.

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

      That is under the assumption that test 1 is the sample test 1. However, problem G is different and I think it makes sense to have penalty for test 1.

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

        During the contest a lot of coders could think "There is no penalty for problem G, so I can submit as many times as I want". If there will be penalty for this problem, it will be not fair for those contestants.

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

          There are only 2 ways to realize there is no penalty for G during the contest.

          1. Get G Accepted. In this case, it doesn't affect the result.
          2. Look into other contestants' submission history and found the issue. In this case, my reaction was "display error on the scoreboard".
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            It's not true. Wrong submissions are marked in the standings as -n.

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

I think there's some people who will give up participating Bayan onsite because of the flight expenses.

Then,I wonder that , invited contestants will be only people whose rank is lower than or equal to 20th, or include some people whose rank is upper than 20th.

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

    They also have to consider if the rankings will be affected by the penalties from problem G (as said before, right now no one gets penalties). I think they should :)

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

    And I have similar question about top10, whose flight expenses are paid. It will be top10 from the contest or top10 among contestants who will take part in onsite round.

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

    I'm wondering if anyone above the 10th place will pay for the flight out of their pocket.

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

    If someone in the top20 just gives up the chance, will the chance be handed down to the following contestants?BTW, it's quite expensive to fly there..and poor for the 11th,who was just so close to get a free flight..

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

For Problem D, Gassa's AC code 2482976 make assumption that for n = 63 and every p, there is always a solution for this problem. I just tried the case when the input is just 1, ..., 63 in order, and every prime p ≤ 50000, and the assumption does hold. Anyone know how to prove this?

Edit: Just tried 63, ..., 1, and the assumption holds too.

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

    I just thought that for n = 63 (actually it is 127 in the submitted solution), there are 263 subsets which we can take, something like 263 / 64 of them have zero XOR, and these subsets "behave randomly" modulo p, so the probability of finding the solution is very high.

    If p and 10 (base) are somehow dependent, the randomness assumption can break. The only valid cases are p = 2 and p = 5 but these numbers are too small to break the solution. However, my solution could be wrong for non-prime p such as multiples of 10 000.

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

      I have thought about that too, so I strongly believe that the assumption is true. But I still want to find a complete proof.

      By the way, would there be editorial for this contest?

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

Hi there, Can anyone tell me what's wrong with this? Thanks in advance ;)

F — Race

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

This is an old Peykan.

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

There are some troubles with the show of problem.Please check it.

UPD:Now it is fixed.

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

"суверирные" поправьте...

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

Has anyone received the T-shirt?