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

Автор Nedy88, 14 лет назад, перевод, По-русски
Привет всем,

Codeforces Beta Round #26 состоится в понедельник, 16 августа, в 19:00 по московскому времени. Раунд будет проведен в формате Codeforces, и если все пройдет хорошо, он будет рейтинговым. Авторы задач - Артем Рахов и я. Спасибо Михаилу Мирзаянову и Дмитрию Матову за помощь в подготовке раунда. Так же спасибо Юлии Сатушиной за перевод задач на русский язык.

Желаю удачи, увидимся на раунде!

UPD: Контест закончился, всем спасибо за участие.

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какой див?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Оба
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что за девушки у тебя на авах постоянно?
    Это твои подружки или подружки, о которых ты только мечтаешь?:_)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Две девушки мои были на авках, а остальные просто.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А текущая кто?
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Google Images по запросу "Asian student girls" :)
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А Яндекс мне 14-ым ответом выдал http://images.yandex.ru/yandsearch?p=13&ed=1&text=asian%20student%20girls&spsite=fake-042-3564424.ru&img_url=www.badassoftheweek.com%2Fbruce_lee.jpg&rpt=simage - мужика какого-то, вроде из фильмов:))

            Пойду-ка я поищу Asian naked girls, там вероятность больше))
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Наконец-то формат Codeforces!!
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А мне не нравится.
    Пока думаешь о тактике, отвлекаешься от решения задач.
    TopCoder в этом смысле приятнее, но, конечно, нет смысла копировать идею - нужно придумать свое.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
А в перспективе планируется все раунды типа Codeforces format? А то старый формат тоже было очень интересно решать.
14 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится
Лично меня заинтересовала последняя фраза "Увидимся на раунде!". Знаю что предираюсь, но КАК можно УВИДИТСЯ на раунде, а если даже можно, то смысл?
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Hey , if u don't mind can i ask one personal question?

Were u guys working on the Testing Process or Development of Codeforces Format round these days? Or it was just bcz u are busy with ur works.?

I am eager to know bcz i have with been the codeforces since its 3rd round.


Thanks
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всем удачи, ребята =) Я думаю этот контест будет весьма и весьма интересным :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Формат конечно хороший, но по-моему самая большая проблема в том, что далеко не у всех задач можно разбить тесты на претесты и все остальные, т. е. задачи подходят только довольно специфические.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Думаю надо давать примеры которые побольше раскрывали подводные камни задач, так как 5 задач а времени 2 часа, снижает бдительность
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Не могу открыть решение в Round21 как для взлома. Это связанно с тем что контест закончился?

Скажите пожалуйста как можно проверить flash-player на то что он будет работать на контесте.

И еще если можно напомните как открыть решение для взлома?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Контест завершен,как по мне ламать решение невозможно, поскольку решение проверяются на полном наборе тестов.

    а открывать код для взлома ,можно просто нажав на id  отправки, как дальше сам поймешь когда откроешь.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Логично чтобы взлом можно было делать из таблицы с резами. Ибо искать в списке сабмитов это долго.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Так там так и есть
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        нет,нет....я ошибся..сори...ты прав. Надо нажать в той клетке что отвечает данной задаче, данного учаскина.
        ИЗВИНЯЮСЬ :(
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всем удачи!!
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Лагает... Удалите мне вторую посылку по задаче C если можно. Почему то две посылки сразу отправились...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И мне по B, как оказалось, двойное нажатие кнопки делает два независимых сабмита.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
даа, надо привыкнуть к такому формату. По сути дела это топкодер но не не аплете. Когда был взлом? 10 мин до окончания? я прозевал
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Минут за 5 до конца я не смог загрузить таблицу моей комнаты. Это продожилось до конца контеста. Очень обидно, ведь именно в это время я хотел попытаться взламывать решения соперников.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Точно то же и у меня было. Успел взломать только один раз (кстати, приятно :) ).
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Аналогично. Только, по-моему раньше, где-то за 10 минут до конца и таблицу результатов тоже.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Сейчас все начнут просить тесты (я бы тоже попросил); может, выложить где-нибудь их для всеобщего осмотрения?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Объясните пожалуйста, почему этот  (задача B) код получает ТЛЕ на 15 тест? неужели в 5 секунд не входит? Линейный же алгоритм!
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не знаю, как стек в java а стек в C++ кажется довольно медленно ест 100000 итераций. Но это только гипотеза.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Блин... сомневаюсь конечно, что так тормозит... хотя... проверить бы как-то.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Сделай стек на массиве. Недолго же пишется...
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Смотрю я на твой код и думаю, что стек можно заменить счетчиком i с операциями +1 -1 и сравнение с нулем.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Может я конечно чего в вашем коде не понял, но что-то мне кажется, что у вас квадратичное решение (точнее, квадратичное чтение входных данных): вы при чтении много-много раз делаете s += c, но string неизменяемый, так что это может быть довольно долго.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вот коварный код :). А я увидел считывание readline и подумал, что тут все норм.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    С одной стороны ты можешь нагенерить тест из 1000000 открывающих скобок и посмотреть чё получится. А с другой в твоём решении стек вообще не нужен. Нужен только его размер, потому что ты в стек кладёшь только открывающие скобки.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Дааа... Как же обидно когда не хватает 5 минут на отладку Е, а потом она с одним исправлением заходит на дорешивании.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Дааа. Та же тема с задачей С. На Е я там не понял: просто Y инкремент делать надо? Локальные переменные какую погоду делают?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      За первую операцию в теле цикла поток запоминает значение. За вторую присваивает его глобальной переменной.
      Т.е. после отработки в следующем порядке: 1 2 2 2 2 2 2 1 значение у увеличится только на 1, т.к. первый поток запомнил у1=0, а потом присвоил: у = у1+1 = 1.
      Ну в общих чертах здесь: http://en.wikipedia.org/wiki/Race_condition#Computing
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
можна тест 8 в финальном тестировании?
14 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Топ4 в рейтинге жжот :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I asked a question, but I think I more or less understand the problem. Each attempt costs 50 points. After I made successful one, next unsuccessful attempts costs nothing, but what happens after I made next successful one? Will all attempts before the last successful be counted as -50?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    I believe the answer to that will be "Yes".  See Codeforces format description 8:
    You may resubmit the solution at any moment, but it may reduce your score. It happens if resubmission is successful (i.e. passes all the pretests + previous hacking attempts). In this case, the previous successful attempt would be considered as a reason for penalty (see item 3).


14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Can someone throw some light on how to work out D. Tickets?  I see from ACed solution that the formula is 1.0 - (n! m!)/((m-k-1)! (n+k+1)!).  But, why?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    It can be solved similar to calculating Catalan numbers by method of refelection. (see wikipedia)
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Oh!
I really loved it
when is the next round?
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Буду очень признателен тому, кто объяснит, каким образом получается формула в задаче D.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Это по сути обобщение одного из способов получения формулы для чисел Каталана. Посмотреть это можно например в википедии: http://en.wikipedia.org/wiki/Andr%C3%A9%27s_reflection_method и http://en.wikipedia.org/wiki/Catalan_number (раздел Second Proof)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
can any one explain how to solve problem C? i tried to solve it using brute force appraoch but it gives me time limit?can any one explain the solution and thanks in advance.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Split the problem in cases:
    n = number of rows
    m = number of cols

    * n and m are odd -> No solution
    * n is odd -> Fill the first row using pieces of type a -> now, n and m are even
    * m is odd -> Fill the first column using pieces of type b -> now, n and m are even
    * n and m are even -> Fill the matrix using blocks of size 2 * 2 (two pieces of type a, two pieces of type b or one piece of type c). If you are in the cell (i, j) you have to check the cells (i - 1, j), (i - 1, j + 1), (i, j - 1), (i + 1, j - 1) in order to calculate the chars you can use for the current block (remember that if you're using a block of two pieces of type a or b, you will have to use 2 different chars), now use one available 2x2 block  (if there is no available block -> No solution), update the pieces and go for the next non-filled cell.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Thanks so much. i solved it.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Interesting.  Why does this approach always gives a solution whenever possible?
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        • The first case is trivial: Pieces with even area and the total area is odd.
        • The second case: n is odd. We can't fill any column using only pieces of 2 x 1 and 2 x 2, because, at end, always, there will be 1 non-filled cell. So, in any moment we will need a 1 x 2 piece, then, used in the first row and fill all cells in that row (one 1 x 2 piece fill two cells, and the number of cols is even) if we have more than m / 2 pieces.
        • The third case: almost same explanation that the second case.
        [In both cases (second and third) we get a matrix where m and n are even.]
        • The last case: n and m are even. n * m = (2 * n') * (2 * m') = 4 * n' * m' (for n', m' >= 0). The area of the matrix is multiple of 4, then, we can filled it using pieces of area 4 (2 x 2, 2 x (1 x 2) or 2 x (2 x 1)) if we have enough (a / 2 + b / 2 + c >= (m * n) / 4).
        adamax wrote a tutorial about beta round 26. You can find it here -> http://codeforces.me/blog/entry/610
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anybody give me test case 5 of problem E?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
дайте 8 тест к задаче С плиз
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я вот пропустил этот раунд, поэтому не знаю и задаю глупый вопрос. Правильно ведь я понимаю, что копипастить чужое решение, чтобы проверить, упадёт оно на твоём тесте или нет, таки нельзя?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Там есть картинка с решением и сбоку самодельная полоса прокрутки. В целом выглядит как в TopCoder апплете - не выделяется, не копируется, не вставляется. Про это был вопрос?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а чем не вариант сделать принт-скрин, а потом распознать??
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Принтскринить надо в несколько заходов, потом соединять. В общем-то ты просто испортишь себе все удовольствие от участия и получишь меньше пользы. При этом я не вижу, чтоб ты особенно выиграл от такого читерства.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          да я тоже =) .. просто захотелось спросить, давно уже такая идея в голове была.. ну насчёт нескольких заходов - думаю 2-3 хватит
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А вот у меня 200 строк только шаблона. И без шаблона ничего не работает. В любом случае, это было сделано, чтобы втупую не читерилось. Если бы можно было бы копипастить - был бы контест на копипаст. А так сразу видно что надо методом пристального взгляда искать баги. После этого у тебя остается возможность читерить, но она тебе во вред. Такая вот политика...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can Anyone explain me the solution of problem C? I tried it but didn't get the correct approach... :(
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hint on test 9? Must have an implementation bug.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
во время контеста я случайно открыл свой код к одной задаче. Мне показалось что ето тоже можно взламывать(хотя я ето естественно не делал), ето действительно так ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I got AC to. But still I think there is a problem I don't understand.
In the problem example, the output
aabb
aabb
bbaa
bbaa
is correct. How come? There must be smth else that I'm not taking into consideration.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I've thought about it some more and I found that by checking only N,S,W,E neighbours there is a testcacse I would fail(also taking into consideration that by checking a 5*5 square I would AC).
The test is 2 4 2 2 0. So I need to check SW also. Actually with a little bit more attention I concluded that I only need to check N, W neighbours when I place a or c type boards and when I place b boards I need to check N,W, SW neighbours.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
"...Авторы задач - Артем Рахов и я..."
"...Так же спасибо Юлии Сатушиной за перевод задач на русский язык..."

что в себя включает авторство на задачу? потому как если задачи надо было переводить значит у них есть другой источник...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Задачи даются на двух языках. Автор пишет задачу на одном языке, переводчик переводит на другой. Зайди в любую задачу и переключи интерфейс на английский и увидишь, что будет
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      не обратил внимание что один из авторов из Болгарии...
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Когда ожидать №27 контест?
Очень уж нравятся они в новом формате :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Me again, sorry for overposting. Could you help me with problem E's  Presentation Error on test 35?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Bug Found. Problem ACed. Thank you all.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Why WA on test3?
Problem B.
#include<iostream>
#include<string>
using namespace std;
string a;
long int k(long int );
int main(){
cin>>a;
long int j=a.length(),b,d=0,g=0;
long int c=0;
for(long int i=0;i<j-1;i++)
{
         b=k(i);
         if(b>1)
         i+=b-1;
         if(b!=0)
         {
         d=d+b;
         }
         else
         {
         d=0;
         }
         if(d>g)
         g=d;
}
cout<<g<<endl;
cin>>g;
return 0;
}
long int k(long int h)
{
    if(a[h]==')')
    return 0;
    long int s=0,f=0,n=0,j;
    j=a.length();
    for(long int i=h;i<j;i++)
    {
             if(a[i]=='(')
             s++;
             if(a[i]==')')
             f++;
             if(f==s)
             {
             n=i-h;
             return n+1;
             }
    }
    return n;
}
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I wrote the following for A. prime numbers but i am getting WA on test case 11. Can anybody help?


#include<map>
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>

using namespace std;


int main()
{
bool check[70];
for(int i=0;i<70;i++)
check[i] = false;
check[0] = 1;
check[1] = 1;
vector<int> primes;
for(int i=0;i*i<3000;i++)
{
if(check[i]==0)
{
primes.push_back(i);
for(int j=i*i;j*j<3000;j+=i)
check[j] = true;
}
}
int n;

cin>>n;
int last =0;

for(int i=2;i<=n;i++)
{
int count =0;
for(int j=0;j<primes.size();j++)
{
if(primes[j]*2>i)
break;
else if(i%primes[j]==0)
count++;
}
if(count==2)
last++;
}
cout<<last<<endl;
}






  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    You can't simply ignore primes larger than 70. For example, the number 142 is almost prime, but according to your code it's not.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
when will be the next contest?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Why RTE???
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<vector>
using namespace std;

#define max 3500
bool prime[max];
void sieve()
{
int i, j;

for(i=1;i<=max;i++)prime[i]=1;

for(i=2;i<sqrt(max);)
{
for(j=i+i;j<=max;j+=i)
prime[j]=0;
i++;
for(;!prime[i];i++);
}
}

int main(){

sieve();
long low, high;low=1;
while(cin>>high){int i,j;
vector<long>count(max,0);long cou=0;

for( i=low;i<=high;i++)
{
if(!prime[i])
for(j=low;j<=high;j++)if(prime[j])if(i%j==0)count[i]++;
}
for(i=low;i<=high;i++)if(count[i]==3)cou++;
cout<<cou<<endl;
}
return 0;}
please give me some case so that i can understand