Привет, Codeforces!
5 июня в 18:05 MSK состоится Educational Codeforces Round 22.
Продолжается серия образовательных раундов в рамках инициативы университета Harbour.Space! Подробности о сотрудничестве Harbour.Space и Codeforces можно прочитать в посте.
Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 задач на 2 часа. Мы постарались сделать раунд так, чтобы в нём нашли что-то интересное для себя как начинающие участники, так и опытные программисты.
Задачи вместе со мной готовили Михаил awoo Пикляев и Владимир vovuh Петров. Благодарим за тестирование Максима HellKitsune Финютина и Алексея ashmelev Шмелёва.
Желаем удачи в раунде!
UPD: Разбор задач.
Hi every one.... is there any way to search problems by their tags? thanks
yes, just go to the problem section i.e.here and click on any tag written along with the name of the problem.
simpler solution: — just google it... like "codeforces problems
tag"Go to http://codeforces.me/problemset/tags/tag1,tag2,..,tagn. So to see all problems about binary searching and graphs, go to http://codeforces.me/problemset/tags/binary%20search,graphs
or use this link: LINK ( I don't know does it have all tags or no )
why some people downvoted him? he just asked a question :(
// now he is getting upvotes :))
I'm new to codeforces and this is my first educational round! Excited! :P
Too few comments! Isn't it weird?
Because this contest is unrated :V , I think.
Why is E not an interactive problem?
Can someone solve me B?I have idea but can't implement.
You can find all unlucky years in log(r)^2, then just sort them and find maximum length between all pairs of neighbours in sorted array. Also check for segments starting in l, and ending in r.
Stop killing the cute MO solutions xD.
How to solve F ?
for each edge find when its in the graph, after that something like this
I should have copied my Persistent IT code instead of trying to re-invent it...
Which problem did you plan to use Persistent IT on ?
E. I thought I had to have extra O(sqrt(n)) complexity, so I thought I had to use persistent IT. Only realized it at the last minutes and it's too late.
You can use SQRT decomposition to answer the queries rather than using complicated Persistent IT
Persistent IT is not very complicated, in my opinion some SQRT methods are more tedious to implement.
What is IT ? Interval Tree ?
Yes
Nice problems! What were your solutions for C?
Calculate all the distances from Alice and Bob, and find the node where the distance from Alice is maximum and greater than the one from bob, multiply that distance by 2 to get the number of moves.
why this solution is right ? can you give more details why we should do another dfs where from the position bob stands thanks in advance
The best strategy for Alice is to always go down in the tree. Bob wants to survive for as long as possible so his best strategy is to go to the furthest node from Alice. As explained in the editorial, Bob needs to go up in the tree (by 0 or more nodes) to reach the branch that leads to the furthest node. Sometimes this cannot be achieved since Alice will be there before Bob. That's why you need to check both distances.
I hope this helps. :)
Notice that Alice will walk down the tree to wherever Bob is, and that the number of steps it will take is just the depth of that path in the tree. That means that Bob should try to get to a node that has the greatest depth.
If the root node is at level 0, and Bob's node is a level x, the Bob can walk up at most
nodes up before choosing to go down the path that has the greatest depth. We can find the depths of the paths using a dfs.
My Submission: 27589077
Any hints on how to solve E?
Solve SPOJ problem DQUERY first, online using persistent segment trees.
For each i, compute bi the position of k - th number that equal to ai to the right (if there's no such position, bi = n + 1), then for each query, count from l to r how many number greater than r.
PS: My solution
pls make a div1 contest :'(
when will we be able to hack???
How to solve problem-B?
Find out all the possible value of x^a + y^b and then fond the max range between l and r.
Could one hack it :)
It failed :(
can some one tell me the answer for the following test case for problem C 16 12 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 3 11 11 12 12 13 13 14 14 15 15 16
i think the answer is 14. but seems its wrong please help!
You can copy the code of a couple of high-rating coders, run this case and, if their answer is the same, it is very likely that they are correct. My program outputs 16, but it might have a bug.
Answer is 16. Bob will walk down to node 16 and wait there. It will take Alice 8 moves to get there, so the total number of moves is 2 * 8 = 16.
The answer is 16 according to my code.
Почему на мой взлом мне пишут "Неизвестный вердикт"
Взломай точно так же еще раз, мне помогло
Nice problems, Why the rated rounds are not like this round? :"D
Can anyone give me a simplified version of test 8 in problem C?
Something like:
Answer should be 4.
When you realized that you at got WA because of 2 character in the code...
(Change
db[u] < da[v]todb[u]+1 < da[v])I also got WA at test 8. I found one possible test case below.
10 2 7 1 8 2 1 3 10 4 7 5 3 6 5 8 6 9 7 10
FeelsBadMan
FeelsBadMan
(Got E accepted 10 minutes after the contest).
PS: Btw, is there a fast way to insert image from computer?
Had any One Solve problem C using dp ?!
I think it was a simple greedy type solution,using DP probably wont help at all,also the constraint were not DP type,I may be wrong though..
I am getting WA on problem C for a case which is not valid and the case is also showing valid for hack input. But in the problem it is stated that "Bob starts at vertex x (x ≠ 1)." But in this case x = 1. Please check it.
Here is my code: 27597100
yes same problem.
Sorry, this test is removed now. It was added after contest ended but it was wrong.
Is there any way to get the hacking tests so that I can verify my solutions?
It was possible if u resubmit until education round 19/20. Now not possible
All unique hacking tests are added to testset after the end of hacking phase. It holds for every round.
Any idea how to solve D?
Define dp(x, y) = maximum sum with the last element indices of the two subsequences being x and y (assume x > y). Each state (x, y) has transitions to (z, y) or (z, x) where z > x. Now we have an O(n3) solution, but we can consider only first z's that give valid transitions (independently for each type of transition (same/+1/-1/congruent)), so it becomes O(n2).
My code is AC, and I hope it's correct :O
I got a wrong evaluation from Codeforces on Problem B. After the contest, When i checked the test case where i got Wrong answer. The output computed by Codeforces was wrong. I was getting a different output (the correct one) on all the other IDEs. Kindly look into this. 27593531 [Test #10]
I submitted your code using GNU C++11, and it was accepted. I don't use C++ normally so I'm not sure why. I hope this helps you discover the problem.
Thanks. Thats certainly a bug then. Because, whatever gets executed in C++11 can get executed in C++14 in the very same manner.
can some one help me with this? There is an array of integers,we need to answer queries in this form. given L,R and A,B need to count number of numbers in range [A,B] in the subarray [L,R].each query should be solved in logn time.what is the best datastructure to use here?
Segment Tree.
(AFAIK) You can get log(n) time per query with offline processing and segment tree. See SPOJ KQUERY problem for reference. (not giving details as you asked only the name of the data structure :P)
You can do it easily with merge sort tree, a variation of segment tree, but time per query there will be (log(n))^2
In the problem KQUERY we put all the queries and the array elements and sort it.Then we process each element.if it is an array element we update the segment tree, if it is a query we find numbers in range [L,R].here we are exploiting the fact that all the numbers(elements) which came before A query are greater than k.But in my question the numbers should be in a range between [A,B].so how do we do that using offline approach? On the other hand the merge sort tree approach seems good.
Simple. Answer for range [A,B] = number of elements larger than A — number of elements larger than (B+1).
So, for each range [A, B], you can find answer with 2 queries. kquery(L, R, A) — kquery(L, R, B+1) where kquery(x, y, z) returns number of elements greater than z in the subarray [x, y].
got it :D.Thanks for your time.love this community
Now you seem happy after asking question from live contest.
Cheater
Some of the successful hacks for problem C had incorrect tests in it (there was a bug in validator).
We are really sorry about the issue! These hacks are now rolled back, all the solutions which were hacked now seem to be accepted.
We should have worked harder on checking the correctness of all the checkers, validators and solutions. We will do our best to avoid further contests to have such major issues.
The editorial is published.
What's the recommended order for solving problems in a contest? Do we start with the easiest problem A first or is there a smarter strategy?
Start with the easier ones first. You anyway have to do them at some point in the contest. So why not to finish them up asap and then devote your time in the tougher questions.
Because the points you will get in B decreases faster than that of A.
Test case 5 of prob D:
10
9 6 8 5 5 2 8 9 2 2
Answer given is 9. But shldn't it be 10? {6,5,5} forming one subsequence and rest all nums for the other.
The rest will be {9, 8, 2, ...} and you can't take 2 after 8.
Ok got it thanks... i thought differ by 1 meant in terms of mod 7
WHat is the simplified version of test case 10 of problem C ? awoo
No idea. It's just a random tree.
I try to hack and all the website says is this: http://i.imgur.com/aoSKkAM.png
Anything I Should do?
Happens to me a lot too, I just refresh the page over and over until it works lol
Please ignore this. Doubt was resolved.
F isn't original. In fact, I've used the same idea in a contest in our school around three years ago. Also, it can be solved by link/cut tree in
time, which is better than the solution in the editorial.
But since it's an Educational round I don't think the tasks have to be original. I've seen other tasks in ECR that are obviously not original as well.
My code can be found here. You can see my poor coding style back then(therefore I had lots of trouble getting the input format fitted, even though there's only a little to be modified).