Codeforces Round #240

11 лет назад, # |

+74

I think there will be a matrix problem :)

→ Ответить

DylanJiang

11 лет назад, # ^ |

-12

What makes you so positive?

→ Ответить

caustique

11 лет назад, # ^ |

Nickname of the topic starter.

→ Ответить

PraveenDhinwa

11 лет назад, # |

← Rev. 2 →

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

→ Ответить

divij_nsit

11 лет назад, # ^ |

-6

I received the announcement in English

→ Ответить

DylanJiang

11 лет назад, # ^ |

-13

In fact,Everyone has been informed

→ Ответить

hball1st

11 лет назад, # |

← Rev. 2 →

I wish you all good luck and increase the rating

→ Ответить

11 лет назад, # |

-44

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

→ Ответить

11 лет назад, # ^ |

← Rev. 4 →

-22

oh no -44 HELP DIBILS

→ Ответить

11 лет назад, # |

← 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

→ Ответить

11 лет назад, # ^ |

+28

Thanks. Nothing dangerous. I'll fix it before the round.

→ Ответить

11 лет назад, # ^ |

+35

cool thanks. but plz make sure to remove only one (not both) :P

→ Ответить

11 лет назад, # ^ |

i think the issue is fixed now. thanks for ur help! :)

→ Ответить

Killever

11 лет назад, # ^ |

Same here

→ Ответить

I_love_Coding

11 лет назад, # ^ |

+36

May be the rating will increase or decrease twice ;)

→ Ответить

alpq654321

11 лет назад, # ^ |

I love coding too. :)

→ Ответить

11 лет назад, # ^ |

i wish it had! :P

→ Ответить

lisang

11 лет назад, # |

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

→ Ответить

11 лет назад, # ^ |

можно скриншот?

→ Ответить

Igorjan94

11 лет назад, # ^ |

← Rev. 2 →

в правке скриншот

→ Ответить

11 лет назад, # ^ |

А какое в этот момент "Время на сервере" (см. внизу в футере)?

→ Ответить

11 лет назад, # ^ |

И что там в скобках, p1?

→ Ответить

Igorjan94

11 лет назад, # ^ |

уже обновил, пока все в порядке) как будет наблюдаться, посмотрю

сейчас время правильное, в скобках р1

→ Ответить

DimaPhil

11 лет назад, # ^ |

← Rev. 4 →

В первой правке скриншоты. Время неправильное, внизу c4 вместо p1.

→ Ответить

11 лет назад, # ^ |

Спасибо, нашел причину, исправил.

→ Ответить

Igorjan94

11 лет назад, # ^ |

← Rev. 2 →

в правке

→ Ответить

11 лет назад, # ^ |

Спасибо, нашел причину, исправил.

→ Ответить

11 лет назад, # ^ |

+12

Спасибо, нашел причину, исправил.

→ Ответить

SMAKH

11 лет назад, # |

+19

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

→ Ответить

pllk

11 лет назад, # |

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

→ Ответить

11 лет назад, # ^ |

Usual time. There was an issue around timezone support.

→ Ответить

11 лет назад, # |

+12

Delayed?

→ Ответить

11 лет назад, # ^ |

Delayed!)

→ Ответить

11 лет назад, # ^ |

Yeah. Probably related to the occasional crashes ("Service temporarily unavailable.")

→ Ответить

Darkstalker

11 лет назад, # ^ |

+64

Will it ended like TCO 2014 Round 1A yesterday ?

→ Ответить

11 лет назад, # ^ |

I hope not!

→ Ответить

I_love_tigersugar

11 лет назад, # ^ |

No, I think it won't be held next week, like TCO Round 1A.

→ Ответить

hzyfr

11 лет назад, # ^ |

number of registers keep increasing... from around 900 to 1000...

→ Ответить

11 лет назад, # |

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

→ Ответить

11 лет назад, # ^ |

i agree with you

→ Ответить

11 лет назад, # ^ |

nice hahdle

→ Ответить

11 лет назад, # ^ |

thanks :D

→ Ответить

11 лет назад, # ^ |

So you can vote for my handle :)

→ Ответить

-AKram-

11 лет назад, # ^ |

yes

→ Ответить

THAT70sSHOW

11 лет назад, # |

Is the contest delayed ?

→ Ответить

afrizal

11 лет назад, # ^ |

as you see

→ Ответить

naggar

11 лет назад, # |

+22

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

→ Ответить

Rap_Promoter

11 лет назад, # |

+19

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

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

→ Ответить

qwerty787788

11 лет назад, # ^ |

В англоязычной версии поста есть :)

→ Ответить

ApachE

11 лет назад, # ^ |

Но начала контеста-то еще не было. Они пока не опоздали.

→ Ответить

hzyfr

11 лет назад, # |

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

→ Ответить

naggar

11 лет назад, # ^ |

I don't know, but let's just hope everything is under control.

→ Ответить

11 лет назад, # |

wish a nice contest

→ Ответить

testingcode

11 лет назад, # ^ |

Что такое? Пишет осталось 4 мин, время проходит, и снова 4 мин, уже 3 раз.

→ Ответить

11 лет назад, # ^ |

ok you're right

→ Ответить

ApachE

11 лет назад, # ^ |

-8

Время до закрытия регистрации; Время до начала контеста; Второе время до начала контеста.

→ Ответить

11 лет назад, # |

can we know the reason for delay?

→ Ответить

11 лет назад, # |

last 30 seconds~~~~

→ Ответить

talznpy

11 лет назад, # |

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?

→ Ответить

0p9o8i

11 лет назад, # |

← Rev. 2 →

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

→ Ответить

kingofnumbers

11 лет назад, # ^ |

-17

I have a guess:

since the authors are Iranian then they wrote problems in English and then the statements have been translated to Russian ,during translating the mistake happened

→ Ответить

accidentallygivenfuck

11 лет назад, # ^ |

-21

What? There were 8 hocruxes? And 8th was hidden in Tom's CF account? One more HP movie? Harry Potter and Codeforces account LOL

→ Ответить

varun.tinkle

11 лет назад, # |

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)

→ Ответить

THAT70sSHOW

11 лет назад, # ^ |

← Rev. 2 →

I too faced the same problem , and misread it floor ( (w-a)/b) instead floor( (w*a)/b) . Wasted 45 mins :(

→ Ответить

1k_trash

11 лет назад, # |

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

→ Ответить

11 лет назад, # ^ |

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

→ Ответить

1k_trash

11 лет назад, # ^ |

Блин.

→ Ответить

aangairbender

11 лет назад, # ^ |

Ну или так :D

→ Ответить

Borisov

11 лет назад, # ^ |

Как вы получили такую формулу?

→ Ответить

11 лет назад, # ^ |

Ну если как в примерах a == 1 то сколько можешь баксов взять столько и берешь, остальные жетоны оставляешь. А если "a" больше, то нужно уже вспомнить что просто остаток от деления это уже не количество жетонов а, ну не знаю, очки какие-то. А вот если разделить на "а" то получится как раз количество жетонов, которые остались.

→ Ответить

Borisov

11 лет назад, # ^ |

Спасибо, теперь понял смысл

→ Ответить

aangairbender

11 лет назад, # ^ |

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

→ Ответить

11 лет назад, # ^ |

← Rev. 4 →

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

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

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

→ Ответить

compilation_error

11 лет назад, # |

← 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;

}

→ Ответить

11 лет назад, # ^ |

use this

→ Ответить

11 лет назад, # ^ |

or you could also use ideone

i find it more useful for sharing code.. :)

→ Ответить

Lazzaro

11 лет назад, # ^ |

Your code ran endlessly when dealing with the special case n=1.

→ Ответить

compilation_error

11 лет назад, # ^ |

thanks

→ Ответить

11 лет назад, # ^ |

or even paste ubuntu

→ Ответить

Mukit09

11 лет назад, # |

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

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

→ Ответить

11 лет назад, # |

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!

→ Ответить

11 лет назад, # ^ |

can you say what was the wrong i think i do same wrong

→ Ответить

11 лет назад, # ^ |

i took x-floor((floor(x*a/b)*b)/a) instead of x-ceil((floor(x*a/b)*b)/a)... took quite a while to realize this mistake...

→ Ответить

11 лет назад, # ^ |

isnt x%b enough?

→ Ответить

11 лет назад, # ^ |

nope... it is not enough... for example, take x=12, a=2, b=7... the actual answer is 1 but x%b gives 5...

→ Ответить

11 лет назад, # ^ |

so i couldnt understand the B

→ Ответить

11 лет назад, # ^ |

thanks

→ Ответить

11 лет назад, # ^ |

you're welcome

→ Ответить

nsun48

11 лет назад, # |

Pretest 4 is pretty strong.

→ Ответить

11 лет назад, # ^ |

if you are talking about problem C pretest 4 then i agree...

→ Ответить

nsun48

11 лет назад, # ^ |

Actually I'm talking about problems B, C, and D.

Screenshot: http://i.imgur.com/b8M210d.png

→ Ответить

11 лет назад, # ^ |

i cant say much on pretest 4 until i see it, but i think pretest 7 is strong!

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

n=1 and k!=0 :D

→ Ответить

11 лет назад, # ^ |

:D didn't take care of that... :P

→ Ответить

kingofnumbers

11 лет назад, # ^ |

LOL , I made two wrong submissions one failed on pretest 4 and the other failed pretest 7

→ Ответить

balakrishnan

11 лет назад, # |

+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.

→ Ответить

11 лет назад, # ^ |

are u referring to the warning which says to not submit solutions using the %lld specifier in C++?

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

In fact, we do not have any problem now even if we use %lld on Codeforces.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

luckily for u, it passed. but only just (3447ms)! ;)

→ Ответить

kien_coi_1997

11 лет назад, # ^ |

You can use %I64d, CF preferred %I64d. I used it instead of %lld.

→ Ответить

lisang

11 лет назад, # ^ |

I had the same issue. And it is really strange to have a warning with "lld" which is correct. And no warnings at all wile using "ld" and it seems like there is no situation when it could be useful.

→ Ответить

andreyv

11 лет назад, # ^ |

← Rev. 2 →

Previously there was a bug in MinGW, and %lld did not work — only non-standard %I64d did. Now it has long been fixed, but the Codeforces warning remains.

→ Ответить

11 лет назад, # ^ |

Oh, I didn't know the bug. Thanks. I thought the reason of the warning was that CRT used by MinGW hadn't supported %lld in the past.

→ Ответить

andreyv

11 лет назад, # ^ |

Yes, it was exactly this.

→ Ответить

11 лет назад, # ^ |

I see. Many thanks!

→ Ответить

11 лет назад, # |

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.

→ Ответить

11 лет назад, # |

-20

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

→ Ответить

11 лет назад, # ^ |

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

→ Ответить

11 лет назад, # ^ |

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

→ Ответить

11 лет назад, # ^ |

Понял.Спасибо!

→ Ответить

sskolot

11 лет назад, # ^ |

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

→ Ответить

11 лет назад, # ^ |

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

→ Ответить

oversolver

11 лет назад, # ^ |

← Rev. 2 →

что это за решение такое, там вроде очевидный n^2logn

upd. а, кажется понял, дп в другую сторону

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Можно было просто перебирать делители каждого нового последнего числа до корня.

Наверное, на n^2logn автора и рассчитывали, плохо составили тесты, что ли.

→ Ответить

11 лет назад, # ^ |

Кстати, 6283465 какую сложность имеет? А то я пока от рекурсии к итерации плоховато перехожу.

→ Ответить

oversolver

11 лет назад, # ^ |

это и есть n^2logn

→ Ответить

11 лет назад, # ^ |

тогда +1 к вопросу ниже)

→ Ответить

sskolot

11 лет назад, # ^ |

А можете привести решение? Не понимаю, откуда логарифм.

→ Ответить

oversolver

11 лет назад, # ^ |

← Rev. 2 →

dp[x][n] = кол-во посл-ей длины n с первым числом равным x.

dp[x][n] = sum dp[y][n-1], y=kx.

то есть одно dp[x][n] считается за M/x, а сумма n/i (i=1..n) как известно == nlogn (гармонический ряд). в итоге и выходит n раз запускается два цикла суммарно за MlogM

→ Ответить

11 лет назад, # ^ |

for(int i=1;i<=n;i++)
for(int j=1;j*i<=n;j++)

Следует внимательно присмотреться вот к этому коду. Интересный факт, что, как сумма гармонического ряда, это в итоге потребляет O(nlogn) времени.

Пример решения:

6274315

→ Ответить

sskolot

11 лет назад, # ^ |

Вот этого факта про сумму гармончиеского ряда не знал, спасибо вам и Bugman.

→ Ответить

11 лет назад, # ^ |

Ну для таких ограничений это нормально. А вот когда для n≤10⁵ слегка оптимизированный n³ проходит, это веселее.

→ Ответить

11 лет назад, # |

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

→ Ответить

Qumeric

11 лет назад, # ^ |

It was a special case. n == 1 (if k==0 print any positive integer, else print -1)

→ Ответить

renovated2020

11 лет назад, # ^ |

Test Case
1 2 9
5
AC output:0

→ Ответить

afrizal

11 лет назад, # ^ |

← Rev. 2 →

why the answer is 0? still dont get it

UPD : okay i understand now

→ Ответить

DanAlex

11 лет назад, # |

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

→ Ответить

andreyv

11 лет назад, # |

+17

Nice problems, I liked them.

→ Ответить

mmaxio

11 лет назад, # |

+59

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

→ Ответить

redjohn

11 лет назад, # |

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

→ Ответить

mysterion

11 лет назад, # ^ |

+14

В принципе загружать Windows — плохая идея :)

→ Ответить

redjohn

11 лет назад, # ^ |

-13

Вы намекаете, что у меня пиратка? Нет, windows у меня лицензионная и загружал я официальное обновление. Но в случае с пиратским софтом я с вами соглашусь :)

→ Ответить

11 лет назад, # |

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

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Link your submission :D :D

→ Ответить

http://codeforces.net/contest/414/submission/6287121

11 лет назад, # ^ |

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

DEL

→ Ответить

11 лет назад, # ^ |

Read the problem statement again, the numbers you print should be >= 1

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

You should output 1 (or any sufficiently small positive integer) for test case 1 0, not 0. The integers a_i must be in the range [1, 10⁹].

→ Ответить

11 лет назад, # ^ |

Omg! :D

Thank you, now I understand the mistake :)

→ Ответить

graceoflives

11 лет назад, # ^ |

if n=1 and k=0 you should print 1 instead of 0

→ Ответить

SC_pRo_ION

11 лет назад, # |

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

→ Ответить

-AKram-

11 лет назад, # |

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 :/

→ Ответить

ivplay

11 лет назад, # ^ |

I was also stuck for a long time :(

→ Ответить

graceoflives

11 лет назад, # ^ |

at the first moment i thought like you did...

and then i realized that it's a . not -

→ Ответить

-AKram-

11 лет назад, # ^ |

I need to pay more attention to details.

→ Ответить

11 лет назад, # |

-8

why is system testing taking so long today?!

→ Ответить

Lazzaro

11 лет назад, # ^ |

← Rev. 2 →

Perhaps system test cases of Problem C are so abundant.

→ Ответить

lovro-sinda

11 лет назад, # |

Any hint for task D , DIV2?

→ Ответить

11 лет назад, # ^ |

DP [len][last]

for i = 1 to n for j =1 to k for next= j to k with step j DP[i+1][next]+=DP[i][j]

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

it can be solved using dynamic programming. if u dont know about it, then first read up on it and solve 3-4 basic DP problems before reading below.

we can assume that dp[i][j] be the number of solutions such that i elements are already chosen, and the last of them is j.
then we will have dp[i][j] = dp[i+1][j] + dp[i+1][2*j] + ... + dp[i+1][n/j*j]. and the base case is dp[n][x] = 1.

my AC solution 6275634 uses this idea.

→ Ответить

pachon

11 лет назад, # ^ |

I use the same idea :D, i think it was an easy dp

→ Ответить

11 лет назад, # ^ |

Combinatorics

→ Ответить

kien_coi_1997

11 лет назад, # ^ |

Really? Could you explain your solution?

→ Ответить

11 лет назад, # |

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 $\text{[math]}$ 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?

→ Ответить

TsunamiNoLetGo

11 лет назад, # ^ |

Sadly, not all problems are solvable using python on codeforces.

You should be cautious submitting problems having O(+1000000), It will most probably time out ... specially using python 3.

→ Ответить

11 лет назад, # ^ |

Heh, okay, guess I need to get my C++ skills up too. Never thought Python is this much slower than C++. And perhaps note to problem setters: problems that don't force the participants to use a particular language are good. I'm missing those.

→ Ответить

11 лет назад, # ^ |

It's not about being able to use any language, it's about writing a program that's fast enough. Maybe you could make a Python code work fast enough if you optimized a lot?

My solution of C (div1) has a complexity that makes it possible to pass, but it gave TLE during the contest, yet I'm not saying the time limit should've been larger. It's basically the same thing.

→ Ответить

11 лет назад, # ^ |

I was under the impression that O(KN) is already fast enough ("hey, only 4·10⁶! Okay, perhaps multiply some coefficient, but it's not that large, isn't it?"), but you have a point too there.

→ Ответить

Qumeric

11 лет назад, # ^ |

← Rev. 2 →

No one did. I found 1 C#, 1 Delphi and about 20 Java.

→ Ответить

11 лет назад, # ^ |

Delphi isn't "slow".

→ Ответить

Qumeric

11 лет назад, # ^ |

That's why i said "no one did" :)

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

I've got AC on Python 3.3

That was easy 6288729

→ Ответить

11 лет назад, # ^ |

920ms~~ how lucky it is~

→ Ответить

11 лет назад, # ^ |

6288836

Optimized version, 530 ms

→ Ответить

EROR

11 лет назад, # |

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

→ Ответить

11 лет назад, # ^ |

I think it is because of the special judge of div1 A(div2 C)...

→ Ответить

DaneshvarA

11 лет назад, # |

When can we see our new rates?

→ Ответить

11 лет назад, # ^ |

just wait a minute~~~ the system is calculating wish your rate get increased~~

→ Ответить

DaneshvarA

11 лет назад, # ^ |

I hope so. Thanks. U2 I got to go to school tomorrow early morning so that's why I'm asking:D

→ Ответить

11 лет назад, # ^ |

now it is updated...

→ Ответить

_jagoth

11 лет назад, # |

← Rev. 2 →

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

→ Ответить

magician_14312

11 лет назад, # ^ |

At first, I thought that the sign was —. Thus, I couldn't explain sample tests. The image of expression maybe not clear enough.

→ Ответить

11 лет назад, # |

+17

Damn. I solved C in O(n²2ⁿ) (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.

→ Ответить

Vaness

11 лет назад, # ^ |

← Rev. 2 →

6285907, 6288207 — first one got TL during the contest(the only one that passed pretests but got TL on systests), second one passed all system tests in practise mode. The difference is only in one line:(

→ Ответить

kien_coi_1997

11 лет назад, # ^ |

My solution's complexity is O(n*2^n+mn)

→ Ответить

boleyn.su

11 лет назад, # ^ |

I make a mistake in Div1 D, write a-(b-c) as a-b-c. I corrected this and submitted only to find that the contest was just over!

→ Ответить

Vladimir_508

11 лет назад, # |

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

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

→ Ответить

11 лет назад, # ^ |

может быть переполнение x[i]*a в предпосл строке

→ Ответить

ahmedameen

11 лет назад, # |

← Rev. 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://codeforces.net/contest/415/submission/6284352

→ Ответить

11 лет назад, # ^ |

I think it is n^2logn

→ Ответить

mnbvmar

11 лет назад, # ^ |

+18

Note the following important "equation":

$\text{[math]}$

(it can be easily proved).

Now we see that in your code computation of dp[num][counter] takes about $\text{[math]}$ operations (and this is done for each 'num' and each 'counter'). Then for each counter computations are quite short:

$\text{[math]}$

The counter can have k different values, so overall complexity is $\text{[math]}$ .

→ Ответить

11 лет назад, # ^ |

nice analysis！

→ Ответить

ahmedameen

11 лет назад, # ^ |

i got it :) thaaaank yooou :)

→ Ответить

Saveliy

11 лет назад, # |

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

→ Ответить

11 лет назад, # |

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

→ Ответить

accidentallygivenfuck

11 лет назад, # ^ |

-23

Maybe this fact will help you in Div1-C. For any x following is true: gcd(x, x + 1) = 1.

→ Ответить