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

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

Привет всем!

Раунд Codeforces #165 начнётся сегодня в 19:30 по Московскому времени, и будет проведён в обоих дивизионах. После долгого двухнедельного перерыва это первый раунд для участников Div I. :)

В этот раз задачи подготовили я, Евгений Вихров (gen), и Кришьянис Прусис (cfk). Кроме совместного участия в ACM ICPC в этом году, мы также коллеги по проекту с множеством алгоритмических задач. Некоторые задачи раунда появились именно во время работы над этим проектом.

Во время контеста вы познакомитесь с легендарным героем Эмускальдом множества талантов и поможете воплотить в жизнь его гениальные замыслы. Задачи покрывают большое количество алгоритмических идей, поэтому, как всегда, мы надеемся, что каждый найдёт себе задачу по вкусу.

Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод условий, а также Михаилу Мирзаянову (MikeMirzayanov) за великолепную платформу создания контестов на Codeforces — Polygon.

Мы желаем всем интересного раунда!

UPD1: Разбалловка задач:

DivII: 500 1500 1500 2000 2500

DivI: 500 1000 1500 2000 2500

UPD2: Поздравляем победителей!

Div I

  1. PavelKunyavskiy
  2. Egor
  3. tourist
  4. rng_58
  5. tomasz.kociumaka

Div II

  1. woxihuanni
  2. mnbvmar
  3. QLSpirit_011
  4. PraveenDhinwa
  5. leviathan

UPD3: Появился разбор.

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

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

Нормальный был вопрос....

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

I love contests !!

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

Эх, чувствую контест будет интересным, жалко пропускать :(

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

Remarkably the two of our problem setters Evgeny Vihrov (gen), and Krisjanis Prusis (cfk), have exactly the same rating, besides being project mates.

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

Всем удачи!!!

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

求轻虐>_<

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

why is the handle changing item removed???

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

Another rated contest for the div1 contestants after 2 rounds.

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

JUST HAVE A FUN!

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

По описанию контеста кажется что он будет довольно интересен. Надеюсь так и будет)

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

Ideas generated from project, I am pretty sure that problem statements will be long. :( .

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

What will be the point distribution ?

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

Это будет мой первый див-1 раунд, надеюсь не слиться в синие)

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

Высокого рейтинга!!!

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

After a little break, I'm going to write today's contest... Good Luck

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

Ух долгожданный кодефорс всем удачи!!!

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

Прошлая задача про треугольники обрадовала. Надеюсь и сегодня обрадуете.

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

"the first one after a long two-week break for Div I participants."

This touched the bottom of my heart...! :D

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

Интересная разбалловка Div II.

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

I haven't wrote contest almost 2 years

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

для див 2 задачи обещают быть интересными

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

Уже в сумме 3326 участников) Вот это рекорд!

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

WOW number of registered in Div1 reached 850

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

Что означает вердикт: "Ошибка исполнения"?

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

В очереди уже 3 минуты — не к добру...

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

is something wrong with the judge or this is normal??

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

This contest should be declared unrated as the server was down for a long time as well the verdicts came late :\

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

Тупой контест!

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

I hope it'll be declared unrated

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

Кто знает, как решалась C(div. 2)/A(div. 1)?

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

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

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

      Бинарный поиск не нужен, потому что в коробку размера M + 15, где M-максимальный размер коробки из инпута, гарантированно все влезет. Это так, потому что в коробку размера i помещается 22(i - j) коробок размера j.

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

      Даже лучше, хватает проверить только коробки от 2maxk + 1 до 2maxk + 16, так как количество их до 10^9. ;)

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

    Можно решить, используя логарифмы.

    for(int i=0;i<n;i++)
        {
        cin>>k>>a;
        
        long double cur=k + log(a)/log(4);
        if(a==1)
        cur++;
        if(cur>max)
        max=cur;
        }
        
        
        cout<<int(max+0.999999999)<<endl;
    
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

What is the notorious pretest 4 for problem A in div 1?

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

Прошу помочь найти ошибку в решении задачи C Div-2. Решение UPD: нашел ошибку

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

Насколько же хитро автор замаскировал наибольшую неубывающую подпоследовательность в В... А в целом задачи понравились.

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

Today I couldn't hack from Firefox (the popup window didn't move and "Hack" button was below the bottom of the computer screen).

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

Задача C. Не знаю, как народ в общем, а я не впер, что он обязательно должен создать коробку... Либо я тормоз, либо условие странное :( Скорее первое, но все равно обидно. Я думал, если все влезает, то крутяк. В общем решал другую задачу

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

    1) Ларец v можно положить в ларец u, если длина стороны ларца v строго меньше, чем длина стороны ларца u.
    2) Помогите ему найти наименьший волшебный ларец, в который можно поместить все его ларцы.

    Очевидно, что ларец, в который он положит все свои ларцы, должен быть больше наибольшего из ларцов.

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

Hey , i was getting badway 504 in last two minutes of contest. And in the last two minutes i was waiting to submit my solution to 3rd but couldnt do it due to that 504 error. Please Please please consider my solution for C now as i had completed it in time ,else it will be unfair .

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct logr {
       double k;
       double x;
} box[50];
bool key(const logr &a, const logr &b) { return (a.k < b.k); }
int main() {
    float min;
    int n;
    cin>>n;
    for (int i=0;i<n;i++) cin>>box[i].k>>box[i].x;
    sort(box,box+n,key);
    for (int i=0;i<n-1;i++) {
        if ((pow(2,box[i].k)*box[i].x*pow(2,box[i].k))>(pow(2,box[i+1].k)*box[i+1].x*pow(2,box[i+1].k))) {
           min=(pow(2,box[i].k)*pow(2,box[i].k)*box[i].x)-(pow(2,box[i+1].k)*pow(2,box[i+1].k)*box[i+1].x);
           min=ceil(min/(pow(2,box[i+1].k)*pow(2,box[i+1].k)));
           box[i].x=(pow(2,box[i+1].k)*pow(2,box[i+1].k)*box[i+1].x)/(pow(2,box[i].k)*pow(2,box[i].k));
           box[i+1].x+=min;
        }
    }
    min=pow(2,box[n-1].k)*ceil(box[n-1].x/2);
    min=ceil(log(min)/log(2));
    cout<<min<<endl;
}
»
13 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +10 Проголосовать: не нравится

I mean, seriously, are those statements supposed to explain the problem, or confuse it even more??

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

    Sorry, they were shorter in the beginning, but we had to explain some subtle things and they grew in size... :/

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

      I am not talking about length, I am talking about how much useful the information you put, was aiming make clearer the task itself. Let's mention for example the task Div2 B, the definitions of updated or not are so misleading.

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

      And this coordinates in Div1B ; /... I've read description 5 times to be sure that these coordinates are just a mislead :d... Not a funny joke, but pretty confusing :d

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

        Why do you think it is a joke? Determining what data do you need is an important part of solving a problem.

        Also, I think that all statements were rather clear and unambiguous. (Div2 at least)

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

        I can understand that can be frustrating... But there were reasons for coordinates:

        1. Just by looking at the sample, you can tell that one can replant a plant anywhere at real coordinate.
        2. The origin of the problem had coordinates also, so they were kept.
        3. It is often quite valuable to tell that some data is redundant, and is a good reminder to trust your reasoning.
        • »
          »
          »
          »
          »
          13 лет назад, скрыть # ^ |
           
          Проголосовать: нравится -37 Проголосовать: не нравится

          Anyone, who isn't a monkey, will immediately know that if you can replant them into any real coordinate (what was clearly stated in description), exact coordinates are redundant. Putting something like that in the description won't take any positive effect. It causes thoughts like "Either I am dumb or author thinks that I'm dumb". Reading the description few times took me more time than solving+coding :/

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

            That wasn't the intent. :D But I'll try to make short and clear statements in the future, this time it just was an experiment for us to write extended legends about one hero.

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

            So, in your opinion reading the task is not included in solving it. I would beg to differ. Understanding the statement is a first step in solving every task. Hence, if you rushed too fast or haven't done it well — sorry, there's no one to blame except you (except if the statement was way to unclear, but it's not the case here in my opinion). Well, I have seen quite a lot of tasks where some information doesn't matter — it's your task to decide what you need and what you don't. Some perfectly valid tasks could even be one-liners, where all you need to do is to understand the statement. Why not?

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

              You're all talking "determining which data is important" is a part of solving task. But in this case this was so obvious and it hasn't caused effect "Oh! I'm so smart, I figured out that this coordinates are not important! Such a nice result!" but "Probably I didn't read description carefully, because it would be too obvious if those coordinates really were redundant."

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

Несколько комментариев по поводу DIV-2:

  • Во-первых, как по мне, но задача B не самым лучшим образом переведена на русский язык...
  • Во-вторых, никак не пойму почему вот это решение С не правильно? (Сылка)
»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Почему валится поиск в ширину в С див1 ?

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

"...Некоторые задачи раунда появились именно во время работы над этим проектом." Всем желаю такой интересной работы:) Спасибо за классные задачи!

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

My solution for problem C wasn't rated. http://mirror.codeforces.com/contest/269/submission/3052470

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

Интересный раунд. Разбор задач будет?

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

    Из-за нехватки времени мы ещё не сделали, но завтра будет. Пока можно поломать голову над Е. :)

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

I think Test #12 in problem C is wrong, because "If there are several solutions you can print any of them."

Edit: Sorry guys i get it!.

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

What's the idea behind div1-B and div1-C?

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

I can't understand why the coordinates are given in problem div1 B

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

На дорешивании div2 C не проходит 15 тест, причем он запущенный у меня локально выдает правильный ответ. Моё решение (с++11): http://pastebin.com/CXxCDx9V Протокол тестирования: http://pastebin.com/8j5BV3q5

Запуская у себя получаю верный ответ 14. Компилировал clang++ и g++46 — всеравно 14, почему на сервере тестов получается 15?

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

Люди, объясните, плиз, почему решение 3051832 по задаче В прошло, несмотря на то, что в цикле там может быть обращение к -1 элементу массива и выход за его границы.

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

Hi. Does anyone have any idea how the code in below could work correct in my computer and get WA on pretest 2 on CF? I checked it with MS and GNU and they gave Compilation Error and WA on pretest 2 respectively. here's the code: 3060066 thanks.

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

Can anybody tell me what were the bugs in Div1 C, which weren't detected by pretests, what caused so many succesful hacks? I'm pretty curious about that.

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

link to editorial please?

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

thanks for nice problemset. I realized I shouldn't pass a round even if its writer is Purple.

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

Доброе утро. Подскажите, когда будет выложен разбор задач?

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

Testcases in Div2.C are not strong enough.

My code got AC, but fails on this test:

2
0 1
1000000000 1

link: http://mirror.codeforces.com/contest/270/submission/3062842

BTW, if youare interested why it fails look at this line: ll xarisxi = pow(4, 1.0*(V[i+1].first-V[i].first)); where I calculate 4 to the power of the difference between two quantities of boxes.

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

Congratulations to kelvin to be the first participant who has successfully upsolved the hard problem 269E - Теория струн: 3062253!

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

    Thank you for the congrats and for preparing a great contest! During the contest, I was very happy to find out that I know how to solve the hard problem, but equally sad when I (after 30 min or so) find out I probably cannot finish it in time :p

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

Div 2 was really good and amusing contest , questions were just so cool , i loved solving them , thanks gen :)