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

Автор Fefer_Ivan, 11 лет назад, По-русски

Добрый день, Codeforces.

Сегодня в 19:30 по московскому времени состоится Codeforces Round #197.

Авторами этого раунда являются я и Gerald. Условия переводила Delinur, за что ей моя искренная благодарность. Так же спасибо MikeMirzayanov за созданиe и поддержку Codeforces.

Стоимости задач: 500 — 1000 — 1500 — 2000 — 3000.

Удачи!

UPD: Чтобы сделать анонс более интересным и увлекательным мы считаем необходимым вставить в анонс шутку про коней и фотографию, на которой изображен процесс подготовки раунда.

Воспитательница в детсаду:
- Коновалов, ты зачем сломал Конюхову его игрушечного коня?!

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

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

Too late and too short announcement!

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

I hope to it has DP && graph problems ... thanks for great time

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

годная фотка :] у меня шкаф дома такой же :]

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

    Что там вообще в углу происходит?! Там кажется искривление пространства.

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

Я считаю, что конь — однозначный вин.

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

Is this a step towards the COW LEVEL?

I wonder what's the effect of the mask on coding performances. On one hand you probably focus a bit better, but you might also become horsey...

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

Really intresting [but easy!] Problemset and nice horse joke and photo!!
Thank U a lot!!

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

Very nice problems.. Thanks to authors...!!!

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

How to solve E?

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

    Not sure if this is correct ;) Would also be curious to learn the intended solution. I think this is not it.

    Intuition: a sequence of length 1000 after three operations consists mostly of a few sequences like 5,6,7,8,... and 9,8,7,... . The boundaries of such sequences are of interest to us, because they may have probably been the points where the string 1,2,...,1000 was "broken". For example, in the sequence 321789456, the numbers 3,1,7,9,4,6 seem to be interesting. On the other hand, there should not be many interesting numbers.

    So, let's say that a number i is suspect if it is not neighboured in the sequence by the numbers i-1 and i+1 (and let's also have 1 and n be suspect). We do backtracking — we try to generate all possible sequences that are created by reversing subsequences that begin and end with a suspect number. The complexity should be , where s is the number of suspect numbers (I would guess no more than around 14).

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

pretests are too weak!

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

На чем ломали Е?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится
    1. На том, что рассматривали непрерывные блоки как один элемент.

    2. Жадный алгоритм.

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

      А почему 1 вариант неправильный?

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

        Вот такой тест ломает мое решение:

          7
          6 7 1 2 4 3 5
        

        Правильный ответ:

          3
          5 6
          2 7
          1 6
        

        6 и 7 должны разделиться.

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

    На TLE.

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

nice system testing! ))) thanks

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

Как решается E(div2) ?

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

    Это был контест на один дивизион. В приписке div. 2 не было необходимости...

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

    Я дорешал таким алгоритмом:

    Разделим наш массив на цельные куски, то-есть такие, что состоят из последовательных чисел (возрастающих или убывающих). Запомним все позиции, которые являются концами таких кусков, а потом переберём все возможные пары (L;R) из этих позиций, для каждой из них выполним переворот в массиве, и пойдём рекурсивно(с максимальной глубиной 3) к началу алгоритма. Если в какой-то из моментов получили правильную последовательность — восстанавливаем ответ.

    Единственное что, потребовалась следующая оптимизация: для R брать только концы кусков.

    Итого: 810 мс, и если избавиться от векторов — 342 мс.

    Асимптотика что-то около O(n·maxc6) , где maxc — максимальное количество цельных кусков в массиве.

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

How to Solve D?

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

    I you knew Segment tree you could solve it!!!

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

      enlighten me please, I could't find a suitable Data Structure for it

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

      I haven't learnt about segment trees yet, but I solved the problem by storing all the results inside a 2D vector. Then for each query, you will have to update 17 nodes in the worst case. My solution wasn't very fast though.

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

    You can simply solve it using Segment Tree. Suppose you have a Segment Tree which is a Full Binary Tree with 2^17 leaves and thus has height of 18. Now you need a property to compute the value of one node using its children. If your node is at odd height then its result is the OR of its children, otherwise it's their XOR. You can update in O(logn) and find the wanted value in O(1) (just take the root of the tree) Hope i helped :)

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

Nuff said.

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

Problem C is very tricky :(

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

    I failed C as well, however the contest was interesting and the problems were very well explained.

    Thank you very much Fefer_Ivan.

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

    I get AC after the end of competition. Just because I add code that enumerate the first weight of left scale. so sad...

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

Got it... Sry

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

7 successful hacks for Problem C just with this simple test:
1110000000
4
:O Just Like my previous avatar!

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

for problem E, answer given by solution for testcase#7 is incorrect. the result won't be 1,2,3,4,...,98,99,100 the result for given answer by judge's solution is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 97 98 22 23 24 25 26 74 73 72 71 70 47 48 49 50 51 52 53 54 55 56 57 58 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 27 28 29 64 65 66 67 68 69 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 63 62 61 60 59 92 93 94 95 96 99 100

it's not correct! or i & many other contestants understood the problem in a wrong way.

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

Can anybody explain why do this solution get AC?

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

    i didn't read the algorithm, but it's output for TC#7 is same as mine, but he passed it and i didn't! i don't know why!!! here is my code

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

      No, your answer is reversed.

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

        oops. the problem wanted her movements, not us! :| by the way, my algorithm is not correct, i reversed it just to check, and i didn't pass TC#8 because i'm solving it with more than 3 moves.

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

During the contest,Aatr0x (I don't know him) sent me following message... And I noticed he passed D.Anyone sent D's sourcecode to him?

#include <cstdio>
#include <algorithm>
#include <vector>


using namespace std;

char s[15];
int m,last,cnt;
vector <int> v,ans;
int l,r;

int main()
{
    scanf("%s%d",s,&m);
    for(int i=0; i<10; i++)
        if(s[i]=='1')
            v.push_back(i+1);
    while(1)
    {
        int i;
        for(i=0;i<v.size();i++)
        {
            if(v[i]!=last && l+v[i]>r)
            {
                last=v[i];
                l+=last;
                ans.push_back(last);
                break;
            }
        }
        if(i==v.size())
            break;
        cnt++;
        if(cnt==m)
            break;
        for(i=0;i<v.size();i++)
        {
            if(v[i]!=last && r+v[i]>l)
            {
                last=v[i];
                r+=last;
                ans.push_back(last);
                break;
            }
        }
        if(i==v.size())
            break;
        cnt++;
        if(cnt==m)
            break;
    }
    if(cnt==m)
    {
        printf("YES\n");
        for(int i=0;i<ans.size();i++)
            printf("%d ",ans[i]);
    }
    else
    {
        printf("NO\n");
    }
    return 0;
}




THIS IS QUESTION C
SEND ME D
»
11 лет назад, # |
Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

"she writes down the bit-wise OR of adjacent elements of sequence a" if this sentences wasnt wrong than

1 . step => a1 , a2 , a3 , a4

2 . step => a1|a2 , a2|a3 , a3|a4

3 . step => (a1|a2) ^ (a2|a3) ...

...

but problem is

1 . step => a1 , a2 , a3 , a4

2 . step => a1|a2 , a3|a4

3 . step => (a1|a2) ^ (a3|a4) ...

Because of this statement i couldnt colve this problem , may be i 'm quilty too because dont read all statement or dont look sample test , whatever there is a problem with statement.

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

    Yeah I made the same mistake at first as well. Just goes to show that reading the sample helps. :)

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

Can anyone explain test 7 for problem E for us? Lots of contestants failed on that with the same output: 3 22 97 27 74 47 69 I don't think this output is wrong... Can anyone help me?

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

imho, D much more easier than C.

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

    it is(just a kind of feeling)! but i dont understand the meaning of the problem D. perhaps i should learn maths harder..

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

      this problem is just standard segment tree problem , not related to maths

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

        That is an interesting statement...

        Can segment tree be defined without using mathematics?

        Unless I am misunderstanding what "maths" means, I do not think it is possible. But someone can prove me wrong.

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

How to approach D efficiently?

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

    After every query only n elements of this pyramid are changing, and you can recalculate them after each query.

    ADD: You can store all information in array a[2N], where N = 2n, elements with indexes more or equal N are leaves and childs of vertex i are 2i and 2i + 1. See my solution

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

      I assume that by pyramid you mean the "recursion" until we reach 1 element...

      So if we have the numbers: 1 6 3 5 and we have query 1 4, we will obtain the list 4 6 3 5, you mean that only pair 4 6 needs to be computed, yes? Then this result will "propagate" and we use it with (3 & 5) to get answer?

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

        By pyramid I meant binary tree, which you can draw in process of calculating the result. On every vertex there is number. You need update value of first element(4), update OR-sum of first two elements 4 | 6, and update value of root of this "tree" XORing (4 | 6) with CALCULATED(you have no need to calculate it again) value of (3 | 5).

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

          Can you please tell me why we need memory of 2^n size? Because, in other seg tree problems I saw using 4*n size of memory.

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

            Segment tree of size k needs at most 2n + 1, where n is the least number such that 2n ≥ k.

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

system testing was very fast today (Y) :)

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

why 4344499 and 4341816 solutions were skipped in system test? There were no additional submission in each of the problems and both of them passed the pretest.

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

Why my solution for Problem D use 1700+ms and other's avg time is 300ms...

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

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

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

    Одно из решений: посчитаем такую динамику bool dp[n][prev][balance], которая говорит нам, можем ли мы после n, положенных на весы гирек иметь такой баланс, при том что последней мы положили гирьку с весом prev. Переходы вроде бы очевидны. Код

    ADD: На самом деле можно обобщить подход и сделать граф с состояниями (prev, balance) c опять же понятными ребрами. И просто проверить, есть ли в этом графе цикл, в который мы можем попасть из начального состояния или простой путь длины не менее n.

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

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

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

В Е последнее отправленное на контесте решение(которое получало ВА на взломе) оказывается выводило перевороты в обратном порядке. И конечно, как всегда в таких случаях бывает, после исправления сразу получает АС. Теперь точно можно со спокойной душой идти убиваться об стенку))

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

А будет разбор задач?

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

the contest dealt with various kind of problems which was very very helpful to develop the skill for a contestant :)

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

Hi all! I solved problem C but i don't explain my code get Accepted this problem

I think it is O(t^m) with t<=10, m<=1000 This is my code http://mirror.codeforces.com/contest/339/submission/4352722 Thank you :D

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

    OMG. really INCREDIBLE. i dont belive that is realy. but it is realy.==> TEST is very low

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

    :|

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

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    include

    define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i++)

    define DOWFOR(i,a,b) for (int i=(a),_b=(b);i>=_b;i--)

    define mp make_pair

    define pb push_back

    define reset(c,x) memset(c,x,sizeof(c))

    define oo 1000000000

    using namespace std; char s[100]; int m,res[10000],sl=0,w[20],t=0,sum[2]; bool ok; void duyet(int x) { if (sl>=m&&ok==false) { printf("YES\n"); FOR(i,1,m) printf("%d ",res[i]); ok=true; return; } if (ok==false) FOR(i,1,t) if (ok==false) { if (w[i]!=res[sl]) if (w[i]+sum[x%2]>sum[(x+1)%2]) { sl++; res[sl]=w[i]; sum[x%2]+=(w[i]); // cout<<sl<<" "<<sum[x%2]<<" "<<sum[(x+1)%2]<<endl; duyet(x+1); sl--; sum[x%2]-=(w[i]); } } else break; return ; } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); gets(s); scanf("%d",&m); reset(w,0); reset(res,0); FOR(i,0,strlen(s)-1) if (s[i]=='1') { t++; w[t]=i+1; } // FOR(i,1,t) // cout<<w[i]<<endl; if (t<1) { printf("NO"); return 0; } sum[0]=0; sum[1]=w[1]; sl=1; ok=false; FOR(i,1,t) if (ok==false) {

        sum[0]=0;
        sum[1]=w[i];
        res[1]=w[i];
        sl=1;
        duyet(2);
    }
    else 
    {
        break;
    }
    if (ok==false)
    {
        printf("NO");
        return 0;
    }
    return 0;
    

    }

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

    i do something like this i used dfs on a tree that have t^m vertex but it will get much faster if you code that if a vertex can't be an answer don't continue it. see my solution 4358155

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

Well, problem A and B are easier than before... And at first thought use dfs to solve problem C will get TLE...

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

Will there be a post with the author's solutions?

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

Some code got Accepted on problem E will fail on this test:

10
5 4 3 2 10 1 9 8 7 6
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    4350288 this one for example.

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

    Can you explain the idea behind this testcase?

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
      --[-----first swap-----]--------------------------------------------
      ---------------------------------[--------second swap------------]--
      -----------------[------------third swap-------------]--------------
      

      Some codes didn't work this situation.

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

        4 2 4 1 3 That example is more shorter (doesn't work that test on his program)

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

What a Ridicule joke... :-|

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

How to solve C problem?

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

how to solve problem C?