Привет, Codeforces!
13 июля 2016 года в 19:00 MSK состоится четырнадцатый учебный раунд Educational Codeforces Round 14 для участников из первого и второго дивизионов.
<У меня уже накопился большой список задач, пожалуйста не расстраивайтесь, если ваша задача долго не попадает в раунд>
О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.
Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день, в течение которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.
Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.
Не стесняйтесь присылать как простые (и даже очень простые), так и сложные задачи (но обязательно интересные). Просьба присылать задачи к которым вы знаете решение, с понятным условием (наличие легенды исключительно по вашему желанию), а также сопровождать условия одним-двумя примерами, чтобы можно было быстро убедиться в правильности понимания условия.
Благодарю их и всех кто присылает задачи! Количество, присланных, но ещё не использованных задач постепенно растёт. Если я нигде ничего не потерял, то я уже ответил всем кто прислал мне задачи более 5-6 дней назад. Прошу с пониманием отнестись в случае, если ваша задача долго не появляется.
</У меня уже накопился большой список задач, пожалуйста не расстраивайтесь, если ваша задача долго не попадает в раунд>
Комплект задач был предложен участниками сообщества. Задачу А предложил и подготовил Артур Яворски KingArthur. Задачу B прислал Никита Мельников nickmeller. Задачу C предложил пользователь blowUpTheStonySilence. Задачи D и E из большого комплекта задач присланных Zi Song Yeoh zscoder (он, кстати, сейчас участвует в IMO, пожелаем ему удачи). Задача F была предложена пользователем Michael Kirsche mkirsche.
Как я уже говорил задачу A подготовил Артур Яворски KingArthur, остальные задачи для вас подготовил я (Эдвард Давтян). Спасибо Татьяне Семёновой Tatiana_S за проверку английских текстов условий. Задачи вычитывали и тестировали пользователи, предложившие их, соответственно Артур Яворски KingArthur, Никита Мельников nickmeller, пользователь blowUpTheStonySilence и Michael Kirsche mkirsche. Большое им за это спасибо!
На раунде вам по традиции будет предложено шесть задач. Надеюсь они вам понравятся! Комплект задач должен получиться сбалансированным и, на мой взгляд, не сложным.
Good luck and have fun!
UPD 1: Все взломы по задаче D будут перетестированы.
UPD 2: Фаза открытых взломов будет продлена до завтра.
UPD 3: Прошу прощения за проблемы в задаче D. Решения получающие WA3 были перетестированы. Теперь все в порядке.
UPD 4: Соревнование завершено. Все решения протестированы на полном наборе тестов. Вскоре появится разбор задач.
UPD 5: Разбор задач опубликован.
I think I can solve with one or more problems in this test,good luck!
Wish you good luck
"TAK" and "NIE". So fun)
Codeforces website is very slow during the contest :/
Problem statement is not very clear. :( Also the website is so slow.
The english statements were not very clear in this contest :(
please check problem statement(english) before contest more than once. :(
The statement for problem A (in english) is horrible.
P.S.: I had to use google translate on the russian statement in order to understand the problem.
Half of round time could not connect. 'The connection has timed out'.
How can O(N^3 * Log(K) ) TLE in problem E ?
I am still loading problem A.
me reading problem A (before revision)
you sir, made my day :D
How can O(N^3 * Log(K) ) TLE in problem E?
My solution took 1.3/3 seconds. I am using statically allocated matrices. I guess maybe with vectors it may TL..
I've seen AC solutions with vectors.
Java with arrays TLE.
Java matrix exponentiation somehow passed by a hair: 19090004 (Never mind, that got hacked)
Edit: This one passes with plenty of time to spare: 19096055
Operation % works very long, you can use O(N^2) operations % instead O(N^3) in matrix multiplication.
You can see function mul in my code for details: http://codeforces.com/contest/691/submission/19082266
ignore
on what situations is this trick valid and yeah please explain MOD2?
MOD2 could be any multiple of MOD,
Thanks, cool idea!
How to solve E?
I Have solved it with Matrix exponentiation.
It looks like DP, but
kis too big. So, you may use matrix exponentiation. Let's create matrixA[N][1], everyA[i][0] = 1. Then let's create matrixB[N][N]. For everyiandj:B[i][j] = 1if the number of ones in the binary representation of the number(a[i] xor a[j])is a multiple of 3, elseB[i][j] = 0. So, answer is any element of matrixC = binpow(B, k - 1) * A. ComplexityO(N * N * N * logK)Any element of matrix C??Does all element will be same?
It does not fit with the given sample
Why am I getting a TLE in the Problem D?
My code
May be IO? Try
ios_base::sync_with_stdio(0);Why am I getting a TLE in the Problem D?
My code
TRUST SCANF AND PRINTF!
The main idea of your code is okay, but it has been implemented very inefficiently. First of all, when number of input >= 5*10^5, it is better to use scanf instead of cin. Also, you could improve your dfs function. It is better to check whether a node has been visited within the loop-this way, unnecessary function calls can be avoided. A lot more optimizations can be done; and I haven't looked at the code more deeply, but I think the logic is okay(as far as I have seen; apologies if I am mistaken).
This way means?
D: UnionFind to find connected groups, sort each group separately
E: Let matrix
, then the answer is sum of the elements of MK - 1. You can think of it as counting "paths" (sequences) in a graph with adjacency matrix M.
F: Compress and sort the array. Then we can enumerate all products of pairs which are not greater than max(p) and save counts for each product. There are at most max(p)log(max(p)) such products: (max(p) / 1 + max(p) / 2 + max(p) / 3 + ...). Then we need to count all products which are greater than max(p), using Fenwick Tree or partial sums (e.g. for each index i we find position where ai * aj > max(p) and then sum all counts on suffix starting from j). The latter count will always be added to the answer. Then to compute the answers we need to compute suffix sums on the array of counts per product. Special care needed for repeated elements.
Why am I getting a TLE in the Problem D?
My code
Hi! Why (ai xor aj)%3=0 is same as the number of bits in ai xor aj are a multiple of 3?
Shouldn't the answer of problem E test 4 be 63? My program found 63 valid combinations...
http://pastebin.com/HHDqbZ6s
Typo: Generated 62
UPD: Oh crap, I misread the statement. It's about the NUMBER OF BITS... Now I see.
Someone else tried to solve D using random selection of pairs for swapping? It was a funny idea but wrong, of course. :)
Why didn't they use a template type of definition to create __builtin_popcount() ?
I always get one WA for that!
This is intrinsic stuff, you can do a template version yourself :)
Hah! Kept getting Wrong answer on test 7 due to this
use __builtin_popcountll() for long long type
I did it sir but after One time wasting WA :P
I liked almost all the problems — I didn't have time to read F, as I spent too much time on C, which I didn't like.
Can someone explain problem e in more details??
This is actually a graph problem. Vertices are the elements of a, and edges between them are present if number of 1-bits in their XOR is divisible by 3. The task is to find number of valid paths of length k.
What you need to know is that if you multiply adjacency matrix of this graph k times by itself, you will get matrix that contains info about number of ways to get from one vertex to another in k hops (better explained here). After you get that matrix (this can be done in O(n^3*log k) via binary powering) you just need to sum up the values of the nodes and this sum will be the answer.
I think, He said to explain the problem not solution.
I also didn't get it, if a={1,1} and k=1 how is the answer 2? anyone explain please
The sequence will be of just one element. You can pick either the first one or the second one. Hence, the answer is 2, and it doesn't matter whether they are equal or not.
You should count the number of different valid index sequences, not sequences of their values.
but 1 isn't a multiple of 3
Question asks for xor b/w consecutive elements to have no of 1's in them as multiple of three.
Thanks a lot for such an interesting round, Edvard! And many thanks to authors for the efforts, it was definitely worth it!
Bonus for problem D: calculate the minimum number of swaps to achieve the maximum lexicographically permutation
Other variant for problem D: given two permutations and the allowed swaps, it is possible to obtain one from the other by making a sequence of allowed swaps?
Problem D: So, one swap step can be used any number of times!!! Didn't realize that. Anyways, how to solve this when each swap step can be used at most once??
When you found a connected group (with dfs or union-find), you have to put maximum element from that group to the first place and you can do it in only one way, e.g. if the group is 5 3 1 8 7 2 4 then you first put 8 to firstposition, and you have used all swaps between 5 and 8, so you repeat the idea on the rest, e.g. put 7, then put 4: 8 5 3 1 | 7 | 4 | 2.
EDIT: I've realized that the connected components are not necessarily chains. There even may be loops and therefore multiple paths from the largest element to the smallest position. It is not clear how to choose optimally.
In problem B, How is the answer for "opo" is NIE when the answer for "oHo" is TAK?? :/
The symmetric string is "oqo", which is not the same as "opo".
s-palindrome is a string that can be mirrored. For example, oqpo — is TAK (q and p are mirrored to each other).
In C, could be there multiple answers?
E.g, 323.345 can be presented as 3.23345E2 and 323345E-3
323345E-3 is incorrect, there must only be 1 number to the left of the decimal point.
the answer should be in the form of x = a·10b where 1 ≤ a < 10 so 323345E - 3 is wrong because 323345 ≥ 10
Is unexpected verdict in hack 240056 (problem F) caused by load issues (too many B hacks) or something else?
How to solve D? Naive dfs will time out,so how to compute efficiently?
Edit : I understood the solution.
https://en.wikipedia.org/wiki/Mirror_image
Nice, thank you very much :P
BTW this is the first problem I see that requires checking for mirror reflections and doesn't clarify what is the reflection of each character. In my opinion doing things like not clarifying makes problems really annoying. Afterall this contest is "educational", it should not annoy us by wasting our time checking if there's a reflection for each of 52 characters
I was hacked because i thought that i can be reflected to it self i.e string : iii does conut as s-palindrome but it turned out it shouldn't
It should teach you that such problems exist. I encountered a reversible stepladder and rotatable calculator-style digits.
Was getting TLE on F until I put cin.tie(0) into code.
Then changed everything to scanf and it worked twice faster.
http://codeforces.com/contest/691/submission/19096778 — scanf version, 1200ms
http://codeforces.com/contest/691/submission/19096765 — cin version, 2324ms
So the answer is just to drop cin/cout and switch to scanf?
The problem statements were really ambiguous. Even if we ignore the mistake in English statement A that was wrong for whole 10 mins, and made the problem unsolvable for English reading coders, why did you feel the need to include: "but not necessarily it should be the last one". It adds no clarification or help to the problem, and only confuses the competitors.
And for problem B, you should've specified that we should use the pictured alphabet to determine what the mirror images of certain characters are. Since it really depends on the font we use. For example: the letter l in some fonts mirrors it self, but here it doesn't, the same happens with the letter i.
I agree. The sentence "but not necessarily it should be the last one" made me think I was not understanding the problem as I could not see which kind of information was this sentence adding.
Hi, I want to join to these series rounds.
Why does it named "Educationl"?
Is there any plan for these rounds (e.g any discipline for problems and including subjects for a round)?
Is there any program of study the subjects?
Does it need to solve all the problems in previous rounds to join these series or not?
Here
That moment when you hacked yourself :D
Can someone please explain Problem Dthat how to model it into a graph. Thanks.
At first you notice that every position is node of our graph and swaps are our edges. Solution of this problem is to find connected components and then sort their elements. For every component we know values of initial permutation. Because we want maximum permutation, the highest value of component must be leftmost (of possible positions that are in current component). If we look at first example, we get 3 components. 1(1) — 4(4) — 7(7) 2(2) — 5(5) — 8(8) 3(3) — 6(6) — 9(9) () — value In first component the highest value is 7, so 7 should be at position 1, then second highest value is 4, so it is on position 4 and 1 is at position 7.
You actually don't even need to model graph, all you have to do is use DSU.
I hope this will help you.
A, B, C were "stringy" problems, here you can see some of mine solutions using regexes with Perl: A — 19090971, B — 19095540, C — 19089637 (or 19096070)
What's going on with D? Is it checker/validator bug somebody found? :)
Yes. Unfortunately, someone else is figured it out too and unlike me, he/she is exploiting the bug instead of avoiding it.
^ So u are saying u got >100 valid hacks.
I can't be 100% sure because of the buggy checker. All these solutions failed on my computer (or were close to time limit) at least.
Was judge_chutiya_hai already taken or did you make a typo?
Unfortunately, this behavior blocks challenging submissions on the real bugs in this problem :( .
We will increase hacks phase duration until tomorrow.
The hacks for the problem D will be rejudged soon. Testing during the contest was correct.
For problem D, I have tried hacking my submission with such test
3 1
1 3 2
1 2
My output is
2 1 3
while the answer given by std is actually the same.
Obviously the correct answer is
3 1 2
so there must be sth wrong with std.
I think you are right. I have never seen so many rednames are hacked.
What is the hack for problem D otheer than this?I am hacked.
Looks like you made exactly the same mistake as the author solution. No one can hack you until rejudge :).
I do not get you?
Hacks for the problem D will be rejudged soon.
Please update us when they're rejudged
+112 hack... Awesome
Can someone explain problem A to me in english? I can't understand the description
Every citizen should wear a jacket with exactly one unbuttoned stud (no matter what it's in order, first, last, etc.) except in the case when a stud on the jacket is alone, then it must be buttoned. So you have n studs and its statements (0 — unbuttoned, 1 — buttoned). Print "YES", if jacket buttoned right, or "NO" if didn't.
Problem B: Can any one please tell me why I'm getting error in test 14 http://codeforces.com/contest/691/submission/19109528 since the test case is not fully displayed and can't see it to correct or even trace the answer thanks, Emad
In your mirror function if left == 'w' you are returning true if right == 'W' ( Capital). Here right should be 'w'.
For Problem D, my submission http://codeforces.com/contest/691/submission/19110524 failed on test case 3, it shows the answer for case 3 is "1 2", however I found a lot of other's submission that the answer for case 3 is "2 1". So my question is which is correct?
From what I understood, it should be "2 1".
Same problem :(
Your submission was rejudged. It's Ok now.
Your submissions were rejudged. They are OK now.
Will submissions for problem D for virtual participation be re-judged? because I still have this invalid hack.
It was rejudged, you got OK.
Only submissions are rejudged, right? Hacks are still shown with "Ignored" status.
I am still hacked in the virtual participation submission.
I see that final testing is complete but challenges are still not rejudged (have "ignored" status). Some wrong solutions are passed as a result. See http://codeforces.com/contest/691/submission/19091023 and its challenge 240335 for example. This solution doesn't use path compression and so needs O(n^2) time on average (in the set construction phase) on my test in the challenge. If you are not going to rejudge these challenges, could you please add tests from them?
I can't do rejudges myself. I will add the test to the testset. And discuss possibility to rejudge the challenges.
The rejudge ability is badly needed in Education Rounds. Is it only MikeMirzayanov who can add it?
Where is editorial for this contest ?
OP said it'll be posted soon, just wait!
The runtime for problem E is not realistic at all. I have got TLE on test case 12 and tried it on my PC and it worked in less than 700 ms. I think something wrong is going on.
Try reducing the number of times you compute modulo. http://codeforces.com/blog/entry/46009?#comment-304869
hi, I don't understand the problem D, principally this part: "p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so pk = qk for 1 ≤ k < i and pi < qi"(the core of the problem :) ). Could you please, explain me this. thanks
Let p and q be 2 different permutations. Permutation p is lexicographically smaller than q if the first element that they differ at, is smaller in p than q.