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

Автор matrix, 12 лет назад, перевод, По-русски

Всем привет!

Завтра в 19:30 MSK состоится Codeforces Round #240.

Это наш первый раунд на Codeforces и мы надеемся, что он вам понравится. Задачи были подготовлены авторами: Amir Keivan Mohtashami (matrix), Farbod Yadegarian (FarbodY) и Gerald Agapov (Gerald).

Традиционно благодарю MikeMirzayanov за системы Polygon и Codeforces, а также Maria Belova (Delinur) за перевод задач.

Желаем вам хорошего и интересного раунда.

Удачи!

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

Распределение баллов:

div1: 500 — 1000 — 1500 — 1500 — 2500

div2: 500 — 1000 — 1500 — 2000 — 2500 (стандарт)

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

Div 1:

  1. fqw

  2. sankear (Единственный, кто решил задачу E во время контеста)

  3. Egor

  4. qwerty787788

  5. hos.lyric

Div 2:

  1. jzzhu

  2. SJTU_WengJian

  3. alcot

  4. LoveEvita

  5. huyifei

  6. NiuYiqiang

Статистика по раунду, подготовленная DmitriyH, находится здесь. Английский разбор можно прочитать здесь.

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

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

2 Iranian problem setters , that sounds great !

I wish it will be different and special round :)

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

I think there will be a matrix problem :)

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

is it only me that has received the announcement first time in Russian despite primary Language being English in codeforces?

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

I wish you all good luck and increase the rating

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

Do you know dibil power Ha ? this is 1000th dibil :D HURRAY DIBILS

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

i don't know how, but i'm registered twice for this contest!
EDIT: sorry the image i initially posted was too large, so here is link to image

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

Что то в последнее время с началом раунда какие то очень странные вещи происходят. Иногда высвечивает что осталось на 4 часа больше чем реально + при переходе на страницу с соревнованиями время начала стоит 23:30, потом обновляешь и все нормально.

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

Wish both Iranian problem setters, Amir Keivan and Farbod, Gold medals in this year`s INOI. Good luck.

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

Is the contest time 19:30 or 23:30?

Currently (at least for me), the time on the contest list is 23:30 and the counter shows that the contest starts in 6 hours...

Screenshot: http://koti.mbnet.fi/pllk/cf.png

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

Delayed?

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

hey, has the round been postponed by 10 minutes? i suddenly see 00:11:42 in the countdown!

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

Is the contest delayed ?

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

Let's hope it is not a problem like what happened in TCO yesterday.

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

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

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

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

Is that server downtime ? I saw "Codeforces is temporary unavailable" page several times just before some minutes.

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

wish a nice contest

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

can we know the reason for delay?

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

last 30 seconds~~~~

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

In Problem B,I can't see the picture about "how much dollar a worker can get if he returns w tokens". Then what should I do?

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

LOL I think this is the first round I've encountered on CF that the English statement is correct instead of the Russian one.

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

In problem B the image was so bad i made one wrong submission before asking a question to clarify that the expression was floor (w*a)/b , i had earlier thought it to be floor((w-a)/b)

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

Как решалась Б (див 2)?

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

    вывести (x_i * a % b ) / a;

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

    Для каждого запроса одни и те же действия. Сначала посчитаем сколько денег работник получит если отдаст все жетоны, а потом бинарным поиском подберем такое минимальное количество жетонов, что если работник сдаст их, то получит столько же, сколько если сдаст все жетоны.Ответом на очередной запрос будет разница между выданным количеством жетоном и найденным значением.

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

      это все равно что оптимизировать линейный поиск результата деления.

      // cout << a/2
      int a = 6; int b = 1; 
      while( b <= a && 2*b < a ) ++b;
      cout << b;
      

      Я тоже подобное иногда делаю, когда формулы лень придумывать, ТЛ и не пахнет, а условие легко сформулировать) Но тут все же лучше было считать.

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

Why my solytion on problem C-div 2 gets TLE?


#include<iostream> #include<cstdio> using namespace std; int main() { int n,k;scanf("%ld%ld",&n,&k); int d=0; if(n&1){n--;d=1;} if(n>>1 > k){printf("-1\n");return 0;} else { int bn=n/2; printf("%ld %ld ",(k-bn+1),2*(k-bn+1)); bn--; int j=2*(k-bn+1)+1; while(bn--) { printf("%ld %ld ",j,j+1);j+=2 } } if(d==1) cout<<1000000000-1<<"\n"; return 0; }
»
12 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Nice statements... Easy to understand... :)

Hope to see you again as author.... :)

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

nice contest...

made stupid mistake in B which led to me wasting too much time...

hope to learn a lot from the editorials... :)

thank you to the problem setters!

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

Pretest 4 is pretty strong.

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

Annoying issue with printf: As suggested in the problem statement, I tried using printf to output the numbers for problem C, but I could not submit because of the warning. In the end I had to submit the cout version, which I am afraid might time out.

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

Liked the problems and the statements specifically, though I couldn't solve Div2 E, lol.

Would be really great if some corner and/or extreme cases were excluded from the pretests.

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

Ну блин, что это такое? Второй контест подряд Div.1 A какая-то стрёмная жадность, а Div.1 B — элементарная динамика, которую решает больше человек, чем А. Я не могу понять отношения авторов контестов к сложности задач(

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

    Скажите решение задачи А.

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

      Я решал так — будем заполнять всё парами, у которых gcd равен единице, это числа вида (x;x + 1). А первой паре сделаем gcd равным k - n / 2 + 1, чтобы в сумме было k. Ну и вывести  - 1, если n / 2 > k и отдельно рассмотреть случай n =  = 0.

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

      Жадность рулит. Первая пара — подбирается большое число и большое число*2 так, чтобы (k-большое число) = количеству оставшихся пар. Каждая оставшаяся пара — любые два взаимопростые числа. можно, например, просто простые числа перечислять. И надо не забыть про разные "особенные" случаи, типа неченого количества чисел, или когда число требуется только одно.

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

    А я думал что в B-шке нужно заранее для каждого числа предпосчитать его делители и забить в вектора, но раз проходит O(sqrt(n)*n^2), тогда я тоже не могу понять отношения авторов.

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

who can explain 4th pretest on B question(div2)?

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

C was very nice. I've just finished it now. Big + for the authors. Very nice problems !

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

Nice problems, I liked them.

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

Pretests were too strong. I don't complain though :)

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

Загружать Windows 8.1 за 2.5 часа до начала контеста — плохая примета.

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

Can anybody help me guess why I have WA on the 7th test from Div1 A ? :)

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

Ну и тестирование...

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

I thought it's (w — a)/b for the whole contest and couldn't solve it. I noticed it's a multiplication after viewing some solutions :/

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

why is system testing taking so long today?!

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

Any hint for task D , DIV2?

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

Problem D Div 2 (B Div 1): I should learn a faster language. Even O(KN) on Python still fails the time limit (or I analyzed the run time incorrectly). Most people I asked had only but used C++ or Java or something fast. :(

Is there anyone that tried to solve it in Python or some "slow" language and got accepted?

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

It feels like System Testing Became slow........

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

When can we see our new rates?

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

In (Div 2)problem B there was a huge confusion between — and . sign in the equation w.a/b

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

Damn. I solved C in O(n22n) (plus O(n) per query), but my code wasn't fast enough during the contest. I only managed to optimize it well enough to pass around 1 minute after the contest.

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

Посылка во время соревнования выдаёт неверный ответ на 4 тест http://mirror.codeforces.com/contest/415/submission/6287526 Стоило сменить тип с longint на int64 (сделал после соревнования): http://mirror.codeforces.com/contest/415/submission/6288201

Из-за чего в первом случае выдаёт неверный ответ?

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

can anyone tell me what is the complexity of my solution to Div2 D problem ? at first i thought it n^2*k because of the loop in the function , i know that loop will not be completed at all , but it loops to n in worst case , when i tried the largest case it didn't take too much time , so i submitted it and it got AC , but i want to know the actual complexity of this solution ? My solution : http://mirror.codeforces.com/contest/415/submission/6284352

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

норм пацанам рейтинг не оч подняли

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

Waiting for the editorial for div1 C and E... I have no idea for these two ....

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

У меня в комнате никто не взламывал, и незавалил ни одного систеста.

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

Were constraints in C that big (when O(n log n) (ofc n:=2^n) is expected constraints on CF are rarely higher than 200k) to make O(n log^2 n) exceed time limit? I have written solution in that complexity (I'm so incautious, I thought that this is O(n log n), when this was simply O(n log^2 n) xd) and I think noone will get hurt if those solutions will fit in time limit :P. In my computer on maxtest O(n log n) works 6s while O(n log^2 n) works 7s :P (but in CF difference is significantly bigger). But I won't whine much, I should've think a second before coding :d.

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

Nice problems, B from div1 can be done better in O( n log k * log^2(n)) with matrix multiplication http://mirror.codeforces.com/contest/414/submission/6290524

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

I don't know the reason that after system test, my problem A and B are "skipped"!!! (and A,B problems, I just submit one time) Could admin give me a reason??

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

My Problem B couldn't pass the pretest 4 ... what's the wrong with this? Can anyone faced the same problem?

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

How to solve the problem D in div1

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

Is the system still pending on testing? I am not able to submit solutions for practice mode.