Codeforces Round #183

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

Fixed.

→ Ответить

BekzhanKassenov

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

Are you sure in number of this round? Think, it should be 183.

→ Ответить

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

Sorry for such a silly mistake ... /w\

→ Ответить

Death_With_Live

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

Very early announcement and score distribution (many peoples has like it), great setters and testers — I think it will be very interested.

→ Ответить

Dixtosa

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

Haha noone even mentions Div2 A and Div2 B problems :D

→ Ответить

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

← Rev. 2 →

-10

As you can guess, DIV 2 A, B is set by me ... /w\ ......）。。。

→ Ответить

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

I think the problemset is easier but much more interesting this time..

→ Ответить

hehaodele

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

-8

Who set the problem for Div.2

→ Ответить

HolyInq

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

← Rev. 2 →

Am I right that original statements will be in english?

→ Ответить

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

Of course they're English.

→ Ответить

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

Actually they should be in Chinese..:)

→ Ответить

roosephu

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

+27

Maybe Chinglish lol~

→ Ответить

cmonsuckitbitch

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

← Rev. 3 →

Why this blog was not on home page ?

→ Ответить

hehaodele

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

The first time I can participate in

→ Ответить

lxfind

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

Hmmm contest time changed? 6AM in California...

→ Ответить

Yo-Pta

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

-7

Why time is non-standart?

→ Ответить

enhydra

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

There was a risk of yesterday’s TCO Round 2C being cancelled and moved to 16:00 UTC today. Codeforces’ usual 15:30 UTC would conflict with it. It already happened with round 2A on 31st of March.

→ Ответить

Yo-Pta

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

Thank

→ Ответить

Rubanenko

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

+17

It would be interesting for me(and I think not only for me:)) to know some additional information about the authors of the contest — your hobbies, photoes, interesting stories etc.

→ Ответить

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

+57

xiaodao's photo there >_<

→ Ответить

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

+12

I wondered why comments by MinakoKojima got so many negative feedback?

→ Ответить

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

← Rev. 2 →

+39

A question : is MinakoKojima (Feihu Tang) boy or girl?

I thought the name is a boy's, but in his(or her) photos shared above it's a girl....

→ Ответить

Seter

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

+28

You can see that her name is 唐菲蝴(beautiful butterfly Tang),then everything goes right.

→ Ответить

Velicue

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

+17

She's really a girl, believe me.

→ Ответить

havaliza

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

+39

I recommend you all to participate in this event. You would enjoy solving this set of beautiful (and challenging :D) problems. :)

→ Ответить

evlinkov

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

давненько не было динамического распределения ^_^

→ Ответить

KrK

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

It is the Chinese round. I am really excited to see the problems! :) We had American problems (with USACO cows' background), we also had Japanese problems (rng_58's and the rest). And now is Chinese round. Love it.

→ Ответить

netman

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

Спасибо за контест! Всем высокого рейтинга(правда такое невозможно :) ) и удачи!

→ Ответить

woot

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

-6

=w= unsuccess to reach 1500 last match...=w= so ..hope my friends and i can reach blue again ..T_T

→ Ответить

evlinkov

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

в задаче B может быть 2 дата быть раньше чем 1 ?

→ Ответить

pitfall

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

посмотри на второй сэмпл

→ Ответить

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

+22

Получать в div1 клары по поводу задач div2 — это баг или фича?

→ Ответить

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

Не баг и не фича. Просто это так. Более того если ты во время контеста просто будешь находиться на сайте, то тоже будешь видет клары.

→ Ответить

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

Вопрос не только в этом. Это я сам уже понял. Сегодня меня заинтересовало, зачем в контесте отображать клары по задачам, которые не имеют к нему отношения (div1 D — div2; div2 B — div1). Уже, кажется, сам догадался, что это вызвано особенностями самой системы.

Подозреваю, что для приведения этого в более логичный вид — надо многое в системе переделывать, так что обойдемся:(

→ Ответить

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

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

→ Ответить

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

Захожу я в контест, смотрю "Вопросы по задачам", читаю то, что там написано. У меня там отображается одно и то же для обеих дивизионов, все клары для всех 7 задач дня, а не только клары по тех 5 задачах, которые были именно в этом дивизионе.

Я об этом "отображении". Прошу прощения, если сначала не совсем понятно выразился.

→ Ответить

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

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

→ Ответить

Scorpy

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

← Rev. 2 →

У меня сразу при прочтении возникла мысль, что клар к div1 В и из-за ошибки в переводе слова "data" речь идёт не о данных, а о датах .

→ Ответить

ptnk021215

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

are there any mistakes in sample tests in problem B div 2?

→ Ответить

PeterGriffin

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

-21

Congrats for making unrated contest.

→ Ответить

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

Who told you?

→ Ответить

vitux

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

+21

I hope you joke

→ Ответить

abhay26

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

Sir, this ain't April the 1st.

→ Ответить

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

+26

The contest was perfectly prepared and tested :D

→ Ответить

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

Why in B in the second sample the answer isn't (29,22,75,78)? In this rectangle distance from the center to the point (x,y) is 0, and in the answer to the sample it's 0.5.

→ Ответить

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

Same here. I don't know why this is incorrect...

→ Ответить

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

The sad part is that a lot of people solve it and I don't even know how to interpret the statement — should the rectangle be the closest to (x;y) or lexicographically minimum..

→ Ответить

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

I spend a lot of time to guess — but i still don't know why... Sent clar, let's wait

→ Ответить

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

I sent one an hour ago. Guess what the answer is? You're right, "no comments" :)

→ Ответить

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

For me, they said, that my answer is not optimal..

→ Ответить

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

Did they explain, why?

→ Ответить

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

← Rev. 2 →

I sen't another clar 15 minutes ago, still no answer. UPD: Got an answer : We need first maximize the sub-rectangle, then take the lowest distance.

→ Ответить

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

Damn, missed the word 'maximum'. Thanks, man.

→ Ответить

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

because you should select biggest rectangular possible

→ Ответить

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

Thanks for the answer. I feel like a total loser.. Ah, anyway, this will be a good lesson for my future contests.

→ Ответить

Hedayet

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

From the problem statement . . .Your task is to find a maximum sub-rectangle on the grid (x1, y1, x2, y2). . . .

→ Ответить

mkagenius

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

Missed the round — no mail?

→ Ответить

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

Check spam folder.

→ Ответить

nurzhands

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

← Rev. 2 →

+124

→ Ответить

eipie

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

Translation please? :o

→ Ответить

nurzhands

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

wow wow clars, be easier)

→ Ответить

http://en.wikipedia.org/wiki/Cyclic_number

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

+36

Как нормально решать С?

→ Ответить

sasha.sochka

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

How to solve Div2 D?

→ Ответить

Nezzar

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

first make a and b coprime try to max the length of x such that x%a=0, then check if y falls in range. if not, max y such that y%b=0

→ Ответить

HAPKOMAH

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

-10

Когда хакал, у чувака было время выполнения 2.6 секунды, а в задаче ограничение 2 секунды. Хак не защитали. То есть это ок, да?

→ Ответить

MikeMirzayanov

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

Какая задача? Какой взлом? Если что, в задаче 304A - Теорема Пифагора II ограничение по времени 3 секунды.

→ Ответить

HAPKOMAH

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

Видимо да ._.

→ Ответить

faiyaz26

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

+43

→ Ответить

tsoy

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

Lots of hacks on A div2 with test "10000", library solution on B div2 on Delphi, unprepared B div1. Nice.

→ Ответить

Avitella

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

← Rev. 2 →

python lol)))

from datetime import date

a1 = map(int, raw_input().split(":"))
a2 = map(int, raw_input().split(":"))

print abs((date(a1[0], a1[1], a1[2]) - date(a2[0], a2[1], a2[2])).days)

→ Ответить

pkhaustov

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

← Rev. 2 →

У меня вопрос к тем, кто готовил задачи. Вы вообще свои условия читали? Вы хотя бы картинки смотрели в них? Мне весь контест приходили клары, которые заставляли меня открывать браузер и проверять, не взломали ли меня. Зато по злой иронии (я пока что не знаю почему) взломали мое решение по C за 15 секунд до конца, а нотис об этом я получил через 15 секунд после конца контеста. Задачи, в общем-то, неплохие, но уровень подготовки контеста оставляет желать лучшего. Особенно порадовал клар по задаче второго дива. Спасибо, будем чуть больше знать про даты.

UPD. Простите, поторопился с оценкой качества задач. Ниже написали, что задача D решалась популярной статьей из wiki. Набор задач после такого вряд ли можно назвать неплохим.

→ Ответить

PavelKunyavskiy

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

+108

I'll just put it here. http://en.wikipedia.org/wiki/Cyclic_number

→ Ответить

Nikitosh

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

+11

Кстати, у меня после успешной попытки взлома переходило на английскую версию сайта. Устраните проблему, пожалуйста.

→ Ответить

wao.uchiha

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

I think the limit of n for A div 2 should be 10^3 or 10^5. Most of my room has a O(n^2) solution. Especially a nearly O(n^2*log(n)) succesful in defended 2 attack.

→ Ответить

Dmitry_Egorov

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

+125

no comments

→ Ответить

caustique

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

-13

Объясните, пожалуйста, а почему у всех проходят (по крайней мере, претесты) такие простые решения по С?

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

→ Ответить

c.c.

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

+24

Because of so many mistakes, I strongly think this round should be unrated.

→ Ответить

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

if so, this will third continuous unrated contest :)

→ Ответить

Jay

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

I agree with you.The questions were published so late that we had misunderstanded the problem and wasted much time. BTW, the D is a popular knowledge which you can find it on the Internet.So, I hope this round will be unrated.This is the only way to make it fairly.

→ Ответить

GlebsHP

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

+100

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

→ Ответить

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

← Rev. 5 →

-40

Dynamic scoring usually makes scoring very different from past. Will it influence the rating system?

→ Ответить

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

this is called dynamic scoring

→ Ответить

aaaaaaaaaaaaaaaaaaaaaaab

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

It's dynamic scoring

→ Ответить

zanoes

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

+15

What a funny round!

→ Ответить

mmaxio

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

+23

Сегодня я узнал, что такой код

import java.math.BigInteger;

public class D {

	public static void main(String[] args){
		BigInteger.valueOf(3).isProbablePrime(1);
	}

}

под Java 6 и 7 на CF в запуске работает 5 секунд :(

→ Ответить

cerealguy

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

← Rev. 2 →

+18

Я о существовании такой гадости узнал после одного из онсайтов :(

→ Ответить

mmaxio

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

+11

Тогда хватит это терпеть!

→ Ответить

NALP

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

Давайте вспомним этот пост

→ Ответить

dario-dsa

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

-21

Great round, interesting problems. :-)

→ Ответить

Renkai

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

The problem is nice,but clarifications too disturb.Waiting for next round.

→ Ответить

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

My O(N^2+k^2 a_max log a_max) solution passed system test of problem C with a lot of brunch-cutting... I think it is not intended...

→ Ответить

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

← Rev. 2 →

an O(n^2+ans*k^2+a_max ln ans) solution was expected.

→ Ответить

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

Sorry, I mistook the analysis of my order... My solution was your order, thank you.

I think TL is too short because my solution passed in over 1800ms with a lot of brunch-cuttings...

→ Ответить

Fcdkbear

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

+13

Try to use array instead of vector, it speed up performance of my code dramaticaly in this problem.

→ Ответить

http://codeforces.com/contest/304/submission/3706514

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

Oh, thank you for your advise.

→ Ответить

olekluka

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

Nice problems. A lot of maths, but It's enjoyable. :)

→ Ответить

JayYe

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

Intereting problems!

→ Ответить

scott_wu

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

+50

The data for div1 D seems weak. When N=1, it's clear that every base works, so the answer is x-1 if x > 2 and -1 if x = 2. However, some solutions that didn't handle these cases still passed system tests. For example, 3709363 gives 1 on the case "1 2".

→ Ответить

PeterNaut

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

What is the solution for problem Div 1 — C (Div 2 — E) (Minimum Modular)?

→ Ответить

Abbas.Servati

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

← Rev. 2 →

System testing of Div.2 was very bad.it was finished , but final standing was not ready!

→ Ответить

left_hand

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

Div.2 A

My code is TLE. ~~~~~ ans=sqrt(0.0+SQ(i)+SQ(j)); if( ceil(ans)==ans ) cnt++; ~~~~~ But I change “(int)ans==ans” ,then get AC....

TvT

→ Ответить

accidentallygivenfuck

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

← Rev. 2 →

Check out mine 3706566. I think problem is in ceil() and floor(). Got AC replacing floor(c) with (int)c — 3712951. I would like to say : Authors, How about increasing time limit to 4s ? but it's too late. I have already got my Wow you have +67.

→ Ответить

ragesh91

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

i too used ceil() function and TLE...

→ Ответить

Kianoosh

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

← Rev. 2 →

It would be better that you check your solution in custom test before submitting....

→ Ответить

jlahcejlot

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

Долой 31й тест в задаче B див2! "сколько между ними дней включительно"

→ Ответить

Logvinov_Leon

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

Только что с права видел ссылку на разбор. Но когда кликнул попал на свой профиль. И всплывающее окно, что недостаточно прав. Мне кажется, что это бага.

→ Ответить

andreyv

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

Нет, просто разбор случайно опубликовали и потом сразу скрыли в черновики.

→ Ответить

Nikitosh

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

Автор убрал блог в черновики

→ Ответить

Turtwig

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

ORZ failed div.2 A

→ Ответить

olive

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

For Div2 C, now I understand why I could not find any formulas for even values of n..

→ Ответить

kleninz

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

Weak pretests :(. B-Wa 11 because of mixing up n and m.

→ Ответить

jremloz4

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

← Rev. 2 →

Wow constraints were really strict.

My DIV2 A didn't pass because of the c++ floor method which is too slow, compared to a cast. For DIV2 B, why doesn't it work using mktime and difftime from ctime? ...

→ Ответить

Droom

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

Are you still sure that's because of floor()?

→ Ответить

jremloz4

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

Well I did some tests:

Using floor: http://codeforces.com/contest/304/submission/3713082

With a cast: http://codeforces.com/contest/304/submission/3713854

→ Ответить

Droom

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

843 ms with cast

1609 ms with floor()

But it doesn't mean that solution with floor can't be accepted

→ Ответить

gauravrana981

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

my final tests are checked but its showing skipped what does it mean????? http://www.codeforces.com/contest/304/submission/3709339 please clarify it...

→ Ответить

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

Are you sure your solution is your own, not copied from others?

→ Ответить

Petr

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

+18

Screencast: http://youtu.be/XWsPoC4p-EY?hd=1

→ Ответить

nurzhands

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

+29

add music))

→ Ответить

tomtomlv

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

How to get full test cases for: http://codeforces.com/contest/304/problem/E?

Thanks!

→ Ответить

ssi7415

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

Check the submission of Ents : http://www.codeforces.com/contest/304/submission/3710988

→ Ответить

tomtomlv

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

In the submissions large input data are cut.

→ Ответить

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

you can't get large test cases

→ Ответить

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

+32

Такого со мной еще никогда не было. Я хотел взломать решение dilutedream а. За 23 секунды до конца вбил тест подумал, что он не корректен. Подправил его и снова сделал взлом. У вот теперь я вижу, что мой первый взлом оказался удачным, а во второй раз за одну секунду до конца я взломал kingofnumbers. :-)

→ Ответить

tourist

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

+307

Having spent about 20 submissions trying to find out the reason of my wrong answer on test 8 in Div1-E, I've managed to receive the following outcome from the judge:

wrong answer 201st numbers differ — expected: '-0.0132824', found: '0.0124727', error = '0.0257551'

This doesn't look like a correct probability, does it?

→ Ответить

KADR

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

+69

I've got TLE 8 during the contest, but later I optimized my solution a bit and now it's giving the same answer as yours on the 8th test even when I use long doubles.

→ Ответить

error202

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

-36

All tester's program have different solution so you know

→ Ответить

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

← Rev. 2 →

the model solution of E is wrong...it has precision problem.

the setter is trying to fix it... but still rng58'solution seems has precision problem too...

actually they all work fine when n=40, but start to differ when it become bigger,when I change the double in model solution to long double,it seems it is the same answer with KADR.

→ Ответить

rng_58

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

+48

I've asked the author to give me his solution, and the author's solution returned even worse answer (smaller than -10000) for the following case:

int main(void){ int i; cout << 80 << endl; for(i=0;i<80;i++) cout << i << ' ' << i+80 << endl; return 0; }

My solution during the contest (got WA) also contained precision errors for this case. The probabilities were between 0 and 1, but the sum of the probabilities in some row was more than 22 (while it should be 0).

Currently I guess it's impossible to solve this problem precisely under the given constraints.

→ Ответить

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

+26

That is really bad.

I think this round should be unrated to you QAQ.

→ Ответить

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

← Rev. 2 →

-13

yes, if his solution is realy correct

→ Ответить

HAPKOMAH

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

-11

Yes, they can.

→ Ответить

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

← Rev. 2 →

+11

tourist's solution has no precision problem, but it run in O(n^5),maybe too slow. (it run 1890ms,barely in time:) )

I optimize it and work out an O(n^4 logn) solution,I guess now it is ok:3716717

→ Ответить

yaro

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

In attempt to make my Java version go through the time limit (without use of if (l[i] <= L && r[i] >= R) elimination) I gradually optimized it and after succeeding I also found out that Gena's (with or without your great asymptotics improvement) solution can still be noticeably optimized. :)
Initial version: http://codeforces.com/contest/303/submission/3716717
With two code optimizations: http://codeforces.com/contest/303/submission/3718523

→ Ответить

Gerald

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

+43

Yes, you are right. The author's solution is wrong for that tetscase. But all the pretests were right.

So, now we are discussing how to solve this problem with precision and make the results of the round as fair as possible.

Thanks for the notification!

→ Ответить

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

← Rev. 2 →

+12

I have seen you solution, it is a good idea but it actually run in O(n^5),maybe there's some test can make it TLE （the inner running time is (the number of segment contain givn sub-segment)^4. I have optimize it a bit and now it run in O(n^4 logn). check it 3716717 here. Now I think this problem is solved.

→ Ответить

tourist

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

+28

It seems that my solution's running time doesn't depend on the actual test case as long as l_i ≠ l_j, r_i ≠ r_j and l_i < r_j for all i and j. A gap of 110 ms is not big enough, though :)

Your optimization is nice, thanks! Now the problem is really solved.

→ Ответить

galois25

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

I checked WJMZBMR's n^4logn code and i believe that it has precision problem too, though it pass all the test datas.

Besides, I guess it may require O(n^5) to get the right answer, and so i suggest either enlarge the time limit or reduce the size of n ;)

→ Ответить

Gerald

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

+63

We discuss for a long time with a setter this problem. So we change the solution to a correct one. All the solutions that passed pretests at the contest failes on the system test as expected. So, this problem doesn't affect on the participants, because the pretests were right.

My appologize for this situation. And great thanks to tourist for the notice!

→ Ответить

Temirulan

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

Can you write tutorial for this problem?

→ Ответить

k0st1a

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

← Rev. 2 →

-19

Задача D div1 во время систеста имела 56 тестов, сейчас там есть как минимум 57, и некоторие accepted решения не проходять етот 57 тест.

→ Ответить

lazylie

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

← Rev. 3 →

It seems I solved 303C - Minimum Modular with brute force 3712393 which, I think, is O(5000*10^6) in the worst case.

Is there any testdata which challenges the program or I calculate the complexity wrong?

→ Ответить

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

Your solution is not brute, cause you calced values s and use them as optimization. Your solution is very close to right solution.

→ Ответить

velazqua

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

Can anyone provide a proof of Div I Problem A? I just noticed the pattern for n <= 10 and just submitted that hoping it would work.

→ Ответить

dc.

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

← Rev. 4 →

EDIT : The proof I have post is wrong. See the comment below.

→ Ответить

__Joker

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

Please correct me if I am wrong, but I am not getting the proof.

When you say even-odd pairs, does that mean all the evens come from A and all the odds from B. But, we can still get n/2 odd by mixture of ( E,O) And (O,E). Precisely n/4 (E,O) and n/4 (O,E). And same applies for getting n/2 evens. In essence this points that we can still gets the even-odd configuration.

→ Ответить

dc.

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

You are right. Sorry for having post a wrong proof.

→ Ответить

__Joker

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

No problem at all. Actually, this is way I was trying to prove that any configuration possible not for even n.

I just got proved that if n is even and if it is not divisible by 4 then there is no configuration with the above reasoning.

If you get the proof using the above logic please let me know.

→ Ответить

Ripatti

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

← Rev. 3 →

+46

If $\text{[math]}$ , then $\text{[math]}$ or just $\text{[math]}$ , where S = 0 + 1 + ... + n - 1 = n(n - 1) / 2. So, there must be $\text{[math]}$ . But when n is even, $\text{[math]}$ .

→ Ответить

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

← Rev. 2 →

Where S=0+1+2+3+...n-1=n(n-1)/2

→ Ответить

Ripatti

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

Thank you, fixed.

→ Ответить

kums_

4 года назад, # ^ |

there must S = 0 mod n. But when n is even, S != 0 mod n. I do not understand the above statement. Could you please elaborate more. Thanks

→ Ответить

codinginveins

4 года назад, # ^ |

When n is even, S = n * (n — 1) / 2 let n / 2 = p which is smaller than n S = p * (n — 1) Clearly, S in this case is not divisible by n.

→ Ответить

khaledkunbargi

11 месяцев назад, # ^ |

But also when n is odd. The sum formula stays the same. or I am getting this wrong ?

→ Ответить

khaledkunbargi

11 месяцев назад, # ^ |

Ahh Now i get it. S = n(n-1)/2 this sum is divisible by n because S/n = (n-1)/2.

Now if n-1 is even then n-1 is divisible by 2. else if n-1 is odd(n is even) the sum is not divislbe by 2. thus not divisible by n.

→ Ответить

happy

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

this is fine, i got the logic, but how to get the sequence as all sequences are not valid. your formula just tell if a valid sequence is possible or not.

→ Ответить

Check the wikipedia article, it also contains a proof

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

← Rev. 2 →

for N is even output -1 for N is odd the two permutations like this: 0 1 2 3 4 ... n-1

→ Ответить

lutljs

3 года назад, # ^ |

Why is that? How do we come to this?

→ Ответить

Pretty_Woman

3 года назад, # ^ |

I had the same doubt. But I guess it is expected that we try the obvious permutation first and observe that its the required one. When N is odd having the permutation

0 1 2 3...N-1

gives a permutation of required category. While it has been proved above very nicely that for N-->even there won't be one

→ Ответить

BekzhanKassenov

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

-30

Стоит tourist-у написать комент, как он получает кучу плюсов :)

→ Ответить

hacker007

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

For this very fast solution to problem A in div2, could someone explain the math behind it? Thanks.

→ Ответить

Darko

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

→ Ответить

RepairComputer1

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

How to solve div2 E-Minimum Modular? Thanks in advance.

→ Ответить