Всем привет! Сегодня вечером в обычное время состоится Codeforces Round #296 для обоих дивизионов, автором которого являюсь я.
Готовить задачи мне помогали мои сокомандники, члены команды Moscow SU Trinity sankear и malcolm, а также множество ценных советов дал MikeMirzayanov, за что им всем большое спасибо. Переводом условий мы обязаны нашей бессменной переводчице Delinur.
Как обычно, вам будет предложено пять задач на два часа. Разбалловка будет оглашена позднее.
Приглашаю всех участвовать! Надеюсь, каждый участник найдёт себе что-нибудь по душе в предстоящем раунде.
UPD: разбалловка — стандартная.
UPD2: в связи с техническими трудностями раунд перенесён на 15 минут вперёд. Приносим извинения за непредвиденную задержку.
UPD3: Приносим свои извинения за проблему с задачей Div1-D. Претест #16 не удовлетворял ограничениям n, m, k <= 200000. Системное тестирование для первого дивизиона будет отложено. Если вы считаете, что этот тест серьёзно повлиял на ваши результаты, вы можете написать мне сообщение, и мы сделаем раунд для вас нерейтинговым.
Системное тестирование во втором дивизионе произойдёт в ближайшее время в обычном порядке.
UPD4: Тестирование завершено. Поздравляем победителей!
Div1:
Div2:
UPD5: Был добавлен разбор на английском языке.
First contest without saying thanks to Max Akhmedov (Zlobober) :)) ;) :D I'm really looking forward to participate in this contest ! \:D/
So we should say thanks to Zlobober :)
For some reason round writers never thank themselves..
I'll show you a counterexample ;)
Spoiler alert!!
Wait for a div1 round for a long time! I can't wait any more!
Since the last contest, div2 were waiting the same amount of time
I am div2,and I am proud.I want to become blue gay!
you can (;
gay....do you mean "guy"?....
Nope, he said "blue" :D
Understand you. Yaoi manga is very nice!
Waiting...
daiyu.
this contest is for Iran Good Bye 1393
happy new year!
actually Good Bye 1393
happy new year! :D ( 4 shanbe sooriam hast :-P )
I love your contests,very nice! Zlobober ,you are my idol :P
I missed CF' rounds. It is good to see new round. HC && GL to everyone :)))))))))))
this codeforces i gonna blue , if i will not i'll try again
congrats
at standard time T_T...
Great thanks Maxim Akhmedov Zlobober preparing the contest :D
"Moscow SU Trinity sankear и malcolm"
Please change this to
"Moscow SU Trinity sankear and malcolm"
Done, thanks.
All non-russian-speaker codeforces users became to know that "и" means "and" so there's no problem
My first Contest! Yay!
Your user name and the way you comment sounds fishy. But I'll just let it slide.
Finally ... we are so thirsty for contests. I think that I will not be able to live without codeforces.
This is the first time I do with contest Div.1. I hope will get some interesting in this contest.
what is difference between div 1 and div 2?
If your rating is >= 1700, you will compete in Division 1. Else, in Division 2.
Both divisions have 5 problems but Division 1 has harder problems. In fact, usually the first 3 problems of Division 1 are same as the last 3 problems of Division 2.
Here's more information regarding rating.
what is the diffeerence between div1 and div2
Hey, what are FAQ for?
lets define function F — number of different characters between two strings, then we could do something like that:
difference = F("div1", "div2") // should be 1
Why all of these peoples speak english ?
I missed many CodeForces rounds becoz of being away from Net & Load-Shedding problem.Thanks @Zlobober for this round... Hoping for nice problems. Wishing Good Luck & High Rating to everyone :) ! !
I missed many CF rounds becoz of internet & load-shedding problem..Thanks @Zlobober for this round. Hoping for nice problems..Wishing Good Luck & High Rating to everyone !! :)
div2终于来了
We'd better use English -_-#
oh,my god....I should get it earlier.
Hint:comments in russian are not shows in english version.
Exactly on 4shanbe-soori!
А привлекаются ли люди со второго дива для тестирования задач в таких случаюх?(интерестно) Спасибо за раунд!
Thanks for contest. This contest is on our(Iranian) National celebration ( charshanbe suri).
More information can be found here
Thanks .
Is It also celebrate in your country ???
yes it is :D
آقا امشب چهارشتبه سوریه.... :(
Ваш русский совсем не плох! amazing russian language!
"Before contest" countdown actually doesn't correspond to the time on the timeanddate.com, the difference is about 2 minutes. (I noticed because I realized that my PC time is not equal to the codeforces one, but I have synchronization enabled :)
Быстро вы инфраструктуру обновили :)
Ага, даже старт перенесли :)
Даже регистрацию снова открыли, чтобы уж точно дохрена запросов стало
За 2 минуты до начала контеста.
По закону кармы: приезжает работник Codeforces в аэропорт, готовится улететь, как его просят подождать не более месяца, пока ремонтируется аэропорт
Delay
Качнули
time extended
Wow added 15 minut
15 minutes delay, why?
Forgot to register, why God why ? :/
you can register now
no extended registration for div2 :( ????
fixed. try again.
registration is still open.
You still have time to register because of the delay
wow, thanks God
in fact — god reply your wish ! (like i reply to your comment khkhkhkhkh)
Hi, I could not register in time because of the technical issues (and i logged in late). It says div 1 registration is still open but div 2 is closed? Edit: its open, thanks!
Раз перенесли раунд, дайте еще времени на регистрацию в див2. Товарищ не успел.
The contest is not started right time.15 minutes late will be started.
Some people might have thought that "in at most an hour" means at least half an hour. I would suggest postponing it further to start at 19:00, so that no complaints can be made.
Nope, their fault i can't wait anymore
This was an old message , MikeMirzayanov forgot to change it back to "codeforces is temporary unavailable"
It's too late in China. 8 hours later I have to have class...
It's too late in China. 8 hours later I have to have class...
Почему регистрация div 1 открыто, а div 2 закрыто?
I was late to join contest. Therefore I entered into the codeforces to see about the condition of my friends. But now I can see it is 15 minuets late again!!! Now I can participate to the contest. First time the delay of codeforces becomes good for mine. :-)
you're lucky :-)
The contest is not started right time.15 minutes late will be started..
"We have to upgrade infrastructure...
Let's do it 5 minutes before the contest!"
I must go to sleep because I will go to school in 5 hours later.The sadness of UTC+8.
I must go to sleep because I will go to school in 5 hours later.The sadness of UTC+8.
tqvenii deda movtyann D amocanis 16 testis shemdgenels movutyann suyvelaperiii,2 saati tyvila gvawerinebb xalxss tqvenii suyvelaperi movtyan,mtestavidan dawyebuli mtargmnelidan damtavrebuliii,puiii
%(#*&(@&( какой раунд...
Usually after contest there are lot of guys who complain — Why there were no maxtest among pretests?
And today, in order to prevent such comments, authors decided to put into pretests not only maxtest, but even test larger than maxtest :)
Исчерпывающие предварительные тесты. В одном случае даже чересчур. Ни одного успешного взлома в 1 дивизионе. Не удивлюсь, если абсолютно у всех всё зайдёт на системном тестировании.
А во втором было как раз довольно много, большиство на А и B, но и на C (div1-A) тоже были.
А нет, всё же есть два взлома. У людей на 117 и 603 местах. Но всё равно это, наверное, рекорд.
http://codeforces.me/contest/528/status
Спасибо за контест. Задачи были очень интересными, а условия — очень весёлыми.
It was Good contest but I wish it had more time
Any hints for Div2 B?
Div2 C: Time Limit Exceeded in pretest 11.
How to solve DIV2-D/DIV1-B ?
Let's reverse a problem:
Points a and b are connected only if distance between them is smaller than sum of their weights.
In this case, we can imagine one point as interval [x - v, x + v].
When two intervals overlap, corresponding points are connected.
To find a result, we need to find the largest subsets of intervals that are not connected (in original problem — the largest where every two are connected).
Why do we need reverse problem? Because it makes everything much more easier. Every point correspond only with one interval (in original problem — with two) and simple sweep from left to right will do whole job.
First of all, if x_a < x_b < x_c and a connected to b and b connected to c then a connected to c, so if we have connected sequence of points it's a clique. Now we should find largest connected sequence of points. Let us consider the points with weights as segments with length as two weights and centered in point. We are looking for max set of non-intersecting segments. Here we get events: starts end ends of points. Sort them and go from left to right. When segment starts, answer for this segment (size of the max set of non-intersecting segments from segments from most left segment to segment under review) is max from already closed segments plus 1. It's just a variable, which is updating then segments closes. 10322276
Sort the point by the coordinate. Consider 3 points i, j, k (i > j > k). If there are edges (i, j), (j, k) then there'll be also edge (i, k). Because:
x[i] - x[j] > = w[i] + w[j]
x[j] - x[k] > = w[j] + w[k]
< = > w[i] - w[k] > = w[i] + 2w[j] + w[k] > w[i] + w[k]
<=> there is edge (i, k)
That means if we add i to the clique which contains j, when we'll have a new clique.
Now everything left is a simple DP with Fenwick tree :D You can check my submission for more detail :D
:D This is so overkilled.
That's how I made it too, and it took me about 10 minutes :))
I also spent a long time thinking about the meaning of that formula. Suddenly I realize that they are just circles center at xi with radius to be wi
And answer is the maximum subset of circles that doesn't intersect with each other =)
QAQ , Consider 3 points i, j, k (i > j > k). maybe it is x[i]>x[j]>x[k] ???
Sort the point be the coordinates. Then it's the same :D
Its a lot more intuitive than converting the problem to counting non-intersecting circles, according to me.
Is the contest unrated for div2 participants??
Really hope not!
Contest is rated for Div2 participants.
Contest is unrated only for those Div1 participants who write me a private message shortly.
Why would it be unrated?
You can get the answer at UPD3 :)
Huh, 67 people did problem with FFT :o, nice.
I solved it with brute force. Ran max test in 1.6s in Custom test.
UPD: It passed sys test.
Yyyy, seriously xd? Just check every occurence naively xd? I hope it's not offensive, but I really hope that this won't pass :p.
It's not very naive. I did it with bitmasks, so runtime is T(N2 / 32). This solution does not depend on any property of the test, so unless custom invocation runs faster or I made some stupid mistake, it'll pass.
This problem reminds me of 472G - Design Tutorial: Increase the Constraints. They feel very similar to me, with solution being FFT (which I don't really know), and looks possible to solve with bitmask stuff.
What is the meaning of T(), I have seen it a few times ago?
T is number of step, meaning it doesn't ignore constant factors.
Huh, funny, I didn't know this. Is it formally defined or is that auxiliary notation introduced for competitive programming purposes?
I think I have seen them in OCW videos, though not sure :P
T(n) is used as running time on problem of size n in "Introduction to Algorithms", so I think it's not limited to CP purposes.
I think that this is something different. T(n) as you described now can be equal to O(n2), it is not consistent in any way with the meaning of T(n2 / 32) you used before.
Disclaimer: I'm always confused by these things, so I may be speaking non-sense.
Since O(N) is upper bound function, we can have f(N) = N = O(N) = O(N2). And in here T(N) means true value of runtime (?) So what is wrong with T(N) being equal to O(N2) ? For me, this only means that, in most cases, we should use Θ or T instead of O.
What I'm saying is that you wrote T(n2 / 32) while you should have written sth like T(n) = n2 / 32, because n is T(n) means size of the problem and n2 / 32 ain't one.
By the way I think that Θ would be more appropriate here, because for me T is used rather to write down some equations for complexities like T(n) ≤ Θ(n) + T(3n / 4) + T(n / 5) like in algorithm of finding median. T could be used as O(sth) as well, doesn't have to give strict bound.
Ok, I see the problem now. Thanks! :)
Thank you, and Swistakk too! :)
I guess the most common notation of complexities are
O for upper bound, Ω for lower bound, and Θ for strict bound
If you used the bitmasking optimisation, it's not really brute force. It's as if you said you ate pancakes: yes, the meal is called that, but pancakes themselves usually make up just a small portion of the meal :D. That you used a clever trick to make a brute force algorithm run fast, it doesn't mean you solved it just with brute force.
I am surprised that this problem was used for today's contest; its solution is described at e-maxx.ru (one of most popular sites with algorithms for competitive programming in russian) in article about FFT, so it should be well-known for russian-speaking participants.
As for me, it's completely unclear how the problem is related with FFT... So existance of solution on the internet does not help much
Div1.D was FFT, right? I don't know FFT but knowing what problems can be solved using it, I think so.If no, how to solve it? :)) all the problems were nice except of div1C which would be nice if it hadn't had the case with self loops.I solved it fot the tests which didn't have that case but, of course, I didn't get any points...
What is your solution? I wrote Euler path and for my solution it doesn't matter if graph has self-loops.
Woow, it seems that you have a very nice solution.In this case, C was very nice too :)) My solution was some strange thing, sth like this: I was making a bfs, building the tree and the edges out of the tree were chosen random(or from x smaller to y bigger) and I than, using these edges, I was fixing juste the sense of the edges of the tree, from leaves to the top.Can you please explain your solution?
Firstly, link all vertices which have odd degree. Now graph has Euler cycle. Suppose it's c1, c2, ..., cm. Then we output edges
. But there is a problem when graph has odd number of edges. In that case we need to add edge 
.
Thanks :) I understood and the idea is preety cool
Actually, there's a bit more. Consider a test
Here 1, 3, 4, 6 have odd degree. If you connect 1-3, 4-6, then you'll have to add two more edges to deal with components with odd number of edges. However, 3-4, 1-6 yields a single component of size 6, so this is better.
In general, it is optimal to connect all odd-degree vertices in such a way that all components involved merge into a single component.
But there is only one component in the graph.
Indeed, it was easy to miss something in this kind of statement. Also, the announcement said something about "the construction should not be connected in any sense", which I fail to understand in this case.
They probably meant that your orientation of the edges should not guarantee strong connectivity or something like that.
The graph is connected.
The cables are put so that each computer is connected with each oneperhaps through some other computers.Other possible solution, without Euler cycle, after linking verticles with odd degree: in DFS tree, make all edges that are not in the tree go up (towards the root). Then, for each verticle, starting from the bottom, direct the edge to the parent either up or down, such that # of incoming and outgoing edges is even. The only possible case where we need to add a loop is the root.
Yes solution for Div1.D is FFT.
1) Iterate over 'A', 'G', 'T', 'C'
2) Let's denote current letter c. Construct new string a' and b': a'[i] = [exist a[j] = c and |j — i| <= k], b'[i] = [b[i] == c].
3) Now lets apply b' to a' with offsets 0, 1, ..., n — m and calculate scalar product for each offset. If the value of scalar product is not equals to the number of ones in b' than offset is bad.
4) If offset is not bad for all four letters than it's good.
Third step can be processed in O(n * logn) time: let's duplicate string a', reverse string b and multiply them. Now in positions from m — 1 to m + n — 2 we have the scalar products that we need. Multiplying we can do using FFT.
Hi, may you elaborate it a little bit?, please
was difficult. can't solve Div2-C, what is needed there? map?
I answered queries in reversed order with disjoint set union, but I think that there is simpler solution.
it can be solved in O(W+H+N)
I used multiset for distances between cuts and set for coords of cuts
I used segment tree to solve it, I hope it will pass. The idea is for each column to store the maximum width of a rectangle using this column. It is the same for the rows. When I was reading the codes of people in my room, I saw solutions with sets or priority queues. Can somebody explain such solution?
My solution:
set HCut, WCut — coords of cuts (at first (0, h) and (0, w))
multiset DistancesH, DistancesW — distances between adjacent cuts (at first (h) and (w))
If we've got query (H x), we:
Search in HCut iterators, pointing at two elements which less and greater than x (We always can do it). Suppose, we found it1 and it2 (*it2 > *it1).
We delete from DistancesH (*it2) — (*it1) and add (x-(*it1)) and ((*it2)-x)
Print max(DistanceH)*max(DistanceW)
Add to HCut x
Hi, can you please tell me whats wrong with what I've done? I got a TLE on this: http://ideone.com/SHyKGR
My algorithm is the same as what you've suggested. Thanks for the help in advance.
lower_bound() is too slow for set operation because set<>::iterator ain't random access iterator
you can first insert pos into the set, then go up and down a bit.
10332363
You can also change lower_bound(XXX.begin(),XXX.end(),pos) to XXX.lower_bound(pos). It will get AC.
Oh so my lower bound was doing a linear scan. Thanks, guys. I got it accepted by changing that :)
The smartest solution I saw someone using was using DSU.
You could solve the problem backwards by merging X-axis and Y-axis intervals and updating the largest intervals if the merged interval is larger than the current one.
The algorithm itself is O(nα), isn't it?
thanks 4your ideas.
First time of playing hacks, so interesting.
Btw you can check your div. 1 A,B,C solutions in upsolving of div. 2 contest.
It's also tested almost instantly there, looks like all submissions are already tested and results are cached.
i know its silly -> a little hint about A-Div2 ?!? so, this is math , no programming -_-
i know its silly -> a little hint about A-Div2 ?!? so, this is math , no programming -_-
here is pseudo-code for Div2 A
while(a>0 && b>0) { if(a>b) { res+=a/b; a%=b; } else { res+=b/a; b%=a; } }
It was nice. Thank you.
It was nice. Thank you.
Div2-B — TLE54
Div2-C — AC
It is sad when you can't solve easy tasks:D
I can't understand this test in Div2B: 2 xy zz
Why is the answer: 1 1 2 ?
We transform strings as xy->yx and have: yx zz
And the Hamming distance IS THE SAME!!!
I can't understand this test in Div2B: 2 xy zz
Why is the answer: 1 1 2 ?
We transform strings as xy->yx and have: yx zz
And the Hamming distance IS THE SAME!!!
Test #11
2 xy zz
Output is 2 -1 -1
Sry(
Check out my crazy div. 1 B solution, lol 10326839
В чем может быть проблема WA26 Div2-B.( Решение) Можно же вывести любой ответ, разве нет? Да и расстояние Хэмминга, как в ответе системы.
при свопе символов на выведенных твоим кодом позициях расстояние хемминга становится равным 3. там же в комментарии чекера написано.
Если я правильно понял вердикт жюри, то если ты поменяешь индексы, которые выводил, то получишь расстояние не 2, а 3. А почему так? Хоть убей, не пойму (лень в коде разбираться:D)
Div1.C:
Гарантируется, что существует решение, в котором p не превосходит 500 000.Разумеется, существует, например, если мы продублируем каждое ребро и свяжем в каждом компьютере с клоном, а потом пустим информацию по ним в одну и ту же сторону, огромное спасибо за инфу
How to solve Div1 B?
Update: I missed this comment where tom describes his idea.
Sadly, it took me an hour and a half to figure what to do with the values x + w and x - w (the last step)...
Thank you, this idea seems to be similar to tom's. Instead of DP, a priority queue can be used. Sort the segments by their left coordinate and the queue's top element will be the one with the smallest right coordinate. At each step, pop the top element while it's right coordinate is less that the current's segment left coordinate. Then, insert the current segment and compare the size of the queue to the answer(I just described the algorithm that I always use to find the number of maximum segments that intersect).
Unfortunately, I didn't figure out the {x-w ; x+w} representation of the points... :)
Если
в условии задачи Clique Problem (Div 1, B) заменить на 
, то получится более сложная и инересная задача.
На решение этой модифицированной задачи я и потратил почти всё время на соревновании, из-за того, что спутал ≥ с ≤ ... Но решил таки! и написал даже свои рандомизированные тесты для неё, чтобы разобраться почему решение всё время валится на претесте 3... <рукалицо> В конце-концов разобрался, жаль только, что на решение правильной задачи не хватило пары минут.
А я именно эту более сложную и интересную изначально решил и отправил, ведь единственный сэмпл подходит под это условие...
will you post the editorial ?? the problems were really hard for me :3
Кстати, насчёт обновления инфраструктуры: тут, кажется, стало происходить что-то странное при попытке оставить комментарий. У меня не получилось оставить ровно один комментарий (потому что я тыкал на "отослать" несколько раз, а потом зашёл на страницу с другой вкладки и увидел 2 своих коммента), и, как я почитал ниже, у некоторых людей тоже. Это я такой социально пассивный, и это на самом деле было всегда при больших нагрузках, или только с сегодняшнего дня?
In problem 527B - Error Correct System, what would be the correct output for the case:
10318065 this Accepted submission gives:
Is it ok? Zlobober
sankear, malcolm, MikeMirzayanov
We will add investigate this test and probably add it, thanks.
I also thought on this problem, too.
Didn't realize why 10315968 got accept until reading this thread. My test case is:
I thought the correct output should be:
But the below output also passed:
The problem says it must be "as small as possible" not just "reducing some".
Will system testing run again with more comprehensive test cases?
Never, for sure! past is past! Codeforces always thinks about future! :D
This contest is just a disaster. Problem C in div1 is written so badly. I am just shocked how could the author write such a long dummy boring story instead of just a few lines?
And the problem D has a wrong pretest, which lead to few people passing, and more contestant are scared and won't read the problems at all!
Because such failure in both C and D, I suggest an unrated contest for all div1 contestants.
The storyline is okay. The world would be boring if every problem has a description like "Given blahblah, you need to find blahblah". The real problem is the key point was hidden in one or two unremarkable phrase, make it difficult to understand.
I (blindly) guess that the original problem statement was written in Russian and this is a translation issue.
You are right. Russian statement was very clear.
Unrated contest because of long statement? Isn't it too forward? Indeed some people were affected by wrong test, but that is a small amount and most of them ended up with a decent position, so it is not helpful for them to make contest unrated :P
I strongly disagree:
1) "And the problem D has a wrong pretest, which lead to few people passing, and more contestant are scared and won't read the problems at all!" — problem D is expected to be pretty hard and most people in Div1 know it, those who decided to try it and actually got a solution are very small amount of all Div1 participants, and those who didn't try it — didn't even realize that there was a wrong pretest. Of course it's unfair for those who've tried it, but an option to unrate their participation is available, so why make other people (like me) who didn't even attempt the problem unrated?
2) Problem C while a little bit confusing had an amusing story and the pictures cleared it up for me. I think if you read it carefully you would also find it understandable. The problem is very nice actually and I enjoyed coming up with a solution for it even though I couldn't debug it.
I agree with 1st point. I misunderstood problem statement of C and tried to solve a different problem, until I saw the announcement :(.
Like! But I really don't wanna this contest to be unrated. I believe many contestants having the same idea with me.
I used to think 40 minutes is the longest time for me to understand a problem...until I spent almost one hour in reading problem C again and again
Hah, yes, that one was pretty confusing, I needed to read this many times too :P.
Why you finished testing div2 before starting test div1? We can self test by submitting div2cde and we can message you to unrated if there's something wrong in the programme.
I think that the unrated option is only in case the test for Div1 D affected you and the code for Div1 D cannot be submitted in Div2.
If my ab are wrong and I have submitted d using fft, then I will certainly try to be unrated
Finally I know my program of finding Euler's circuit used several times is O(nm). What a sad story.
А когда планируется проверка div1?
Zlobober why my rate still the same .. is it unrated contest
Give me a treat, your rating is increased! Your rating change
What a fantastic round for Poland! Never seen such performence earlier! :)
Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... :D/
Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... \:D/
Thanks Dear happyBirthDayBeni ... ^_^ I was really surprised ... I love U ... \:D/
I have a question about the next contest:
"VK Cup 2015 — Round 1 (online mirror, Div. 1 only)"
Can a Div. 2 contestant take part in this contest?, at least 'out of the competition'?. Thanks.
I was afraid to become orange when I finished debugging C 30 seconds after the contest has finished.
Indeed a close call :D
can i have some help on Div 2 D it gives WA, first sort due to coordinates then the idea is to run dfs from (n-1, ..., 0) considering that (i, j) is connected if (x[i] — x[j] >= w[i] + w[j]) and we know that if (i<j<k) & (i, j), (j, k) are connected then (i, k) is connected and maximize the counter this is my code where is the wrong part ?!
During the contest, I thought bitset couldn't be used to solve problem D. Its complexity is
, and I thought it would take at least 10s.
However, after the contest, I found it could pass system test actually and took about only 1.5s.
How can it be so fast......
I still can't understand what's the meaning of div1C...
How mutch time are working lower_bound on set? My solution was fall where I used lower_bound on tl on 11 test... I am about task C...
lower_bound(s.begin, s.end(), a) — O(N) or O(N log N)
s.lower_bound(a) — O(logN)
http://codeforces.me/blog/entry/16996 the problems were nice but the pretest 19 for Div 2 problem B was glitchy. for pretest 19 I got the answer(output) for the minimum hamming distance to be 524. The output given by the codeforces system too is shown to be 524. but then next line i am shown this error :
"wrong answer value presetned by contestant is different from the actual hamming distance: contestant = 524, actual = 526"
even though before this the pretest logs show this:
Test: #19, time: 46 ms., memory: 32 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input 1000 bbabbaabbabbabababaabbabbbbbaabbaaaabbababbaaabbabbbabaaaabbabaaaaa....
Output 524 1 2 Answer 524 999 1000
so my output matches the system output yet i was given verdict of wrong answer...
I believe it means the 524 doesn't match with 1 2
Although you give the correct answer, but the index of i and j are wrong
EDIT: changing
print i+1, j+1toprint ind[i]+1, ind[j]+1will correct the problem, but result in TLE. The double for-loop makes this approach very slow. The complexity is O(N^2)i checked other peoples code too they have given answer 524 but the second answer is different from what the system has given but even then their answers have been corrected.
The second line can be different because multiple answers could exist.
In your case, you answer is wrong. I have corrected it for you in the last post.
EDIT: To be specific, the minimum value after at most one swap is indeed 524, but exchanging the letter at index 1 and 2 won't achieve the minimum, it was 526
yeah i see now.. thanks
the error did not show up in all those 18 pretests lol
You can look at my submission 10333076
Editorial?
http://codeforces.me/blog/entry/17020
For div2 C, I just used priority_que and set to simulate cuttings, and got AC.10325360 But I made a data: 200000 200000 199999 V 1 V 2 ... V 199999 I run it locally, write the output to a file and got nearly 4 seconds..(turn off the output, and got 1.9 seconds) 199999 pops and 399998 pushs in total.. So that was really lucky..
some1 needs to do something about these fake winners,i mean unrated
I am waiting to be able to solve at least two out of Div.2 C/D/E . Then I will submit. What do you mean by fake?
Now that I read one solution to Div.2 C , it seems so easy. Why didn't it click earlier? :(
Because your account is fake!!
Где в условии задачи B говорится о том, что ответ может быть 1? Если вес вершины не равен 0, то нельзя сказать, что она удовлетворяет заданному условию.
Мое решение как раз из-за этого и не зашло, класс..
http://en.wikipedia.org/wiki/Vacuous_truth
В условии не упомянуто, считать ли вершину связанной саму с собой, поэтому я подставлял j=i в неравенство из условия и получал:
0 >= 2*w_i(для формулы тоже нет ограниченияi != j)Ну у вас 1 вершина, она не соединена с собой ребром, как вы сейчас показали.
Далее нужно понять, что 1 вершина — это клика.(... что любые две из них соединены ребром в графе G).
Я воздержусь насчет обсуждения того, ясно ли из этого условия, что это д.б верно только для различных вершин, но все равно 1 вершина — ничем не особеный случай ибо, если мы захотим проверять это условие втч для совпадающих вершин, то никакое непустое подмножество ответом не будет являться, но вас не удивляет же, что ответ может быть равен 2
editorial ?? Its taking too long.
When will the tutorials be available for div2 problems?Especially for C,D,E problems.
А разбор где?
I am still stuck on Div.2 E:
Idea so far: Start with the original graph. I. While there is a pair of nodes with odd degree add an edge between them. (Observation: because of the pair of cables condition we need at least that many new edges.) II. Find an eulerian tour. Create the graph defined by that tour. III. Follow the tour and whenever we leave a node with odd indegree / odd outdegree reverse the current edge to fulfill the pair condition on the node we left. IV. When we are back at the start node it's in/out degree might have become odd. In that case add a self edge to that node.
And here I am stuck: Does this give an solution or might it have one edge more than a solution? Maybe trivial and I just don't see it.
Here's a nice explanation
Oh, thanks. Silly me didnt notice those posts above.
can't see the editorial :( who can help me explaining the DIV2-B case 1&2 ,why both of the output is 1.
You can see Here
I really enjoyed the problems although I was to noob to manage to solve C,D,E div 2. A friend told me that in order to solve them I required to know FFT. Can anyone explain me the solutions to these problems based on that algorithm?
Indeed, your friend was right. Here you can find some applications of the algorithm called "Fast Fourier Transform" http://en.wikipedia.org/wiki/Fast_Fourier_transform .I hope this helps.
where are the editorials
http://codeforces.me/blog/entry/17020
Where is the editorial?