Привет, Codeforces!
В 01.05.2019 17:35 (Московское время) состоится Educational Codeforces Round 64 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет Codeforces!
Harbour.Space University, the International Tournament of Young Mathematicians (ITYM) и St. Paul International School Barcelona создали специальный онлайн тест для школьников старших классов, который пройдет 5 мая в 17:00 (московское время).
Вы можете принять участие в онлайн-тесте, если соответствуете следующим требованиям:
- возраст между 12 и 18 годами,
- еще не выпустились из школы,
- соответствуете правилам в Международной математической олимпиады (IMO) или Международной олимпиады по информатике (IOI) для участия в 2020-м году (то есть имеете право отбираться и, в случае успеха, участвовать в этих олимпиадах).
Все принявшие участие в тесте получат 20% скидку на участие в Tech Scouts — двухнедельном летнем лагере, который пройдет 8-19 июля в одной из ведущих международных школ Барселоны St. Paul International School Barcelona. Те, кто займёт самые высокие места в тесте будут приглашены на собеседование, по итогам которого будут награждены полной оплатой обучения в усложнённом курсе Advanced Technical Track лагеря Tech Scouts.
Для того, чтобы зарегистрироваться, пожалуйста, заполните эту форму до 3-го мая, 2019.
Если вам хотелось бы поучаствовать в обучающем лагере или просто интересно узнать о нем больше, перейдите по этой ссылке: Tech Scouts website.
UPD: С одной из задач возникли небольшие проблемы, взамен нее будет использована одна из малоизвестных задач Максима Бабенко.
Поздравляем победителей:
Место | Участник | Задач решено | Штраф |
---|---|---|---|
1 | step_by_step | 7 | 491 |
2 | MyBotDear | 6 | 270 |
3 | receed | 6 | 280 |
4 | I_love_Tanya_Romanova | 6 | 286 |
5 | dreamoon_love_AA | 6 | 299 |
Поздравляем лучших взломщиков:
Место | Участник | Число взломов |
---|---|---|
1 | halyavin | 64:-3 |
2 | achaitanya.sai | 39:-23 |
3 | wzw19991105 | 18:-1 |
4 | LiM_256 | 14:-1 |
5 | patriot1488 | 2 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
Задача | Участник | Штраф |
---|---|---|
A | halyavin | 0:06 |
B | nuip | 0:07 |
C | quailty | 0:04 |
D | waynetuinfor | 0:11 |
E | step_by_step | 0:05 |
F | step_by_step | 0:15 |
G | step_by_step | 1:22 |
UPD2: Разбор опубликован.
Don't worry. I am there.
Account of @PikMike is very inspiring for everyone, Rating progression from 945 to 2244, NEVER GIVE UP!
PikMike says, NEVER GIVE UP
Hope the problem set is going to be an interesting one like the last one :)
Happy Coding
wtf?
the round should be unrated
what is going on?
Problem A was not well described. The side note under the test case was explaining an unwritten test case which means it was misleading. The solution had been rejudged. I see something strange that most of the solutions get WA answer on test 3. check the announcement of the round. Whatever, it is unrated now
To be honest, for long enough hasn't a problem A been so... chaotic.
Is it rated? Rejudging affects >3000 people.
UPD: Unrated.
read first problem 10 times before seeing announcement. Feeling Irritated
The round should be unrated, it's not ok that after 30 mins I see my AC code on A get WA
Literally everybody did though, I feel like it could still be rated, I don't know
oh no.
Обратите внимание, что существует ровна одна конструкция для некоторых выбранных позиции и размера только первой фигуры.
Что?
Если зафиксировать первую фигуру, все остальные выстроятся единственным способом. То есть ответ существует и он единственный.
Спасибо!
Eventually, the round became unrated. :(
Solve problems just for fun. ;)
Authors, dont worry. Shit happens. Good luck to you
So what's going on in Problem A? My code got WA after rejudge. But I don't know what's wrong in it. http://codeforces.me/contest/1156/submission/53616304
Consider a triangle inside a circle inside a square.
But because the contest is running, the link can't be accessed.
3 1 2 is 6
Wow...that's really interesting.
thanks
Got really happy after getting notification of round being unrated. Already many WA.
should have been rated but oh well
This round the highest Accepted on the entrance div2-A problem was 8. Out of 100! XD
to be honest, this compitition has got a really chaotic problem set.
(who had seen problem A give so many leaks? And problem B also got an error in the standard output.)
yet this round is unrated.
Irritating. Very irritating.
without paying attention to solved problems, It won't change our rating , yeah?
Right
So funny contest.. I see this 1st time, that I solved A and after retest I get WA. Funny evening...
раунд помойка
Автор, ты не смог решить ашку? Рили?
"_Unfortunately_, the round will be unrated."
More like, Fortunately am i rite?
Absolutely, the Author even can`t solve A. So irritating
some people say otherwise. :D
Я конечно понимаю что автору нравятся кошко-девочки и ему многое дозволено , но это уже слишком .
happy coding ❤
this but with GCD, divisor and Number theory
Why not try to learn those stuff and be able to solve problems way over your rating range?
Japanese people welcomed the new era, not error.
love it
Literally half participants on problem A. ( including me )
This photo really swapped out my bad mood today. www
Right, +10 WA to my submissions. Thx, dear author
Something went wrong...
Unfortunately, the contest is unrated(((
This year the highest grade on the entrance math test was 8. Out of 100!
I guess now everyone knows why xD
What a mess.
2 1 2
is this valid for Problem A?
UPD: Finally this is surely invalid because an anoucement.
The triangle is oriented in such a way that the vertex opposite to its base is at the top.
UPD2: really sorry, maybe I should change new glasses, the problem statement says, the triangle is oriented in such a way that the vertex opposite to its base is at the top
No. The direction of the red triangle should be like the black one.
isosceles triangle with the length of height equal to the length of base.
each triangle base is parallel to OX
for each i from 2 to n figure i has the maximum possible length of side for triangle and square and maximum radius for circle
The red triangle fit these condition well.
OK. But there is another announcement now.
Yes, but you have drawn a equilateral triangle for which the height is not equal to the sides, so this configuration is impossible.
this is my fault because of drawn misleading.
even thought if drawn correctly, the answer may be 5 not 6. :D
No. Notice that "each triangle base is parallel to OX".
Anyway, the base is still parallel :)
Yea, I think you are right. In this case, I considered the vertex as the "base" actually, so I thought it's not parallel to axis.
How can a vertex be parallel or not to a line?
If it does not intersect the line then it's parallel to the line :)
But just now there was an annoucement
The triangle is oriented in such a way that the vertex opposite to its base is at the top.
It's also in the statement of the problem:
the vertex opposite to the base of the triangle is poiting up;
And I think it was there before the announcement because I had the tab open and didn't refresh.
yeah, you are right.
maybe I should change my glasses
UPD: there are only four condition in very first,
the vertex opposite to the base of the triangle is poiting up;
this was just added later.
No, you don't have to do that; that state is revised, and before revising that, there was some vague state.
Hehe, didn't even think of this one!
Since the contest is unrated and everyone is discussing the problems anyway... how to solve C? It feels like there should be some sort of greedy way of matching up points but I can't figure it out.
I did binary search for the number of matches k. Check by trying to pair the k smallest points with the k largest points.
just sort the array, and use two variables i and j. initialize i=0,j=n/2 and then just start pairing them.
I want to experience how it feels like asking a solns of ongoing contest in comments.
Here it goes -
"How to Solve D??"
You can solve it with a little bit of DSU.
First of all, use all edges marked as $$$1$$$ to merge nodes into disjoint sets.
Then, the remaining edges — those marked as $$$0$$$ — are considered as the actual edge of the graph (in other words, after using all $$$1$$$ edges to create disjoint sets, we remove them).
From here, we'll perform DFS for the entire graph to find the components of nodes connected solely by $$$0$$$ edges.
For each component, let's denote $$$m$$$ as the component's size. Also, let's denote $$$k$$$ as the number of nodes not within the component, but can be reached from some nodes of the component due to being in the same disjoint set (mentioned at the first step). We'll add $$$m(m-1) + mk$$$ to the final answer.
The calculation of $$$k$$$ is simple — before the DFS traverse initiate $$$k = 0$$$. For each node $$$z$$$ visited, increase $$$k$$$ by $$$sizeof(dsc(z)) - 1$$$, with $$$dsc(z)$$$ is the disjoint set containing node $$$z$$$.
Total complexity: $$$\mathcal{O}(n \cdot \log(n))$$$ or $$$\mathcal{O}(n \cdot \alpha(n))$$$, based on how you construct the disjoint set union.
Why not to use DFS to find the components connected by 1 edges?
Well, we still need $$$sizeof(dsc(z))$$$ after joining nodes by $$$1$$$ edges, and (not sure if there was any neat implementation), if I performed DFS on that step, I'd either do it twice to assign $$$sizeof(dsc(z))$$$ to all $$$z$$$ in that component, or use a vector/stack to maintain the newly visited nodes, which could actually makes the implementation be a bit unnatural.
The answer is S(m*(m-1)) + S(dsc(z)*(dsc(z)-1)) + S(m*k) right? S() denotes sum over all components, disjoint sets and components respectively.
$$$S(m(m-1)) + S(mk)$$$ actually. Forgot to include it into the main comment, will edit in a few seconds ;)
I used Tree DP, with:
dp[0][i]: number of 0-1 path whose lca is child of i
dp[1][i]: number of 1-path which ends at i
dp[2][i]: number of 0-path which ends at i
dp[3][i]: number of 0-1 path which ends at i and the edge connecting i is 1-edge
dp[4][i]: number of 0-1 path which ends at i and the edge connecting i is 0-edge
It's also possible to do it in O(n) using dp on trees. Let dp[x][0] be equal to number of vertices to which we can access from vertice x using paths which have only zeroes as their weights and dp[x][1] same thing but which have only ones as their weights.
We can note, that each path we are looking for has a point where ones change to zeroes. Let's assume that our vertice is the vertice of change for some paths. We can easily observe that we need to add to an aswer dp[v][0]*dp[v][1]+dp[v][0]+dp[v][1].
So now the only problem is to find a way to calculate dp array. Firstly let's calculate number of paths which i mention before but only for vertices in the subtree of vertice x. That can be done as follows: if we have dp calculated for our son, and we use a path of weight y to go to him, then dp[x][y]+=dp[son][y]+1.
Now we have the answer but only for a vertice from which we started our DFS (because his subtree is full tree). Now let's start second DFS. An observation is: if we go from vertice x to its son using a path with weight y then dp[son][y]=dp[x][y]. Why? Having in memory that dp[x][y] is number of vertices we can access from vertice x using paths which have only weights y, then we see that this number can't change if we are using a path of weight y.
Lots of tree-DP problems based on paths have a standard procedure consisting of two steps:
Initially, if I define $$$dp[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a valid path, and $$$dp1[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a path by navigating only 1-edges, then in one dfs we can compute these values. Then, in the next dfs, we include in both $$$dp[v]$$$ and $$$dp1[v]$$$ the case where the second vertex of the path is the parent, which gives us the final answer for vertex $$$v$$$. So after this dfs, $$$dp[v]$$$ will be the number of valid paths originating at vertex $$$v$$$ and $$$dp1[v]$$$ will be the number of valid paths originating at $$$v$$$ by navigating only 1-edges. Note that we must change the value of the parent before that of a vertex, because we want to use the second definition of $$$v$$$ for the parent in the second DFS.
problem A (and other problems also) proved that every contestant is also a Labour. Happy Labour Day.
Is it possible that a cycle inscribed into the non-equilateral triangle (isosceles with the length of height equal to the length of base) with three distinct points touched?
Think that there is "An inner circle of a triangle". It is always possible.
fortunately, the round be unrated :) problems are interesting,but I have bad performance.
I know author is going to be blamed for this round. But honestly, I found the problems really beautiful and engaging. Kudos to author.
Good decision to announce the contest as unrated .
Thanks for very interesting problems! Can anyone tell me how to solve B?
Lets represent a, b, c...z as 1, 2, 3, ... 26. Now the best strategy is to club all a's together, all b's together etc. If you keep first all evens and then all odd terms, then we'll just have to worry about junction. For this you can find a pair of (even, odd) which differ by atleast 1.
Let's switch to numbers instead of characters, so the alphabet will be $$$0,1,2,\ldots 25$$$. Notice that a pair can only be ugly if one of them is odd and the other is even. First we have two cases if there're only odd or only even numbers, in that case we're done. Else we have at least one odd and one even number, intuitively we may want to minimize the touching of odds with evens so we may think about an order where first the even numbers then the odds come. This will only be possible if there's at least a pair of odd and even numbers that have a difference larger $$$1$$$ (since then we can put them in the middle and the rest can be placed arbitrarily) and obviously in the case when we have $$$0$$$ such pairs it would be impossible to order them (since in every ordering there is at least one odd-even pair), so we can see that the above statement is equivalent to that there's a valid reordering.
For everyone who got WA on test 7 (problem C), try this case:
10 2 1 2 3 4 5 6 7 8 9 10
Correct output: 5
I made a greedy solution (sort all the numbers using multiset, then for every number find the smallest number it can be connected to and erase both numbers from the multiset) and this case showed me that my approach was wrong. I hope it'll be helpful to someone.
what about z?
I put everything in one line. It should be:
10 2
1 2 3 4 5 6 7 8 9 10
Please point out the 5 pairs. TIA.
1, 6
2, 7
3, 8
4, 9
5, 10
A simpler test case to prove the greedy approach wrong is:
4 4
1 5 6 9
Thank you!
(Direct quote from Problem A) So can you pass the math test and enroll into Berland State University?
Um..... (sigh...)
after rejudged A
It was at this moment theroot knew, he fucked up xDD
I wanna be a yellow coder
Why RE on test 16? Code
I guess it is due to size of the array. As segment trees have around 4*N nodes.
Btw if possible then please explain your approach here!
В чем баг то заключался в задаче A?
3 3 1 2 ответ 7, по идеии ответ 6. Кажется автор тоже пропустил этот момент.
Нет. Там получается, что одна вершина треугольника совпадает с точкой пересечения окружности и квадрата
So.. Any hint for C?
If you order the array and one of the best possible solution has some pairs with both indexes in the first half of the array, you can change one index of each this pairs be indexes of the second half of the array. And this new set of pairs still is one of the best solutions.
Same way if you have some pairs with both indexes in the second half.
Last contest I wrote a toxic comment and I'm really sorry for that because mistakes happens and we should understand that
Any hints for E ?
You can doing it using a Mergesort tree.
For each element Ai calculate the range in which it will be maximum. That is Li and Ri where Li is the highest index j < i such that Aj > Ai and similary Ri is lowest j > i such that Aj > Ai.
For each Ai, check each j in Li...i-1 to see if Ai — Aj exists between i+1...Ri using the mergesort tree. (You just have to maintain a set on each node in the Mergesort tree and check for each node in the range if the required value exists in its set).
Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once. Each query takes logN*logN time.
Thus the complexity is N*logN*logN.
Not sure if easier approach exists.
"For each Ai, check each j in Li...i-1 " Can you please help me understand why this will not lead to O($$$n^2$$$)?
"Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once."
Could you explain this part a little bit more? What if we have a situation like:
[ ( y ) x ]
Here x and y are two elements,
[]
indicate Lx and Rx and()
indicate Ly and Ry. Obviously, y < x. Evidently, we can construct such a case (for example, 10 5 6 7 1 3 2 8 9 4 11).In such a case, every element between Ly and y is queried twice (once because of y and once because of x). I thought of the same approach during the contest, but I didn't think it would work because of such cases.
I had a similar approach, but i think it is easier. For each element you calculate l[i] and r[i]. These numbers represent the range in which a[i] is the maximum element. To find this easily we can use a stack.
Then, for every i from 2 to N-1, we will do the following: Choose the smallest side in our range [l[i],r[i]]. ( Smaller between i — l[i] and r[i] — i ). Then we can try every number in this range with a "bruteforce" approach. To know if that number will make a valid solution, we need to check if its complement ( a[i] — a[j] ) its in the opposite side and inside the range in which a[i] is maximum.
This approach seems like bruteforce, but with a little bit of math you can confirm it is actually linear.
Code to understand the idea better : 53634108
"This approach seems like bruteforce, but with a little bit of math you can confirm it is actually linear. " can you please give a rough sketch of proof?
I think Li and Ri can be found using range maximum query inside a binary search..
It is faster and not hard to find them with a stack. ( Linear time ) You can read about it here: https://en.wikipedia.org/wiki/All_nearest_smaller_values
divide and conquer
I think that 53648275 is pretty short, easy to understood and O(n log n)
can you please explain your solution a little bit?
I used divide and conquer... $$$f[l, r)$$$ counts how many pairs $$$(i, j)$$$ exists such that $$$p_i+p_j=max(p_i...p_j)$$$ and $$$i < m <= j$$$ for $$$m = (l+r) / 2$$$, and again solve the problem for $$$f[l, m)$$$ and $$$f[m, r)$$$ recursively (cases when the condition $$$i < m <= j$$$ not is true).
So for a fixed $$$f[l, r)$$$ and $$$m = (l+r) / 2$$$ for every $$$l <= pl < m$$$ and $$$m <= pr < r$$$ the maximum of the interval $$$[pl, pr]$$$ is $$$max(max(pl...m-1), max(m...pr))$$$, i assume that the maximum is equal to $$$max(pl...m-1)$$$ this determine $$$pr$$$ of a unique way $$$(pr=max(pl...m-1)-pl)$$$ so you only need check if $$$[pl, pr]$$$ is a valid pair
But what about if $$$max(max(pl...m-1), max(m...pr)) == max(m...pr)$$$ not $$$max(pl...m-1)$$$ ?, then solve the same problem again but with the reverse of the array, because if the maximum is in the right part in the reverse will be in the left part :)
is selecting all possible $$$(pl, pr)$$$ doesn't lead to $$$O(n^2)$$$?
For a fixed $$$pl$$$ you can determine of a unique way the maximum (assuming that is in the left part) and then $$$pr=max(pl...m-1)-pl$$$. So you only need iterate all $$$l <= pl < m$$$
Can someone tell me why this submission got WA https://codeforces.me/contest/1156/submission/53640819
got it fails for this input 10 2 1 2 3 4 5 6 7 8 9 10
4 3` 1 6 9 10 test like this one will explain the WA for you, if it doesn't i made it clear here https://codeforces.me/blog/entry/66796?#comment-509109
If anyone wants to solve problem D using dfs 53633184.
would you please explain your approach
Divide the tree into connected components of edges of 0s and 1s.
Now, there will be three cases to sum:
case #1: the path contains edges of all 1s.
case #2: the path contains edges of all 0s.
case #3: the path contains some edges of 0s in starting then all 1s at end.
For case #1 and case #2 answer will be simply
cnt1 * (cnt1 - 1)
andcnt0 * (cnt0 - 1)
respectively.For case #3: select a center vertex containing both edges of 0s and 1s. Now, to form a valid path, you have to select first vertex from connected component of 0s and second vertex from connected component of 1s. Answer in this case will be
(cnt0 - 1) * (cnt1 - 1)
.[ how ? center vertex will be counted in both components.]
How to solve B? What is the case when we don't get an answer??Please help guys
You need to take unique elements in string sort it and keep even indexes in first and odd indexes in second array. For example if string is "dcbab" then it would be like "ac" and "bd" and check if we can return it as "acbd" or "bdac" if two if this replacements are not possible then we return wrong answer, else we would return possible answer.
But how is this true ??
Because there if we take even and odd indexes of the unique string then there would be minimum 2 letters between them and if there is the size of the string is odd number it means last element of two arrays differ by 1. It means you check if which replacement is right array two-> array one or array one -> array two. And don't forget to print out the number of elements in the string
Cases when we don't get answer..
2
ab
abc
Critaical Test Cases you can check...
2
abd
acd
Output:
adb
cad
How to solve:
You can count the frequency of every letter from 'a' to 'z' in the input string... Then iterate through 'a' to 'z' and if count of it is not zero then insert it in a vector or string as you want... then take the even positions characters in vector1 and odd positions characters in vector2... then check if vector1+vector2 give you a valid solution or vector2+vector1 give you a valid solution if no one give a valid solution then, there exist no solution.. Hope you understand..
I'm a little bit confused. Isn't solution for problem F is to calculate number of winning and all combinations and just divide them?
What's halyavin doing?
in fact, Problem A is nice and trick. if you got WA... did you thought about this foken test case :D ?
6 intersection Points, NOT 7
also, the Infinite Cases :
But during the Contest: Set_IQ(0);
You didn't mark one of the six points in the first picture.
halyavin back in business.
Can anyone help me debug my solution for problem C
https://codeforces.me/contest/1156/submission/53644079
I get WA on test 7, is my idea completly incorrect ?
try case 10 5 1 2 3 4 5 6 7 8 9 10 ans=5
my code gives 5 too
Try test case:
4 4
1 5 6 9
Thanks!
Международная математическая олимпиада — это не MOI, как написано в посте, это IMO.
Why do most problem C solutions split the initial array in 2 ?
Lmao waited for this contest ever since they messed the last one a couple of days ago just to mess this one again.
Maybe this might interest someone...
I solved problem B using random_shuffle
https://codeforces.me/contest/1156/submission/53634293
I thought of this solution but didn't have the balls to write it :D.
In tags of problem C I've seen ternary search.Can anybody explain how to use ternary search in this problem?
https://codeforces.me/contest/1156/submission/53646659 here is a solution using ternary search. it's very similar to the binary search one so i think it isn't necessary to do it using ternary search. i think the easiest solution is using two pointers technique, it's clear that it isn't optimal if we matched any number with another one has index below than n/2 because it may decrease our answer and we could match the two numbers with another two have indices above n/2, so we only have to start the first pointer from 0 and the other from n/2 and increase our answer whenever the condition happen and increase the two pointers too if the first pointer is below n/2, else we increase the second pointer until the condition happen or the second pointer reach n and here is a solution using two pointers https://codeforces.me/contest/1156/submission/53615906
if the solution has one peak or low on the middle of searching range, we can find that by ternary serach . when doing two pointer greedy rolling match p1 = 0 is optimal obviously, and choice of p2 have the property to do ternary search if choose 1 it is not good since best can only be 1 it will be optimal at some middle point and then be bad again at last part since some possible match will be in front of p2
can anybody help me on test 6, problem B plz :( thanks
You can Check the following testcase
2
abd
acd
Output:
adb
cad
Don't worry awoo, we still love you!
+1
D, E, and F were really intersting. I guess without problem A we could've had a great contest.
So are B and C:)
Editorial?
Can someone tell we why I get a WA on test1 problemB My submission, it says that "wrong answer Resulting string should be a rearrangement of the given string" but I think my answer is correct!
Sorry, it's my fault
Prob.B
BOGO SORT Σ(っ °Д °;)っ
53651542
The problems are really good, by the way, how to solve problem E?
My second unrated contest...
Can someone explain problem C using binary search?
After sorting the set of point x, you only need to look at begin and last N points while checking whether N can be an answer.
My submission
You have no right to recognize a non-existent state Its name is Palestine, not Israel -_-
awoo There is a bug in the checker of problem G!
It says "each character is a lowercase or an uppercase Latin letter, or a digit" in the statement, but if you use uppercase, you get WA!
Accepted 53671039 and Wrong answer on test 1 53671084 only differ by 1 byte.
I think you have no choice but to rejudge G and make this round unrated :(
I fixed the checker and rejudged your submission, it's ok now.
The problem G is 20 years old! It was offered by Maxim Babenko for Saratov internal contest. Now he heads development of the YT platform for distributed computing at Yandex. We studied in the same school, in parallel classes. I am very grateful to Maxim that he inspired me to learn programming in those years.
Loved the problems... keep taking such contests more... it was nice contest if we ignore issue on first problem