Привет, Codeforces!
12 января в 12.00 MSK пройдет очередной 285-й раунд Codeforces. Автором задач являюсь я(Савинов Евгений). Это мой первый раунд на Codeforces и, надеюсь, не последний.
Хочу поблагодарить Сергея Кияна(sokian) и Александра Голованова(Golovanov399) за помощь в подготовке и прорешивании задач, Макса Ахмедова(Zlobober) за неоценимую помощь в подготовке контеста, Алекса Фетисова(AlexFetisov) за прорешивание раунда, Марию Белову(Delinur) за перевод условий на английский язык и, конечно же, Михаила Мирзаянова(MikeMirzayanov) за замечательные системы Codeforces и Polygon.
Кстати, сегодня(11 января) у Михаила Расиховича день рождения, давайте поздравим его с этим!
Раунд состоится в обоих дивизионах. Информация о разбалловке будет опубликована перед началом раунда.
UPD1: Будет использоваться динамическая разбалловка. Задачи расположены в порядке возрастания предполагаемой сложности.
UPD2: Разбор задач можно найти здесь.
It's time is too early in our (Iranian students) timezone because we have to go to school.
I think you already are.
Why this http://codeforces.com/contests/501,504
501,504??
because !
Read these reviews ... he tried so hard to answer the question ...(so funny)
85 is a holy number for Iranians :D
I'm an Iranian and find this weird!
But in china 69 is holy number!
Number 69 is holy not only in China :)
69????
You're so rude...
Do you like big number?
Or big ...
Not important
Cause you have small ...
Do you see it?
No...
Cause you're so ashamed to show it...
Shame on you guys!
got it :))
what about 90 ?!
Oh...
That's so nice too :))
Wow ... Mike's Birthday ... That's amazing ... :]
use Preview button better than editing 4 times :D
Sorry ... :-"
Happy birthday MikeMirzayanov.
BTW it seems like tomorrow will be a busy day. Topcoder SRM 645 will take place 5 hours after the end of this round.
Nice — 5-hour long team training perfectly fits inbetween:)
Раунд будет в 3 часа дня для меня, главный вопрос придти на работу до или после)
Можно писать на работе, я обычно так и делаю.
Извиняюсь за, возможно, глупый вопрос, но как к этому относится начальство?
Огромное спасибо MikeMirzayanov за такие замечательные платформы как Codeforces и Polygon. С днём рождения!
Happy birthday MikeMirzayanov.
dis like me pls
Information about score distribution will be posted just before the round starts.
Why for almost all contests score distribution reveled just before the contest? What happens if author(s) revel it early?
No intrigue :)
The difficulty of the problems are very hard to judge...
Поистине гениально устраивать раунд в 12 часов первого рабочего дня в году
Weird timing. Cannot participate due to classes. BTW Happy Birhtday MIKE!!
thanks :)
Happy Birthday dear MikeMirzayanov.
Best wishes, from iran, Hamed
The first round in 2015 :)
Here in Venezuela Contest will take place at 4:30 a.m T_T i hope my alarm can wake me T_T
new year starts , i want to enjoy it as much as possible....:)
Are the problems easy or hard?
missed contest because of class :(
Hey savinov !
You can use this tag "Happy Birthday Mike ":)
Score distribution?
I'm so happy that I catch the contest. It was a hurry that I went home from the school.
In Codeforces rounds, when two or more separate contests are going to be held, the contests numbers are given by separating with comma. How to detect which contest number belongs to which one? e.g.: Today, two separate contests are scheduled for two divisions in round #285 and the contest link is: http://codeforces.com/contests/501,504. Now, my question is which division belongs to 501? is there any general way to know this for any round before its started? I think, MikeMirzayanov could say the exact answer.Thanks in advance.
Maybe it was scheduled to be a div2 only contest, and a contest was scheduled after it, and then it was made for both division?
just a guess.
you may check the URL of list of registered lists.
riadwaw,Good idea, Thanks again. :)
Oh no, dynamic scoring(((
Why????????
You should had registered to contest using 'register' link in contest list. Not everybody always participates, so system should know who wants to generate rooms.
in first 10 minutes i was 5th...
But now I'm 260th...
Why I can't never solve C???? :(
In first 10 minutes I was 3) And now 349 :(
And also now you are 1200 :)
Yes( I write 250/p instead of p/250 :( It's very very sad(
Nice problems! :)
It's a very bad idea to give numbers in decimal in D :(
Looking at D — I am now surprised that numbers in C are up to n, not up to 10^18:)
What was the aproach to task C?
Since the graph is guaranteed to be acyclic, it is a forest and hence it has a leaf. Find one such leaf v. Its neighbor-XOR-sum is the XOR of a single number (the label of its sole neighbor u), so we know there is an edge between v and u. Now decrement u's degree count and XOR u's neighbor-XOR-sum by v (this means removing v from the forest), rinse and repeat.
To avoid O(n2) time, store the leaves in a stack/queue. After a first pass through the vertices, you will only add at most one vertex at any given time (if u above has degree two, u itself is added to the stack).
The moment, when you thought that in input vertices can be shuffled.
It is similar to topological sorting
Как C делать? У меня вот упадет, да и много у кого, мне кажется.
How to solve problem D/B ( Div2/Div1 ) . thanx in advance :)
http://en.wikipedia.org/wiki/Factorial_number_system
I've used a similar approach.
However, I could only transform the permutation into a factoradic sequence in a quick way, but not vice versa.
Any good approaches? Thanks much!
What first comes to mind is a data structure that can find the k-th smallest element stored in it. I used a binary indexed tree in composition with binary search. From what I see after skimming some of the solutions that was a common approach. The total time complexity is
.
You can use binary search.
My submission 9414663 used this factorial number system but TLE'd. Is there an implementation that could make my program faster or is it because I used Python (which is slow)?
list.remove is O(n).
You used decimal in your
math.factorial(x)line. The trick is to avoid conversion to the decimal system and compute everything in factoradic directly.Guess how long it takes to compute
math.factorial(200000), and repeat this 200000 times.Yes, your algorithm runs in at least
time. You have to find a faster algorithm.
On the other hand, my
solution got TLE too in Python, so yes, you also need to move to a faster language.
Верно ли такое решение к Е?
Подвешиваем дерево за какую-нибудь вершину. Считаем хеши в каждой вершине на пути из нее в корень и из корня в нее. Дальше при запросе перебираем длину lcp бин. поиском. Чтобы зачекать префиксы хешами, находим lca каждой пары вершин и с помощью двоичных подъемов и level ancestor (la) получаем хеш префикса.
Итого
...
Можно заменить lca и la на крутые алгоритмы за O(1), но я в них не верю
TLE? Oo
Вам так не нравится
? :)
На самом деле можно бинпоиск и двоичный подъем объединить и сделать так, чтобы оно работало за
на запрос.
Hi,
I find the English version of problem C's description is confusing: " XOR sum of the numbers of vertices adjacent to v ..."
I can only understand it, after look at the Russian version: "XOR-сумма номеров вершин, смежных с v ..."
Seems like google translate did bad job :D
PS: I am out of this round, so I comment here. Good luck for your final rank!
EDITED: The statement should be: " XOR sum of the indexes of vertices adjacent to v ..."
The XOR sum of numbers a1, a2, ..., an is simply a1 ^ a2 ^ ... ^ an; everything XORed together.
Although yes, "the XOR sum of the numbers of vertices adjacent to v" might be better phrased as "the XOR sum of the labels of vertices adjacent to v".
Хороший контест, жаль слил его, застопорившись на первой задаче :( Очень понравились чужие решения Div-1 A, без всяких Set-ов, через стек/очередь, до которых я не догадался.
я сразу после конца допер до такого решения))
Can somebody please explain to me the second test case for C problem? Thanks in advance.
Note: (From problem statement) ...were the first integer is the number of vertices adjacent to vertex v, and the second integer is the XOR sum of the numbers of vertices adjacent to v...
No idea what second integer means. I do not understand why if both vertex have the same adjacent vertex number then the second number is different.
There are 2 verticles (0 and 1) with the only edge between them, so for zero verticle degree=1 and xor of 1 is equal to 1, for the second — degree=1 and xor of 0 is equal to 0.
Thanks!
There is an edge between vertex 0 and vertex 1.
so for vertex 0, degree = 1, and XOR sum = 1 (vertex 1 is the only adjacent vertex)
for vertex 1, degree = 1, and XOR sum = 0 (vertex 0 is the only adjacent vertex)
second integer means the XOR sum of the numbers on the adjacent vertexes, not the number of adjacent vertexes.
For example, if a vertex 0 is adjacent to vertex 1, vertex 2, and vertex 4, then the second integer for vertex 0 is "1 ^ 2 ^ 4 = 7"
Thank you. I understood now.
"were the first integer is the number of vertices adjacent to vertex v"
"the number of vertices" means the amount of vertices, connected to this vertex.
I think it's a shortage of the translation.
Am I the only one that thinks that number of interesting problems in that contest equals 0 :/? Though E was interesting a bit, but also pretty tedious to code, but I didn't find anything interesting in BCD, especially D which was "change decimal to binary and do some Gauss", pls. Sorry to say that.
I have the same opinion.
I found problem Div1-A/Div2-C pretty interesting and funny (maybe because our skills differ too much).
I was finding it interesting for quite a while — until I noticed it was a forest ;)
is it even solvable if it wasn't a forest? :v
Wow, when writing that comment I expected lots of minuses, because that's what hating posts usually get, but people seem to agree with me :P.
Well, usually when I see some downvoted hating post, it sounds like "I got TL on B, why did you set such a small limit? And I also got WA on C because of overflow, why there are no overflow cases in pretests? And I totally screwed up today, so this contest is awful".
And today I tried this round, because I've missed live edition; after that I opened comments, saw your message and thought "yeah, he is completely right...". This is the difference between that "usually" and this case.
What was the approach for Div 1 C?
Only observation that I could make is following.
For a fixed index i, let us say there exists an index j s.t. if we can make the entire array an valid palindrome by shuffling values of array from index range [i, j], then we can also do the same for any range [i, k] where k > j. This idea can be used to do binary search over j.
But I had doubts about how to check whether shuffling of current range [i, j] can make the entire array palindrome or not?
This, actually, was my exact observation as well. And I have the same question; though I believe I worked out one of the two possible cases..
it can be done without bin_search:
How can we check given range? For every position 'p' in our range:
1) we increase count[t[p]]
2) if n+1-p is outside this range, we decrease count[t[n+1-p]] (unless 'p' is a middle position in whole array)
In std::set let's have numbers such that count[a] is odd or negative (I call them "bad" numbers). A range is good if everything is ok outside range and:
1) our set is empty, or
2) our set has one number and count[this number] is positive odd number (it is possible only for odd n)
If you observe more, you would found that there are only twe basic range. Let a[1+k] != a[n-k] and for every i < k, a[1+i] == a[n-i]. So the two basic range is [1+k, g] and [h, n-k]. so you don't need to binary and just iterte over g and h.
I don't understand. For a string 22134 We can rearrange range [0, 2], but not [0, 3]...
You are rearranging a segment, but the entire string should become a palindrome.
I guess we can say that the Div. 2 3rd place account I_have_many_girlfriends (which was likely a Div. 2 account) is a cheater (because he has many girlfriends) :P
Which would not be very surprising because one cannot have many girlfriends without cheating on them.
I think there is problem about Div1.D and E's time limit. After solved C, I found that the basic solutions for both problems are possible to get TLE. An solution O(n^3 / 64) for C and an solution O(mlogn^2) for E. But the O(n^3 / 64) for C get Ac and O(mlogn^2) for E get TLE. So unfair to someone just as me choose E to solve~
My solution needs
time, solutions with bigger complexity shouldn't pass.
кто поможет найти 14 читеров, решивших В? в этом случае, ее стоимость возрастет до 1000 и рейтинг упадет не так сильно))
до этого раунда мне нравилась динамическая разбалловка))
Just learnt how reading bignums and asking about j-th bit looks in Java ;
And in C++?????
Great idea to give them in decimal, that task was surely equally hard to Java and C++ coders.
Whenever the system testing is fast, the rating updates are slow! :D Whenever the system testing is slow, the rating updates are fast!
epic bug =\ this code passed 7 tests ...
thanks savinov :)
your contest has nice problem :)
Approach for problem B.
(Explanation from adurysk)
Finding order of a permutation in a factorial representation
You can represent the order of any permutation like this. If a[0...n-1] is the given array, let la[0...n-1] be another array in which la[i] stores number of j such that j > i and a[j] < a[i] now the order of permutation a[0...n-1] will be la[0] * (n-1)! + la[1] * (n-2)! + la[2] * (n-3)! +.....you can see that la[i] < n — i similarly you can calculate the array lb[i] for the permutation b[0...n-1] now sum these two to get lc[i] = la[i] + lb[i] now at some index lc[i] can be greater than n — i, you can avoid this by shifting the carry to the index i — 1 and reconstruct the array c.
Getting permutation C from the lc array.
This part should be pretty easy. Go from left to right. Let us consider the situation in the beginning. At index 0, our value lc[0] denotes that precisely lc[0] numbers are less than our number at current index. So we can directly say that current number will be lc[0] + 1. So if we go to next index, we need to remember this assignment done at index 0. For that we can maintain a set of remaining numbers in permutation of size n. Now we need to find lc[i]^th the number in this set. This way we can extend the approach for any index i > 0.
We can use BIT for maintaining the required set.
Note: By set, I mean a mathematical notation of set, Don't confuse it with set in STL.
what is the intuition behind adding lc[i]=la[i]+lb[i]? even if we add these then it will contain n+1 numbers right?
Расскажите, пожалуйста про 23 тест в Div1/C. Очень интересно. З.Ы. много решений упало на этом тесте.
какой-то большой рандомно-пошафленный палиндром с алфавитом из двух букв.
What was the approach for Div 1 D?
What was the approach for Div 1 D?
Wow, dreamoon_love_AA back to red in no time. Congrats!
His rating is like Christian Bale's transformation.
You forgot about the American Hustle.
Будет разбор задач?
Уже 16 часов, как
http://codeforces.com/blog/entry/15743
Ага, с конца контеста прошло 3 часа
Упс, не подумал :)
Видимо CF показывает время создания поста, а не публикации — ИМХО это довольно странно.
Задачи с легендой про Мишу — это был идеальный контест :)
Does anyone have properly commented solution to div1 B (it would be nice if codeforces allowed us to sort searches by the "comment concentration" of code)
When competitive programming, people aren't bothered to put comments.
In almost all solutions of Div.2 D / Div.1 B I see magical operation x -= x & (-x) on integer x. Maybe someone can tell what is the meaning of it? And by the way, what is the data structure used? Where can I learn more about it? For me it doesn't look exactly like a segment tree.
It is the core operation in Binary Index Tree. You can see more details and tutorial here. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
It is also known as Fenwick tree
What are the detailed aproaches to all questions by the writer?
Why no congratulations on the winners like in other rounds? :(
Codechef is busy doing Hackercup, I guess. :P Server is down.