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

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

Добрый день!

Завтра утром состоится Coder-Strike 2014: Раунд 2. Как обычно, для участия в нем нужно зарегистрироваться на странице.

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

Если есть какие-то вопросы, не стесняйтесь, задавайте их в комментариях.

Удачи и до встречи на раунде!

UPD 1. Прошу прощение за небольшое опоздание, разбалловка стандартная.

UPD 2. Контест завершен, поздравляю победителей, надеюсь задачи вам понравились!

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

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

Количество задач и разбалловка как вчера?

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

    Количество задач — да. Разбалловка, как обычно, будет перед началом раунда.

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

Will the finals be rated for both divisions or the first division only?

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

    May be the finals problems will be too hard for div.2 participants. Now I cannot tell this for sure.

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

When will the finals be held?I hope it's also held at Russian morning(or afternoon) so it will be convenient for coders in China and other east asia countries.

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

    I am very glad to tell you, that mostly it will be held in Russian morning. =)

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

for the rating of this round when you get a best rank between Div 2 participants but between both participants you get the higher rank like 20! wich one is count for your rating?( I got the answer after the end of the Contest THX btw;) )

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

can we get reward point from the game?

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

It coincides OpenCup. dafaq?

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

Назовите разбалловку раунда.

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

Отказ тестирования по E

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

I think problem A of Round 2 have an ambiguity .....the value of ti must be ,min<=ti<=max ... correct me if i am wrong ??

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

    wrong you can see it by exp3

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

    ur not wrong in terms of the answer.
    but since the question doesnt specify these constraints, it means that u must print Incorrect in this case.

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

Что за 9-ый тест в Е? Неужели обычный BFS не заходит? Мое решение работает так: обхожу по столбцам наше поле, если не посещал еще клетку, то пускаю BFS из нее. Ответы на запросы: если клетки в разных компонентах связности, то -1, иначе abs(dist[v] — dist[u]). Что неверного? Вот решение: 6427623

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

    Если посмотреть на ограничения то можно понять что BFS ту будет долго работать (>2 sec). Также здесь есть уловка: "Считается, что клетки первой строки лабиринта нумеруются от 1 до n слева направо, а клетки второй строки от n + 1 до 2n слева направо.".

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

      Ты каждую клетку переберешь максимум 1 раз.

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

      bfs долго? Он посетит никак не больше чем все клетки, разве нет? По-моему хоть несколько раз его тут пускай (и больше, пока не надоест).

      У меня было две ошибки в решении, главная появляется на этом тесте

      2 1
      .X
      ..
      1 4
      

      Была мысль про 2 бфс, но это не помогает при

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

    2 1

    ..

    ..

    2 3

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

I don't know if it's why I've been awake for so long, but statements of problems C and D were a bit difficult to understand.

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

    yes, the explanation of problem D just make me more confused

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

      For the ones not knowing the games 2048, it would be much more difficult to understand

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

    A bit!!!I couldn't understand C through out the entire contest. and still I don't know how the game continues!

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

      I couldn't understand C either, I didn't realize that the questions can be selected in any order.

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

        even i took about 10-15 minutes to realize this fact, because problem statement said:

        then the questions are chosen by the one who answered the previous question correctly.

        since question was so confusing (especially about order), atleast explanation to example cases should have been included!

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

      we have to take care of R2 company only.......

      and they can choose any problem which is not taken already without considering any order......

      for 1st test case, take 1st,2nd and 4th at first then take 3rd no question.....

      The description of C could be more specified.... have no idea about D.

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

So fast systest. Very wow.

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

Nice problems

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

I don' t think there r much div 2 participants...

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

What is the solution to problem D?

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

    hint: You can use dp with bitmask

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

    You do a DP keeping an increasing sequence of powers of 2 by using a bitmask.

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

      Ah, I get it now, thanks. I should have noticed that only the increasing powers of 2 matter :P Also, it is very nice that when we add the number 2 or 4 to the mask, it modifies the mask according to the rules of the game. :D

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

    At first figure out what was the problem . weird statement, one more disgusting contest with poor statement.

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

    Just realize that it can be solved using dp bitmask, anyway i have a different dp solution by considering that it is possible to get 2^{K} if there's 2^{K-2} consecutive 4 (two consecutive 2 can be merge into 4)

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

Кто-нибудь решил b на python? А то я оптимизировал как мог, но все равно не прошло. Может быть, есть способ лучше? Вот мое решение: 6426282 работает за O(n * m)

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

And also I have no idea why my first submission for Problem C got RE. I changed the size of arrays then I got AC later, but why?

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

    I have the same situation, but with problem B :/

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

      in problem B I have same situation too, but that's because i miscalculated array for n is 2000 not 20000 .. LOL

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

        But I' m sure the size is big enough, for the number of auction problems is at most 30.

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

    u have a statement c[i] = a[b[i]], where 1 <= i <= n (not 1 <= i <= m). this is the reason for RE.
    change 35 to 105 and u will get AC.

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

Будьте осторожны, игра затягивает, а времени на контесте не так много!

Вот это в D надо было перед ссылкой на игру написать, а не после.

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

is it problem C can solved by greedy?

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

    Yes! U can calculate the sum of the points of regular problems and the add the points of other problems

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

      how can it be? can you explain a bit more?

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

        well, I' m afraid my poor English can' t explain it clearly... U can view my code. that' s much clearer, I think.

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

    Yes. Basic idea is to take all regular questions first (since you need to take them at some point anyway), then sort auction questions by decreasing order of price and, for each, either double your score or increase it by the auction question price (whichever is greater).

    The point is that you want as high a score as possible when getting to a specific auction question, so you should always start with the highest values.

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

when will the ratings be updated???

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

А свои ноутбуки на онсайте это нормально? Всегда так?

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

    Если рядом с обычным компом — то нет, не нормально. Если из-за отсутствия обычных компов — тоже не нормально, но лучше чем отправить всех по домам.

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

    Вообще, было бы круто писать не на своих компах. А то финал можно и дома написать, а победители потом приехали бы за своими призами.

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

Сделал в youtube 15-минутный скринкаст задания "A", на языке Perl. Если кому интересно — ссылка.

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

First Time to uncheck box "show unofficial" & didn't see any one all of us are unofficial :D

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

Why don't the problems of any Coder Strike round appear in the problemset?

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

What is the solution to E? Is there some approach using segment trees/BIT ?

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

    I used DP in segments of length equal to a power of 2 and then merged them to solve the queries. You could also do that with a segment tree.

    Code: 6427362

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

    Yes, there is a solution using segment tree.

    Consider the interval [l; r].

    Cell of maze will be denoted a pair (i, j) — the index of row and column.

    For interval [l; r] we will store an array d[2][2]. d[i][j] — length of shortest path between (l, i) and (r, j).

    For segments [l; l] is easy initialize the array d. We can easily merge two adjacent segments s1 = [l; m] and s2 = [m+1; r].

    d[i][j] = 1 + min(s1.d[i][0] + s2.d[0][j], s1.d[i][1] + s2.d[1][j])

    My submision: 6425791

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

Why my solution on problem-B gets TIMELIMIT?

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<limits>
#include<vector>
#include<set>
#include<utility>

using namespace std;

typedef long long LL;
typedef long long unsigned LLU;

#define fi first
#define se second
#define DEB(N) cout<<#N<<"  :  "<<N<<endl
LL GCD(LL a,LL b)
{
    return __gcd(a,b);
}

LL LCM(LL a,LL b)
{
    return a/GCD(a,b)*b;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,k,num;cin>>n>>m>>k;
    vector< vector<int>   > chats(m);int i;
    for(i=0;i<m;i++)
        chats[i].resize(20010);
    int j;
    for(i=0;i<n;i++)
    {

        for( j=0;j<m;j++)
        {
            cin>>num;
            if(num==1)
            {
                chats[j][chats[j][20009]]=i;
                chats[j][20009]++;
            }
        }
    }
    int employ[30000]={0};
    int x1,y1;
    for(i=0;i<k;i++)
    {
        cin>>x1>>y1;y1--;x1--;
        for(j=0;j<chats[y1][20009];j++)
        {
                employ[chats[y1][j]]++;
        }
        employ[x1]--;
    }

    for(i=0;i<n;i++)cout<<employ[i]<<" ";

    cout<<endl;
    return 0;
}
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    for(i=0;i<k;i++)
            for(j=0;j<chats[y1][20009];j++)
    

    Complexity of your solution is O(n*k). In worst case n*k = 4 * 10^9

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

There's some editorial for this contest?

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

Астрологи объявили неделю контестов и битмасок.

Прирост контестов увеличился в 10 раз. Прирост задач на битмаски увеличился в 20 раз.

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

    Много улыбок и крови в мире Героев клавиатуры и магии.

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

Помоги решить задачу Е, пожалуйста! Моя идея решения: 1)строим граф, затем dfs-ом находим компоненты связности и в них находим минимальный путь от любой вершины (назовем её главной в этой компоненте) до всех остальных в этой компоненте. 2)Ответ будем искать с помощью LCA в оффлайне. Для этого сделаем списки запросов, затем во время dfs-а для поиска, будем искать предка и пытаться отвечать на запросы. Если главная вершина для u != главной вершине для v, то сразу -1, а иначе ответ будет = dist[u] — dist[lca] + dist[v] — dist[lca]; Вот мой код. Совсем не знаю, где ошибка! :( http://codeforces.net/contest/413/submission/6430904 Помогите, пожалуйста! UPD: я уже понял, что это не деревья

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

    Если нужно, могу рассказать свое решение(Код). Разбор спрятал в предыдущую страницу правки

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

← Rev. 2: Problem C Spoiler Alert!