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

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

Добрый день!

Приглашаю всех принять участие в соревновании, завершающем серию заочных олимпиад ЗКШ для школьников и одновременно являющемся очередным Codeforces-раундом. Начало соревнования - 12 декабря, в 11:00 по московскому времени. 

Соревнование пройдет по правилам ACM-ICPC, продолжительность контеста - 3 часа.

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

В качестве авторов задач снова выступаем я и Дмитрий Матов. Спасибо Геральду Агапову и Артему Рахову за помощь в подготовке задач и Марии Беловой за перевод условий.

Всем удачи!

UPD. Соревнование завершено. Доступны результаты. В школьной индивидуальной олимпиаде победил scottai1, в Codeforces Beta Round - ilyakor. Поздравляем победителей! 

Опубликован авторский разбор задач. Теперь в разбор добавлены также задачи G и H.

Спасибо всем, кто принял участие в серии заочных олимпиад ЗКШ в конкурсе и вне конкурса!



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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ого, сразу две темы о_О
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Пересекается с опенкапом. Гены не будет! :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Гена точно будет в Опенкапе, а не в Codeforces?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Выбрать в данном случае CF это как выбрать ЛКШ вместо петрозаводских сборов. Минусуйте меня.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      На OpenCup.
      Он сейчас в Минске на математической олимпиаде. Так что, и хотел бы досрочно OpenCup отрешать, не смог бы.
      Да и не хотел.
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Спасибо, значит не я один такой :) Я тоже не был, и судя по фоткам и видео - там действительно клёво.

И всё-таки выбор между школьной олимпиадой и opencup, где в это время будут все профи, очевиден.
13 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится
О любовь моя...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Жаль, пересекается со 2м туром саратовской городской олимпиады...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    возможно неслучайно
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Тем, кто собирается писать второй тур городской олимпиады, уже пора спать :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Скорее всего на этих задачах и будет. Если знаешь формат городской олимпиады, то уже можешь проспойлить количество задач :)
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Кто-нибудь знает, OpenCup сегодня точно будет? А то пока нет ни объявления о регистрации, ни ссылки Enter Contest. Обычно они появлялись за день-два.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Будут ли выложены задачи в формате pdf??
  • 13 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится
    Поскольку соревнование личное, мы решили, что условий в pdf сегодня не будет.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Нет, это личное соревнование.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
почему у меня пишет ТЛЕ если у меня на компе всё пашет? может быть там с системой что-то?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Объясните первый семпл тест из задачи С. Если а у нас например 15, то последовательность будет: 1 2 4 5. А если например 19, то последовательность будет 1 2 4 6. Так значит ответ не однозначный же?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Дайте пожалуйста входные данные теста 4 в задаче Д. Сколько голову ни ломал - у меня все проходило. разумеется после соревнования)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    1
    1
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Все понятно) Условия читать я так и не научился
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Исправил ошибку, связанную с тем, что не учитывал единицу как последовательность. Странно, теперь ругается на 11 тест. так же был бы рад увидеть 11 тест задачи Д :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А мне пожалуйста входные данные 9 теста в задаче Д, тоже после соревнования :)
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
ура, я таки красный)
  • 13 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится
    приколист или дальтоник? :D
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      все в куче!
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Это был прогноз, основанный на длительном анализе колебаний рейтинга в зависимости от результатов :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Ты вряд ли ошибся. 3 место в рейтовом раунде при рейтинге большем 1900 гарантирует тебе красный цвет :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        само построение предложения "ура, я таки красный)" предполагает не прогноз, а уже свершившиеся действо по смене цвета :)
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Пожалуйста тест 7 к задаче C 
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Скажите, пожалуйста, 19ый тест на С
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
объясните как решать задачу С пожалуста. и задачу Е 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Скорее всего уже написаны разборы, сейчас опубликуют.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    просто записываешь то, что известно из условия в виде неравенств 0 <= \alpha * (i + 1) + k*10 < 10, где i + 1 сколько раз он заправился до i-й заправки, а k - сколько проехал
    в итоге объединения полуинтервалов получаешь
    L <= alpha < R
    потом находишь из этого сколько можно проехать от последней заправки l <= alpha*n + k*10 < r
    и определяешь, однозначен ли ответ
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      спасибо вот блин правильно думал но несмог написать нужное соотношение. Такая лёгкая задача оказалась
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      гм, на две минуты опоздал =/
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        у тебя идейно другое решение.
        так что тоже полезно, спасибо
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    у меня прошло по C такое решение:

    1. положим a[n+1]=a[n]+a[1] (нумерация с 1)
    пустим бинпоиск по возможному значению альфа
    если существует такое альфа, что можно доехать до a[n+1] , то, собсна, a[n]+a[1] - первый способ
    2. положим a[n+1]=a[n]+a[1]+1
    действия такие же :)
    если можно выбрать такие альфа, чтобы достичь a[n]+a[1] и a[n]+a[1]+1, то ответ not unique
    иначе unique и тот ответ, который получился
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Неочевидная идея. 
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
        смотри, если у нас альфа не целое число, то период остановок будет таким:
        k, k, k, ..., k, k+1, k, k, k, ..., k, k+1, k, ...

        что можно заметить? что на некотором этапе длина поездки может увеличиться на единицу; отсюда, собсна, и решение
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          ну то что города будут смежными-это очевидно. Но вдруг через станций 50 остаток накопится 10 литров и тогда fail? у меня была идея наподобие но я постеснялся ее писать в результате с +7 втупую считал все станции от последней до 3*последнюю
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            гм, тут главное - это понять, что k+2, равно как и k-1, никогда не случится
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Пожалуйста дайте 9 тест на задачу С!
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
how to solve problem C?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    get the upperbound and lowerbound of feasible solution using bisearch
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Binary search for the minimal and maximal alpha, for which given stops are possible. Check if the next stop for these alphas would differ.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Every station si gives bounds (si+1)/i > alpha >= si/i
    Now result can be floor(min_alpha). If floor(min_alpha)+1 also works then there are multiple solutions
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача C решается с помощью решения системы двойных неравенств. Для Alpha, 2*Alpha, 3*Alpha ... N*Alpha и так далее.
Задача E решается динамикой. F(H, T) - может ли победить Иванушка, если сейчас у Змея H голов и T хвостов.
Вот тут интересное начинается. При победе Змея мы хоть как найдем максимальное число ходов динамой. А при победе Иванушки (где надо искать минимальное число ходов) почему-то динамика не прошла и пришлось писать bfs / heap-дейкстру. Я понимаю, что там есть циклы, но вроде их можно просто игнорировать.
Наталья, если не трудно, не могли бы Вы показать 25 тест?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    у меня было WA#25 из-за следующего решения: пускаем поиск в глубину из вершины (h, t) и находим результат

    это не работает из-за неправильного порядка выбора вершин (можно уткнуться в цикл, а на самом деле из него можно выбраться с победой), поэтому bfs-ом находим ответ для Ивана, а потом dfs из (h, t) с меморизацией
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня для Иванушки тоже изначально искалось динамикой. Просто функция L(x, y), которая находила кратчайший путь.
      L(x, y) = forEachPossible (nx, ny) min(L(nx, ny));
      Естественно проигрышные nx, ny отсекались.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    А у меня беллман-форд прошел после отсечения ничьи и победы Иванушки)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня задача разбилась на 3 части:

    1) Предположим, что Ваня выграет - bfs'ом ищем путь к (0, 0)

    2) D[0][0] == INF - Ваня не может выграть. Тогда, если есть цикл, то возможна ничья. Цикл ищем обычным dfs

    3) Ваня проиграет, но теперь мы знаем, что граф ациклический - обычный dp на ациклических графах

    Вот такой вот 3 в 1

13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
А когда обновление рейтинга будет?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Binary search on alpha. First binsearch on minimum alfa (check only the condition if alpha isn't too small), then binsearch on maximum alfa (check only the condition if alpha isn't too big). Then  compute next station for minimum and maximum alpha.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It's possible to find minValue and maxValue without binsearch. Just the main idea:
    Ai <= Alpha * i < Ai + 1
    Here you should do the following:
    minValue = max(minValue,  Ai / i);
    maxValue = min(maxValue,  (Ai + 1) / i);
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
why the following code got presentation error on test 5 of Problem D

const int N = 100010;

long long bk[N];
long long a[N];
int n;

int main()
{
    int i, j, k;
   
    scanf("%d",&n);
    memset(bk,0,sizeof(bk));
    for(i = 1; i<=n;i++)
    {
        scanf("%lld",&a[i]);
        bk[a[i]]++;
    }
    i=1;
    while(i+1<=n&&bk[i]>=bk[i+1])i++;
    if(i<n) printf("-1\n");
    else{
        printf("%lld\n",bk[1]);
        printf("%lld",bk[a[1]]--);
        for(i = 2; i <=n;i++)
            printf(" %lld",bk[a[i]]--);
    }
    scanf("%d",&i);
    return 0;
}
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I haven't read it carefully but you should use %I64d instead of %lld.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      No he shouldn't. If he've chosen Visual C++ compiler, of course... More than that, you don't need 64-bit variable here at all!
      Possibly that's a mistake:
      while (i+1<=n && bk[i] >= bk[i+1]) i++;
      Even if n = 4, Ai can be even 105.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Wild guess - by using "%lld" in scanf/printf, provided you sent it as GNU C++, since it doesn't work well on the compiler that's here (sad...). BTW, why use long longs in this problem?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yeah

    my first code got presentation error on test 5 too.

    i had to change my code completely and then got AC.but still i don't know where i made the mistake.


  • 13 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
    Try test case 
    1
    5

    Correct answer is -1, you print
    0
    1

    I placed a while (bk[1]==0) ; in your code and gave a TLE in case 5, so the case is probably similar to the one I posted.

    edit: typo
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно тест 11 по задаче Е? Если он слишком большой, можно через ЛС.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Here is a slightly different approach without doing binary search.

When a car is located at station X and you refueled your car K times before (let's say initial moment also counts as refuel, so K >= 1), then the amount of fuel in the tank at station X is equal to [alpha * K - X * 10]. You can easily see that:
- if you had to stop at station X, then [alpha * K - X * 10] < 10 because otherwise you would have reached the next station without refuel
- if you didn't have to stop at station X, then [alpha * K - X * 10] >= 10

So, input values give you a set of less/greater conditions on alpha, so you can calculate alpha_lo and alpha_hi for the input data. Then you have to check a few forward station indices X and see if [alpha_lo, alpha_hi) is non-empty for them using the same algorithm. If you find a single matching value X, then the answer is unique. Otherwise it's not.

So, that gives you linear complexity in respect to the max station index.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
During contest I tried to post a question. First it stopped me with 1000 character limit while my question was ~300 characters long. Only issue was that it contained copy-pasted line from problem statement and formatting was long. I don't know how to improve this but I didn't like this situation and I think this should be fixed.
Then when I finally managed to fit in character limit it sent a void message (while I am sure the text was there when pressing submit button). Has anyone had this kind of problems too?
Can some admin look at this?
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
когда блин рейтинг обновят задолбало быть зеленым
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Was this round rated?
13 лет назад, # |
Rev. 4   Проголосовать: нравится -34 Проголосовать: не нравится

this is my code(my reply to Narashy  appeared below the  filix's post!!)

#include<iostream>

#include<vector>

using namespace std;

vector<int> per[100010];

int a[100010],num[100010],lab[100010];

int main(){

int n;

cin>>n;

for(int i=0;i<n;i++)

cin>>a[i];

for(int i=0;i<n;i++)

num[a[i]-1]++;

for(int i=0;i<n;i++)

{

for(int k=0;k<num[i];k++)

{

per[k].push_back(i+1);

if(per[k].size()>1)

{

if(per[k][per[k].size()-1]!=per[k][per[k].size()-1])

{

cout<<"-1";

return 0;

}

}

if(per[k].size()==1&&per[k][0]!=1)

{

cout<<"-1";

return 0;

}

}

}

int l=0;

while(per[l].size()>0)

{

l++;

}

cout<<l<<endl;

for(int i=0;i<n;i++)

{

cout<<++lab[a[i]]<<" ";

}

return 0;

}


13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
The ratings aren't updated.
Why?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

it seems large and it is because i don't know how to post a code here!

please tell me!!!thanks

13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
+197
на топкодере о таких прыжках можно только мечтать =)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Прыжки в другую сторону здесь такие же :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кто-то по-мойму даже +203 к рейтингу получал. (Здесь, а не на TopCoder-е).

    Но всё равно поздравляю.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      http://codeforces.com/profile/watashi
      посмотри на первый контест.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Это смотря как выступать.
    На топкодере за счет учета волатильности прыжки куда больше могут быть.
    Petr за 5 контестов с 1866 до 3000 (227 в среднем), TTLovePP за 2 контеста 1944-2757 (569+244). 

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      там учитывается не волатилити, а количество участий в формуле

      дельта прыжка расчитывается примерно как 150 + 1500/(кол-во участий + 2) (точно не помню)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Забавно:) 
    После первого контеста мой рейт был 1559 и сейчас стал 1559. Но все равно нескромно считаю что мой реальный уровень несколько выше
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я даже после двух загавняканых контестов всё равно остался жёлтым... хотя на tc я зелёный :) Мне не нравится что там нужно создавать класс.. я так и не научился там быстро его создавать и чекать тесты, хотя впечатлений от tc всё равно было море. Щас уже где то полгода не участвовал.

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Именно для этого на TC есть плагины к арене =)
        Самый простой - kawigi, он тебе и класс создаст и main напишет, который проверит код на тестах из условия прямо у тебя на компе.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Он у меня стоит... блин.. я просто так и поленился зайти в вирт контесты, чтоб разобраться, а на одном из срмов так и не нашёл как тестить на претестах.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            эээ.. ну там большая кнопочка снизу - скомпилировать и запустить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Хм.. надо будет ещё раз через лупу посмотреть... Спасибо!
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ура! Я разобрался! Спасибо тебе - заставил меня, ленивого :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        забавно :) у меня на TC рейтинг даже сейчас больше, чем на CF
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    +756

    http://www.topcoder.com/tc?module=MemberProfile&cr=22755328

    :)

    Почему-то на TCO08 есть люди с нулевым рейтингом и прыжками +1900.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Дайте пожалуйста 20 тест для С
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    20
    49999 99998 149998 199997 249996 299996 349995 399994 449994 499993 549992 599992 649991 699990 749990 799989 849988 899988 949987 999986
13 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится
А будет - ли сегодня сведенная таблица результатов индивидуальных олимпиад (школьников) ?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

THX

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Пожалуйста тест 25 к задаче E
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    37 6 50
    10
    2 3
    4 1
    1 0
    2 5
    5 1
    4 4
    0 4
    5 4
    0 3
    4 0
    40
    3 3
    2 2
    1 2
    1 3
    0 1
    3 2
    1 1
    1 5
    5 0
    5 3
    1 1
    5 0
    5 1
    5 1
    5 2
    1 3
    2 4
    4 2
    3 3
    3 3
    5 0
    2 2
    0 1
    5 5
    1 1
    1 2
    0 3
    4 5
    1 4
    3 0
    5 2
    2 0
    3 4
    0 2
    0 0
    3 1
    1 2
    5 0
    0 4
    3 0

    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      вот уже не первый раз вижу, когда выложенный по просьбе участника тест занимает весь экран

      неужели нельзя решить эту проблему как-нибудь иначе, не засоряя комментарии? например, ввести возможность просмотра теста, на котором упало решение (при нажатии ctrl+enter) или просто выложить тестовую базу в свободный доступ

      извините за грубость, но это издевательство - читать вместо обсуждения контеста/задач комментарии вида "жюри, дайте плз тест X задачи Y" и после этого наблюдать сами тесты
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится
        Насколько мне известно, идея выложить базу в свободный доступ команде Codeforces не нравится. Им не хочется, чтобы с Codeforces брали целиком задачи и контесты и выкладывали их где-то еще. 

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

        А так вообще я с тобой полностью согласна. Мне как автору задач было бы удобнее, чтобы проблемы с получением теста решались как-то без моего непосредственного участия. Да и тест такой огромный я, пожалуй, выложила зря. Какие-то маленькие и принципиальные тесты в комментариях еще уместны, а вот такие - вряд ли.
        • 13 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится
          скажу честно: мне не нравится вообще идея выкладывать тесты

          и у меня есть много причин, чтобы предлагать запретить это:

          а) идеи решений обсуждаются участниками в комментариях
          б) разборы висят в отдельной теме
          в) можно скачать решение любого участника, который уже сдал задачу

          уже первых трёх пунктов достаточно, имхо

          г) люди иногда сами предлагают тесты - в некотором роде растёт их challenge-скилл
          д) заставляет участников думать и читать внимательно условия, например, "ааа, у них же головы отрастают, даже если 0 всего осталось..." или "ааа, при тесте "1" оказывается частный слуууучай..."
          е) так как администрация часто онлайн, то в самом-самом критичном случае (предположение "кривизны" теста или что-то подобное) можно всегда написать в личку и попросить тест
          ж) появится гарантия, что после следующего контеста количество мусора в комментариях уменьшится, а не увеличится
          з) учит читать и понимать чужой код
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            гм, надеюсь, что я не ошибся, и возможность наблюдать чужие решения осталась?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Это все очень разумные соображения. Но по-моему, в первую очередь об этом должны думать сами участники, которые спрашивают тесты. Т.е. перед тем, как спрашивать тест, нужно всеми возможными способами попытаться найти ошибку самостоятельно: 
            1) потестировать свое решение;
            2) почитать чужие решения;
            3) пострессить свое решение с чужим;
            4) почитать разбор;
            5) почитать, что пишут в комментариях.
            Хотя ситуации, когда это все не помогает, случаются. Кажется, что "все делаю правильно, но решение не проходит". В этих ситуациях тест действительно необходим, чтобы человек нашел все-таки тупую багу, испытал глубокое удовлетворение от сдачи решения и вновь почувствовал бы веру в свои силы: "я все же правильно придумал решение! если в следующий раз не буду таким идиотом, то обязательно сдам!" Политика Codeforces в этом случае - помочь разобраться, даже если участник сам неправ.

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

            Если вопрос все же есть, лучше задавать его в форме, предполагающей ответ "Да" или "Нет". Это значительно ускорит процесс ответа на вопросы.
            • 13 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
              те, кто спрашивает "какой тест" редко доходят даже до половины твоего списка

              заметь, что в каждом следующем контесте количество сообщений "дайте тест" возрастает, и это печально, ибо происходит благодаря поощряющей такое поведение политике CF (наверное, не совсем правильно выразил свою мысль, но, надеюсь, что меня поймут верно)

              всё равно с этим что-то нужно делать =/
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +6 Проголосовать: не нравится
                То, что количество этих просьб возрастает, я тоже вижу и тоже считаю, что это не очень хорошо. Безусловно, команде CF нужно как-то кардинально решить этот вопрос.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится
          Помоему это совершенно напрасные опасения. Топкодер, например, спокойно выкладывает тесты и я что-то не видел, чтобы интернет пестрил их задачами. Зато выкладывание тестов создает прозрачность и, как следствие, контроль качества. Если авторы задач будут знать, что тесты будут общедоступны, то это еще один стимул делать их по-хорошему.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не исключено, что это связано и с маленьким значком копирайта внизу страничек с тестами/ условиями на ТС. Не уверен, что сейчас у КФ есть такая-же система.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Не думаю, что дело в значке копирайта, просто это никому особо не нужно. Сложно себе представить кого-то кто загрузит все эти тесты и вывесит задачи на какой-то общедоступный ресурс. Кто этим ресурсом пользоваться будет? По-моему никто.
              Ну а если даже и будет, что с того? Меньше народу будет здесь дорешивать? Да и слава богу, меньше нагрузка на сервер. Ведь за дорешивание все равно никаких бонусов нет.

              А прилепить значок копирайта не трудно, естественно и здесь его надо использовать, вместе с еще какими-нибудь надписями.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Впрочем, даже если участники уже смогли вытянуть, что же там в тесте, администрации не всегда есть дело до того, что же случилось.
          Были случаи, когда косяк в условии повалил много участников, которые просто решили задачу до того, как условие было исправлено. Из организаторов никто и пальцем не пошевелил, чтобы кому-то что-то исправить. Недавно был случай, когда на контесте было несоответствие условия и тестов. Об этом было сказано в двух темах, но организаторы это проигнорировали абсолютно, хотя ошибка была более чем очевидна. В результате неверные решения получили AC, а верные получили WA23.
          Мне кажется, что вполне бы уже пора публиковать решения жюри и наборы тестов. Все ошибаются, пусть уж лучше это хотя бы будет замечено.
          P.S.: Я написал это потому, что заметил, что тут проходит игра "Мне не нравится, что..."
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            С задачей про козлов и волков в самом деле проблема всплыла только сейчас, так как ни я, ни Артем не заметили небольшой ветки комментариев по этой задаче. Замечу, что ни у кого из офиц. участников не добавился accepted после перетестирования. Тот раунд был в непосредственной близости от нашего выезда на NEERC и мы были заметно заняты подготовкой. Относительно каких-то других случаев - напишите мне личное сообщение о конкретных задачах в конкретных контестах и тех проблемах, которые вы заметили. Со своей стороны замечу, что администрация прикладывает большие усилия для того,  чтобы решение задач доставляло удовольствие: мы лояльно отвечаем на вопросы, количество redjudges на Codeforces крайне невелико, мы внедрили систему оповещений через alerts, которые участники могут заметить, даже если они в настоящий момент пишут в среде, а не обновляют сайт. Неоднократно мы делали clarifications по задачам, если находили проблемы в условии. Бывали и rejudges, хотя редко. Обращу внимание, что делать rejudge в Codeforces правилах значительно сложнее, чем в ICPC из-за блокировок задач, взломов и т.п.

            А над публикацией тестов мы в самом деле работаем, я думаю, что в ближайшем будущем можно ждать новостей :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Полностью соглашусь с it4.kp.
        Даже при верном решении могут возникать проблемы, такие как тут. А подобные проблемы иногда бывает очень сложно отловить без теста.
13 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

can anyone help me?!

my code gives the correct answer(-1)to the test case below:

1

5

i couldn't find my mistake,its good to put the test case 5 here.

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

can anyone help me?!

my code gives the correct answer(-1)to the test case below:

1

5

i couldn't find my mistake,its good to put the test case 5 here.

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

    6
    1 1 1 2 3 3

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

      its right too!I'm really wondering !what's wrong with that!

      i have posted my code(bud it's a little unreadable!)you can check it your self...thanks


      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        The code you have posted doesn't work for test case
        1
        5

        it gives
        0
        1

        debugging it is easy to see that
        num[0] is 0,

        Then you have
        for(int i=0;i<n;i++) // which only enters when i is 0, since n is 1.
        The inner loop is
        for(int k=0;k<num[i];k++) // since num[0] is 0, it doesn't enter

        It now breaks out of the outer loop and tries to print the permutations. It never even has a chance to print -1.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится
А можно 4-ый к задаче E?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Там прикол в том что если у него ничего не осталось, но что-то вырастет , то он не умер.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      О_о фак.. неужели и правда... я делал как раз что если его гасят, то уже ничего не вырастает.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Не... видимо это что то другое с моим кодом. Вроде подправил, всё равно ва4.

      <cry>Хочу тест!!!!!</cry>

  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    1 0 1
    1
    0 1
    1
    0 0
13 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится
а можно тест 9 к задаче  h "Черное и белое"?
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Можно 25 тест к задаче С?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    76
    342 684 1027 1369 1711 2054 2396 2738 3081 3423 3765 4108 4450 4792 5135 5477 5819 6162 6504 6846 7189 7531 7873 8216 8558 8900 9243 9585 9927 10270 10612 10954 11297 11639 11981 12324 12666 13009 13351 13693 14036 14378 14720 15063 15405 15747 16090 16432 16774 17117 17459 17801 18144 18486 18828 19171 19513 19855 20198 20540 20882 21225 21567 21909 22252 22594 22936 23279 23621 23963 24306 24648 24991 25333 25675 26018

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

У меня в рейтинге по "Школьная индивидуальная олимпиада #1 (ЗКШ 2010/11) - Codeforces Beta Round #38 (ACM-ICPC Rules)" написано, что я занял нулевое место... баг

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can someone help me check whats wrong with my E? I failed testcase 25 :(

http://pastebin.com/VWkUw2Qj
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In D, any possible permutation works? Like
6
1 1 1 2 2 3

Is the solution,
3 2 1 1 2 1

Is this a correct solution?

In case this might be just a coincidence, This is the algorithm I applied;

using a counting sort, count the instances of each number while also storing the numbers in an array. Then, reading the numbers in the array one by one and simply printing its count and then reducing its count by 1.

http://codepad.org/GHUzcb2v this is the code if someone wants to go through it to understand what I have done.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    The solution you give for your test is correct. The description of your algorithm seems to be correct too, but you should be careful with cases when the answer is -1, i.e. no partition exist.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I have simply checked that  for i, j such that i>j then count(i)<=count(j)

      If that is right then perhaps i made a mistake with my limits or something.
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Прошу прощения, а когда будут результаты олимпиады ЗКШ?
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
What is the test 3 for F?And what is the output for the testcase
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ура, я капитан :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всё-таки есть, и не мало, люди с синим рейтингом стоящие выше жёлтых в рейтинге.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Кодфорс заглючило о_0:)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      8 месяцев назад, #
         0 
      Контест был проведен 1-го апреля, за несколько часов до отправления в Казань. На этом контесте были немного изменены правила начисления баллов (я об этом писал). Короче, вкрался какой-то баг. Я только сегодня вернулся в Саратов, в ближайшее время исправлю.


      Может опять что-то меняется? Михаил Расихович вроде бы сейчас в Саратове...
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        попробуй нажми на красный/зелёный треугольник ;)

        "нет такого комментария" - значит, это всё фальсификация :D (вспомнил теорию всеобщего заговора, acm-массоны атакуют)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Блин.. не надо так комменты копировать.. я минуты две не мог понять что творится с CF О_о
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hi, are (Div 2) contests only for users in division 2? How do I know what division I'm in?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    If you are green or grey you are in Div 2, otherwise you are in Div 1.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    corporals and recruits are in div2, you are in div1 but you can also take part in competition (your rating would't change)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The judging system is down?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is an O(n^3) algorithm fast enough for G?
n is the number of planets.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Surely it is not. N ~ 200k, so O(NlogN) is required.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Wouldn't all-pairs shortest path algorithm be the way to go here?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        It is a solution but not fast enough here. Since our graph here is a tree with one added edge, there exist some more efficient algorithms.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
hi.
problem B,what is it,answer?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    For B you need to do some pre-processing and calculate the sum of all elements in the square (0-i)*(0-j) for every i,j. This can be done in linear time as you read in the matrix. s(i,j)=s(i-1, j) + s(i, j-1) - s(i, j) + a[i][j].

    Then you iterate over the entire matrix and calculate the sum in the small rectangle which can now be done in O(1) using the above matrix.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    By the way, here passed a bruteforce like this in accordance with the limitations.
13 лет назад, # |
Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится
Похоже планку не только для Короткевича надо вытягивать но еще и для вот этого человека.

13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Да достаточно просто сделать планку динамичной. Что если какой-то мазохист войдет в рейтинг меньше 100...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Будьте добры 8-й тест задачи С ?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got wrong answer in case no.7 ,,,problem - E -....plz any help

[code]

#include <string.h>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <map>
#include <set>
#include <sstream>

using namespace std;
#define all(c) c.begin(),c.end()
#define rep_(i,n) for(i=n-1;i>=0;i--)
#define rep(i,n) for(i=0;i<n;i++)
#define forr(i,a,b) for(i=a;i<=b;i++)
#define forr_(i,a,b) for(i=a;i>=b;i--)
#define min(a,b) ( a>b? b : a )
#define max(a,b) ( a>b? a : b )
#define sz size()
#define pb(a) push_back(a)
#define mset(a,v) memset(a,v,sizeof(a))

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef map<int,int> mi;
typedef vi::iterator it;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef pair<string,int> psi;
typedef vector<psi> vpsi;
typedef queue<int> qi;
typedef queue<pii> qpii;
typedef unsigned long long ubig;
typedef long long big;
typedef long double bigd;
template<class T> string tos(T x){stringstream ss; ss<<x; return ss.str();}
int Draw,Ivan,Zmey;
vpii v1,v2;
int i,h,t,r,m,n;
class Substitute
{
public:

};
void solve()
{
queue<pair<pair<int,int>,int> > q;
bool vis[1000][1000];
mset(vis,0);
pair<pair<int,int>,int> start(pair<int,int>(h,t),0),cur;
q.push(start);
int cc,ch,ct;
while(!q.empty())
{
cur=q.front();
cc=cur.second;
ch=cur.first.first;
ct=cur.first.second;
q.pop();
if(vis[ch][ct])
{
Draw=true;
}
else if(ch+ct>r)
{
Zmey=cc;
}
else if(!ch && !ct)
{
Ivan=cc;
return;
}
else
{
vis[ch][ct]=true;
int k,l;
rep( k , min(n,ch) )q.push(pair<pair<int,int>,int>(pair<int,int>(ch-(k+1)+v1[k].first,ct+v1[k].second),cc+1));
rep( l , min(m,ct) )q.push(pair<pair<int,int>,int>(pair<int,int>(ch+v2[l].first,ct-(l+1)+v2[l].second),cc+1));
}
}
}
int main()
{
cin>>h>>t>>r>>n;
v1.resize(n);
rep(i,n)cin>>v1[i].first>>v1[i].second;
cin>>m;
v2.resize(m);
rep(i,m)cin>>v2[i].first>>v2[i].second;
solve();
if(Ivan)cout<<"Ivan\n"<<Ivan<<endl;
else if(Draw)cout<<"Draw\n";
else cout<<"Zmey\n"<<Zmey<<endl;
return 0;
}

[/code]

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I don't know exactly what your algorithm is doing, but for example your cycle detection works wrong. You definitely can't solve this problem with single bfs.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      why do u think my cycle detection is wrong?  and what do u mean by "single bfs"?

      iam using bfs
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Consider such an example of normal graph (vertices are numbers)
        1->2
        1->3
        3->4
        4->2
        Your algorithm would mark 1, 2, 3 as visited than it would process 4 and find edge to visited node 2, but in fact there is no cycle in this graph. Also this bfs is strange, because each vertex has a chance to be several times in queue.
        By "single bfs" I meant that standard approach uses bfs and dfs, however I know that somebody solved this problem using two bfses. I think it can't be solved with just one bfs (I can be wrong, because maybe second approach described in tutorial could be done by single bfs, I don't know).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It's better to post your code in one of the services like codepad.org
    Please, edit your post.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there anyone know the test 6 for Problem C?thx

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А можно на 12 тест задачи Е поглядеть? Вроде написал решение совпадающее с референсным.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно так же 23й тест по задаче E?
Если тест велик, то его можно кинуть сюда. :)

Заранее спасибо!
13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
Hope there are no mistakes. :)

B: 5?
C: 8, 9, 17, 19, 25
D: 4, 9, 11
E: 4, 11, 25, 46
H: 9
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
For my solution of problem D - Permutations, it says presentation error on test 4 but I tried many cases on the compiler on my system and am getting it right. Please take a look at the code : http://www.ideone.com/FBceJ
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    On the test case 4 your program outputs just one number 1, white the correct answer contains two 1's.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
@natalia: Can you give that test case input?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
@natalia: The first 1 is the input n. Then the second line contains 1 number (i.e. 1) so the answer my code gives is 1. The number of values output should be equal to the value of n right? So my answer is correct I feel..what do you think is wrong?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    First number in the output must be the number of permutations. Then there must be a line which desribes a partition of the given sequence for several permutation. So the correct answer is
    1
    1

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Oh ok, sorry. My mistake.