Всем привет!
Рад сообщить, что завтра днём в 12:05 по Москве состоится Codeforces Round #345. Раунд составлен из задач первого тура X Открытой олимпиады школьников по программированию, который состоится завтра же в это время, а также нескольких задач, подготовленных специально для раунда. Раунд был подготовлен силами научного комитета московских олимпиад по программированию под руководством GlebsHP, romanandreev и вашего покорного слуги, а также fcspartakm, который помог нам дополнить комплект задач до полноценного раунда.
Соревнование пройдёт по обычным правилам Codeforces, вам будут предложены 5 задач на два часа. Да, раунд рейтинговый :)
Обращаем ваше внимание, что из-за проведения основного тура системное тестирование и дорешивание будет отложено до 15:35. Также просим воздержаться от обсуждения задач в комментариях в период между концом тура и окончанием основного тура олимпиады. Все комментарии с обсуждением задач будут тереться, а особенно настырные нарушители будут наказываться. Благодарим за понимание.
UPD Приносим прощения, начало раунда было сдвинуто на 12:25 по Москве. Нелёгкое это дело — проводить онсайт-соревнование и раунд на Codeforces!
UPD2 Можно обсуждать решения! Системное тестирование будет запущено в ближайшее время.
UPD3 Наконец-то появился разбор: http://mirror.codeforces.com/blog/entry/43677 Приносим свои извинения за задержку с публикацией!
And Zlobober's serious work to get the first place in the contrib list!!
Nice tag (best way to spend Monday)!! good luck;
But seriously though, who holds olympiads on Monday mornings?
I can't imagine a better way to start your Monday.
great minds think alike.codeforces makes my life better
too bad difficult to hack!
please change the contest time in this time in iran we are at school and we have Combinatorics class with Dr jamali (for informatics olympiad)
At any other contest time , someone else in the world might have Combinatorics class with Dr jamali (for informatics olympiad) . Ever think about that ?
Well, I doubt Dr. Jamali goes around giving Combinatorics classes the whole day, every day. For sure Jamali must take some time to rest, teaching must be exhausting.
It could be worse. It is going to be at 6:00 AM in my country.
3 AM here, and school on the same day. :)
It is a egg pain. I didn't found another better translation hahaha
Ohh
Same here!!
A better reason to leave Lecture :) .
Russian contests are always good!
Specially when this team( Zlobober + GlebsHP + romanandreev) are authors !
First thank all people who prepare this contest. But i think the start time of contest is not good for iranian coder (or maybe for another coders who live in another countries too),bacause on this time we are in university... :(
oh my god!why vote negative??? :O
because it's CF :D
i can't believe this (O-O)!!! why???! 19 negative vote !!!for what??? -_-
Because every time will be good for some participants and bad for others. This time you had bad luck, other times the contest will be in good time for you and bad for others.
Life is hard
i just said its bad for IRANIAN coder!
you'd better stop commenting :)))
No matter what time they set the contest to start, it would be inconvenient for someone somewhere in the world
I can upvote your very useful comment
Please postpone contest, I'm still at uni :'(
10 minutes delay, they did what you want :)
UPD: another 10 minutes, please come home quickly
Just came back from school and about to start the contest. I like these rounds with unusual times because I can actually compete on weekdays. Normally, they're hosted at 10 pm or 11 pm in my country's time :(
I'm agree with you :)
I agree*
I am disappoint.
You're Errichto.
And you're not.
I'm FamIsProud.
Arguably 10 or 11pm is better than 3am :P
Rating!? Oh no! Sad end for my cat...
My rating's just like mountains... :(
Mine looks like shit hahaha
the timing of the contest is probably one of the best timings for competitors from Korea; it's 6pm; an hour or two from now (so, 7pm or 8pm KST) would be ideal.
It's 3am on a weekday in the US :P Oh well, better than 10am — at least I have a chance to participate. Looked like it got bumped back 10 minutes though.
Кажется, Petr-у тоже нужно делать CF раунды
delayed for 10 mins
delayed by 20... :(
I'm disappointed too. It was just that I would complete the contest and go to school, now I have either to skip the first class or solve for only hour and a half :(
Why are you disappointed? you have a reason to skip the first class now :D
You might want to tell this to our history teacher :)
History is a lie, Contest is real :D
You want to attend history class! what's the matter with you :D
when I was in school I always skip history classes even if there's no contest :D
We have a badass among us
Really you have badass among your school?
If it were about a Math or Info or Physics class, maybe he would have been more rational, but in this case, man, I'm sorry for you :))
All of you didn't understand. My history teacher will surely kill me for being absent(it's sad because I'm a math/informatics competitor, history is one of my worst subjects :)) ).
暴走漫画。。。。。
no zuo no die
Hey guy ! why so many people got unhappy with you !
Because it's CF :D Maybe most of the people who got unhappy with him is Chinese. Why? I don't know QwQ
All are unhappy with anyone comments in language different from English..
I'm sorry.I don't konw it before.
"know", not "konw"
My English is not good...
Выходит что школьники могут запалить задачи до тура?
нет конечно, "и дорешивание будет отложено до 15:35" Значит тур начинается где-то в 10-30 мск. твой кэп
Первый тур Открытой олимпиады стартовал в 10:30 мск. Так что скорее участники на CF могут запалить задачи до раунда. :)
Guys, I must go to school today ;)
Same — could've gotten 20 mins more sleep. Some of my classes probably are unimportant enough I can use them as nap time though :) Bets it will be delayed 30 mins?
5pm in China. Hungry... Please start...T T
but it's so nice to take part in the contest during the day for Chinese=w=
exactly.
I haven't slept all night last night and Just got back from my university to participate in this round :D
I hope there will be interesting problems.. I am feeling like being Div1 for a while :p
such high , much wow all the best
For me writing after a sleepless night is premise for falling rating=(. Hope it is not your case, good luck
Well... I'm not in my best shape.. but I need to get used to coding in stressful environments, because I am preparing for ICPC WF this year, which is my final year as a contestant :((
any way I only hope the problems are enjoyable that's all :D
I'm feeling the same as you and dropped from #150 to #800 due to int overflow in the last contest T.T
I'm actually glad for the delays :D now I can change my clothes and get into my comfortable pajamas, drink a cup of tea, as well as write this comment :D :D
you did it :)
Yes! Thank you ^_^
I Also got my best rating so far with 1944 points :D
Why are you delaying the start time? u.u
Probably due to Onsite Delays? Just a random guess >(
onsite started much earlier, because duration of onsite is 5 hours
10min delay?!
We can, we do, we practice :(
Another 10 minutes? :O :/
On one hand if I complain about timings, Russians will downvote me, on the other, if I don't and still participate I'll miss my lunch(and get downvotes). Hmmm.....what to do
Keep calm and code :p
I'll have lunch lol. Virtual contest ftw :D
My first time to participate a CF round sync w/ onsite.It's cool!
Should I compete? Because I am in a Lab class and my teacher gave me an "1 hour break!" for completing the tasks early.
Waiting for the next delay :P
Exactly.
what's wrong with the hacking? nothing shows up when i try to hack (sorry for my vulgarity on my previous post).
Its because you shouldn't be hacking. Solve problems, go go go!
I have a similar problem. Pretests passed but cannot lock! Neither is it showing on the dashboard.
It was unuvailable for ~10 minutes. It affected all the participants, so all of you have been in the same conditions. Sorry about it.
Wow.It seems that there are many guys who are unsatisfied with the long time of waiting.
I wonder, who downvoted the boss???
Some brave and cute guys.
cute you are=w=
We are all cute.=￣ω￣=
WOW! How cute you are!
doesn't matter it seams every minute it resets to zero :\
some mysterious power...
maybe mike is giving himself upvotes, lol
Be careful with what you said.Maybe there's something happening to yo.
mike is free to do anything here, did you know that?
We all know that.But I am careful to say it out.
don't be afraid of downvotes, be honest :)
To be honest,I give him a downvote.
Планируйте ли провести раунд в кф завтра по задачам второго тура X Открытой олимпиады школьников по программированию ?
Заранее спасибо.
К сожалению, мы не успели подготовить лёгкие задачи, чтобы дополнить набор до полноценного раунда.
Так дайте acm style div 1, там будет пофиг, если не будет легких задач.
Руки бы отрывать за такое:
#define int long longДа, хитрые парни. Я уже раньше встречал такое, так что проверяю теперь все дефайны :)
Причем я его взламывал не потому, что у него
int ans, а потому, что он в одном месте пишет1LL * sum * (sum-1), а в другомsum * (sum-1).Хитрые? Так просто удобнее в 100 раз, я тоже всегда так делаю, когда нужны long-и. На всякий случай добавляю коммент с WARNING-ом, правда, но не уверен что это кому-то помогало =)
Can somebody explain me this .What is wrong with my generator
First time i solved C in contest . guess what i solved B and C. and 4 WA on A and could not get AC. Awesome problemset :)
I think it is because of unclear statement. Almost sure it is the case if you get WA on pretest #7.
Can somebody explain me This ? Whats wrong with my generator .
This link takes everyone to their own hack section, not yours.
sorry LINK
Did you even compile it? Line 20 is missing a semicolon.
What does this line do ? o.O
printf("0 0\n",ans,ans);Just print 0 and 0, nothing to do with 2 "ans"'s
The statment for the second task is pretty clear, but again I spet 30 minutes to understand problem of the task :D
we should wait till 12:35 for system testing,right
when will system testing start?
In an hour from now as I understand (15:35 MSK).
We kindly ask you not to discuss problems or solutions since the onsite round is still running. We will notify you when it will be allowed (approximately in 2 hours). Thank you!
Мы ещё раз просим участников не обсуждать задачи и решения пока не закончится основной тур олимпиады. Мы сообщим, когда станет можно (приблизительно через 2 часа). Спасибо!
UPD Thank you for your understanding! You may now discuss problems and solutions. System testing will be run shortly.
UPD Спасибо за понимание! Теперь вы можете обсуждать задачи и решения. Системное тестирование скоро начнётся.
Two questions:
When will start testing ?
Why disscussing is so important, when everybody can see codes from other participants ?
Exactly..
I guess that the onsite contestants cannot have any kind of communication with the outside world..
So why bother stop discussions here? I can't see the point in doing so :\
I can see the other's solutions.
Any updates on system testing now ?
Не знаю почему, но мое решение по задаче A отправилось 2 раза подряд — одинаковый код и получило accepted. Кажется, так не должно было быть! (посылки 16564899 16564896)
i still do not understand the problem statement for division 2 D, but judging from number of people who solved the problem, perhaps it's just me who is confused about the problem statement.
Seriously? -_-
So, were there edits in the problem text?
Let me clarify this. We actually received a question pointing to the typo in the statement (the word "has" was obviously an extra word there) and we fixed that typo. After 1.5 hours of contest we received the second question about the mistake in this problem and we didn't even think that you are talking about that mistype. After all, it was a small typo that doesn't affect the understanding of the problem, and we fixed it 1.5 hours ago, we almost forgot about it.
Of course we didn't have any intention of lying to you or whatever.
Okay, thanks .
What is Compilation error? I lost much time because of that...
Are you kidding?
I had not gotten Compilation error and today is first in Codeforces. So i don't know Compilation error well.
I only know this.
struct A ={a,b} => Compilation error A.x = a, A.y = b => Correct
{a,b}this would work withstd::pairnot withstructThere is no = operator by default for custom structs.
You are wrong. It can be auto-generated by compiler.
Yes, there is. In C++11.
Click
You didn't write constructor for two int values. So compiler doesn't know what to do. Click
The problem is that you've written you own (empty) constructor for your struct. If you'd write no constructor, just:
it will work.
Candidate master asking about Compilation error >.<
Ya.. Me too..!! And can you believe, they are asking us to code a solution.!!! I lost so much time in that.!
http://bfy.tw/4cfa
I haven't participated in the round, so I'm not really interested right now to hear the discussion of the problem, however I find it pretty weird how discussion is prohibited, yet all solutions are publicly available.
Probably a mistake? Just posting so the CF team can be notified.
A bit difficult for me.But I'm sure I can do better.hard work will pay off!
Also!I'm not in my best condition. I got Wrong answer 2 times in A and C,and 1 in B. Oh my god!I lost 250 point! Even more...the Internet shut down in the contest.
first time take part in div 1 =w=
Ah, Me too ^v^
Had someone div2 C WA 3? Can't understand where is the problem.
Did you check that your code does not count any pair twice?
i did
Int can't afford the limit. so you should use long long to record the answer.So did you check it?
here is my code http://pastebin.com/hs3H83qJ, I just gonna die waiting sys tests
ohhh, now I've got it. I counted all copies with same y, and then decrease the answer as they all been at same poit.
I Can't Wait... When will the Final test...
Beresta said:
In an hour from now as I understand (15:35 MSK).
It's in the announcement: "Note that because of holding the main onsite round system testing and upsolving will be available no earlier than 12:35 UTC."
What is reason that we are still wating.
'the reason'.I'm sorry.
Protip: you can edit your comments by clicking the button that says "Edit" (surprising isn't it)
why are you waiting? you didn't participate as I can see.
You saw wrong, pal.
available NO EARLIER than 12:35 UTC...
Only GOD knows how much do we have to wait.
It's 12:52 UTC
The haven't promised when the system testing is...
Quite funny picture...
Тот самый злобный коммент: где систесты???
Ждем окончания офиц. контеста, и сразу после этого старт.
Не томите меня, душенька. я хочу знать свой результат
Round must be made unrated. We couldn't hack or lock solutions for ~10 minutes.
Seriously ??? unrated because of 10 minutes not able to hack???
http://mirror.codeforces.com/blog/entry/43615?#comment-282978
.
Believe that you'll solve more problems in next contest!
As systest is not running, everybody should give a chance to submit problems that went wrong in pretest. just asking.
everybody should give a chance to submit the problems that went wrong in pretest as system test is not running. just asking
Так это уже можно начинать обсуждать или еще нет? Мне интересно как Д решать.
del
Прошу прощения, перепутал задачки
Основной момент тут — что решение может получиться проходом вправо до определенной фотки, а затем влево через первую и дальше (либо в обратном порядке — сначала влево, потом вправо).
Дальше можно в цикле идти от первой фотки вправо и проверять как много фоток мы можем захватить с левой стороны (я использовал бин поиск, но можно и линейно).
Я вызывал солвер два раза с реверсированными строками (1 2 3 ... N и 1 N N-1 N-2 ... 2). Не уверен, что это необходимо.
Why do codeforces problems differ so much in nature from ICPC problems? I think ICPC problems are too hard to think :/
Not really... You should compare ICPC problems to Div1 contests. and both are pretty darn hard :D
I believe Div2 contests are comparable to easy regionals
You should also consider teamwork in ICPC and much longer contest time (5 hours). This means more problems can be solved.. So can you see why it requires harder problems to make a good ICPC contest?
How effective do you think Codeforces problems are for preparing for the ICPC? Am I better off focusing more on solving on SPOJ, UVa, etc?
Куда пропал статус?
system testing started ! hold your nerves !
System test is started. Feel free to discuss problems. Sorry for delay.
===
Системное тестирование запущено, можно обсуждать задачи! Приносим извинения за задержку.
How long to wait for editorial ?
I'm sorry but this will be a round with delayed editorial. All editorials for problems will be posted no later than March 9th, most probably on March 8th evening.
You may find brief ideas for the problems by simply asking in comments for this post.
When can I view other people's solution?
How to solve C? please someone tell me briefly
Briefly — after simple math (square, equal, cut) we get that valid pairs have either equals X or equals Y. Put every value in counting dictionary/set/whatever and get sum.
I did that but still got WA on 28th testcase. :'( I found all possible pairs with same X and added it to number of all possible with equal Y and subtracted pair which has both X and Y same.
Maybe overflow?
No, I did use long long. http://mirror.codeforces.com/contest/651/submission/16577339
I think you are doing multiplication before typecasting here
ans += (long long) (k*(k-1))/2;which is why you have overflow.Yes overflow!!!! I added only 4 characters and got AC.
That's overflow. We all know that feel.
I couldn't participate, but I have read the problem and I think you can use a hash table (C++ map) for X and another for Y, and count how many individuals have each X and each Y. Then traverse all those keys and for each one, if the count is N, add to a global counter N * (N — 1) / 2, which should be the number of pairs you can make out of N watchmen.
Then you should make sure not to count twice or to subtract the individuals which are the same X and Y, which should not be difficult.
And as somebody said in another comment, use long long.
While it took me about an hour to read, think and code Problem C, someone on earth solved it in 0:01 min.Just saying.
Well tourist is a tourist.
Welcome to Problem D test 35 .
What was the hacking case for A?
For B it was int32 overflow.
UPD: Damn, I've messed with tasks again. I meant int32 overflow hack case for C.
For Div 2 C it was int overflow.
For A, I hacked two solutions with this test :
1 2Damn these overflows got me again on C. Need to still wait more to get 4 correct in a Div 2 contest :(
WA: http://mirror.codeforces.com/contest/651/submission/16569379 AC: http://mirror.codeforces.com/contest/651/submission/16582445
I should start to use #define int long long probably
You would get Compilation error
The function main must return int value
i did it once, and costed me two hours of debugging :3
use signed main()
Me too :( F***ing overflow.
Why can't I see the tests?
I can see solutions of div2 but not of div1!
I need some help regarding Div2 C.
I did it following way:
I found out the number of distinct horizontal and vertical lines and count of number of points for each horizontal and vertical line. After that simply we can form pairs for each line by using n(n-1)/2 and keep on adding it to the final answer.
But I've a problem that this way I can't remove the duplicate points and each duplicate will be added twice in my answer.
Any suggestions regarding a faster method to find similar points? (The best I know would be simple brute-force and that will be running in a time which violates time constraints?)
Use another map to count number of points in the same position (can use
map<pair<int,int>,int>), then for each position, subtract the result for n * (n - 1) / 2 with n is the number of points in each position.I used a
map<pair<int,int>,int>. You could also sort all the points by (a.x <b.x) and by (a.y < b.y) when (a.x == b.x). After that you can count how much points are equal in O(N).If you code in C++ read about
std::map.I didn't use map and got AC with arrays. So, one array of pairs for (x, y), two arrays: one for X and one for Y coordinates. Sort them all, and then you can calculate easily how many of them are with same X or Y coordinate, while tracking how many of them coincide.
16585770
Thank you for fast rating updates :D
Waiting for system test was like riding a roller coaster for me. And I did have GREAT fun when I knew the results!
Memory Limit 256 MB , memory used 255 MB
255200/1024 is around 249.2 Mb, so you still have a lot of free space :)
Check submission by V--o_o--V — he used 260700 kb :)
He also used 262100 kb and got ML, even if 262100/1024 == 255.957 :)
16582815
Pretty close TL, huh
Congratulations to tourist on his best performance ever — today he got +172, beating his previous record of +162 (which was set back in 2010, in CF Round #8).
One more round with such inflation and we'll see 4000+ :)
Feels wrong that #1 person placed #1 in tournament get so much points.
Why TooDifficult got only 84? Its 2 times lower.
He got 2 times lower place :P
I think it's because the round was really stacked because of the time; a lot of great asian coders participated who couldn't otherwise, and only the more dedicated coders from other continents participated (or the ones who don't have school this week hehehe)
Bredor where is your scrincast with russian rap?
Будет ли разбор(когда)?
In my previous CF Div2 (#343) round, I managed to solve only 1 problem and had a ranking of 2400. Today I could successfully submit 2 problems and had a ranking of 1700. Which implies an increase of 700.
My rating still fell down today. I've no clue as to why is this happening!
Improves from previous round and still rating decreases! :SAD: :(
Well it seems you have participated in too little rounds for your rating to stabilize.
Also it is not really depends on the place number, but rather on the amount of participants, their quality (rating) and your relative position among them. E.g. if contest have only 100 participants and you placed #100 — its worse, than if contest have 10000 participants and you placed #8000. But also if in first case other 99 would have rating of 100500 you probably won't lose anything (maybe even get higher), but if everyone of them have rating of 0 you will fell down pretty heavy. Hope you got the idea.
What do you love more — Problem Solving or seeing positive rating changes ?
Problem E turned out to be surprisingly simple. For example, in the example below, the following works:
(We need a slight modification when the two trees have common edges, but this is not very hard.)
I don't get it. What is the pattern I should see from this example? I am very curious how to solve E because it doesn't seem that hard (you have a lot of freedom when doing operations), but still, I am unable to create an algorithm that works all the time. Can you explain exactly how you solved it? (just the main ideas)
The main idea of one of the authors solutions is working with leaves. Consider a leaf u with its edge (u, v) in the first tree. There are two cases: if the edge (u, v) is present in the second tree, it should stay as is and we can contract this edge forming a new vertex uv in both trees. In the other case we should find any of the edges going out of u in the second tree, let's call it (u, w), and replace (u, v) with (u, w), and after that contract u and w. Note that all v, u, w may be contracted vertices and should be dealt carefully (in particular, the endpoints of removed and newly added edge may be distinct though they belong to the same contracted vertex u). This leads to an O(nα) solution.
I am a cai bi.Nice to play with you.
It seems that smth is wrong with Java invocations. If the parameters are set correctly, it should be impossible to get ML in this language: it will be either TL because of long GC, or RE because JVM cannot allocate more memory. However, I've got ML for the following solution 16574238. It consumes at most (1M (input) + 2M + 2M (edges) + 1M + 1M (dsu)) = 8M int's, 1M boolean's, 1M ArrayList's of total size up to 2M, 1 ArrayList of size 1M. In total it is up to (8 * 4 + 1 * 4 + 1 * (8 + 4 + 8) * 2 + (8 + 4) * 2)M bytes, which is way below 256Mb. Of course there are plenty of temporary variables, but they should be safely garbage-collected. Unfortunately it doesn't show me the test, so I cannot debug what's going on there.
So the question is, how are memory params (-Xmx etc.) set for for Java on server? If they're set consistent to the problem ML, then MLE verdict should be impossible. Am I missing smth?
And another data point. Apparently GC behavior on server is very weird. E.g. the following code:
consumes 194Mb as expected. But the following code
consumes 472Mb! And another experiment: the following code
consumes 292Mb.
This essentially means that if GC triggers, all ML's for Java are divided by 2. I think Java/GC configuration on servers needs some serious adjustments...
I remember someone already pointed out in comments that CF uses Xmx 512MB.
Also this submission: 16585600 and 16585728 looks like Xmx is indeed 512MB.
So, the memory limit verdict happens when the launched jvm goes OOM?? As such -Xmx corresponds to the max heap memory, apart from this there are other sources of memory consumption for a java process, Different GC policy for sure would reveal different memory usage pattern, like in JAVA8 if you call System.gc() in a loop when G1GC is your garbage collection strategy then you would observe that the given java process keeps on incrementally consuming more and more memory without going OOM (consumed memory might be part of native memory area.)
Can somebody post brief explanation of Div.2 E/Div.1 C ?
How to solve Div2 D ?
First precalculate how much time it would take to reach from 1st picture to ith picture while doing right swap each time for each i from 1 to n. Similary calculate time to reach from 1st photo to last picture while doing left swap each time.
Then for each position from i to n while going right, you have to find the maximum position you could reach on the other side (left), this could be found using binary search. Again the same for left to right.
Complexity: O(nlogn)
My solution: http://mirror.codeforces.com/contest/651/submission/16580683
I implemented this too, but I think it's possible to do in O(N), because if you try to find the max position you can reach on left, for each i, then it will be at most the position for i - 1, and hence you can use something like a two-pointer technique (or sliding window if you prefer that analogy) to do it in O(N).
My idea is same as polingy's 16577590
anyone can tell me the tecnique of div2 c ? plz...
Manhattan and euclidian distance between two points is same when at least one coordinate of both the points is equal. You can prove this by equating both equations. Then you can use map to store count of occurrences of each x and y coordinate. Use another map to store count of pair(x,y). You can find answer by adding gC2 for each x and y ( g is the count of occurrence of each x and y coordinate stored in map). However some points may be repeated in the input and so you will add those pairs in the answer twice once for x coordinate and once for y coordinate. So just use the map used to store pair(x,y) and for each point subtract countC2 from answer ( count= number of times given point appears in input).
soln : http://mirror.codeforces.com/contest/651/submission/16566465
First, let us assume
A = |x(i) - x(j)|andB = |y(i) - y(j)|. Then, Manhattan's distance =A + B, and Daniel's distance =sqrt(A ^ 2 + B ^ 2). Solving this, we get2 * A * B = 0, which means that either A or B is 0. So, all such pairs of points which have either the same x-coordinate, or y-coordinate are to be counted. So, we sort the array according to x-coordinate and then for each unique value of x, if the number of points have that x is N, then we add to the total the valueN * (N - 1) / 2as that is the number of ways of selecting 2 points from all N points(NC2). Then we do the same for y after sorting the array according to y-coordinate. But, here there will be 1 problem that we will have counted those pairs twice which have both the x and the y coordinates same. So, to remove this, for each point having coinciding points, if the number of coinciding points is M, we subtractM * (M - 1) / 2from the total.wow,,,thanks bro
no problem :)
It's already frustrating...In div1, we can't see sources or tests. Please fix this issue: I really want to find my bug in div1D
Again failed C because of overflow ( lost 1200 points ).
What do you do to avoid overflows ?
I tried
#define int long longbut thats throws an errormain() must return intI don't use it but you can try this:
Or you can use
int32_tinstead ofint:It is better to define (before the contest)
and just use
lleverywhere instead ofint(except main() type, of course). Speed disadvantages are minor, and at the same time you will get overflow very rarely.Hell No !
i remember getting lots of ML and TL because of this the best way is to use ll only when it is needed but when u wrote ur code and u suddenly find out about the overflow u can simply define int long long and change int main() to main()
Probably on some hard div1 problems (C-E) you can improve wrong solution from ML/TL just using int where long long is redundant. This problem seems unlikely to me on div2A-D, it can happen only when your code is very suboptimal. I'd like to see counterexamples if I'm wrong.
Well since you asked for a counterexample :P
ML exceeded code(in method solve2) : 16439466
Accepted code(just changed type of array
boardfrom long to int in method solve) : 16439508PS : the method names are different because I had just removed the unused method solve before submitting again.
You have three big arrays: Cross[] allcrosses, long[][] board and long[][] sum, other are not greater that a couple of MB. It is interesting why it is ML, because maximal size for each of them is 4*10^6 elements, long is 8-byte and Cross is 4+4+8=16 bytes. So total used memory should be ~4*10^6*(8+8+16)=128*10^6 bytes. In theory. Maybe I don't know something about Java to configure the cause of this doublesizing in practice.
However, as I said, ML here is the result of suboptimal solution. You needn't store all crosses, only positions and values of the two current best crosses.
could someone here explain what division 2 D / division 1 B is about? i had a hard time understanding that question and still have hard time parsing the problem. in particular, in the beginning is all the images in vertical direction? so only cost you spend is when we need to rotate image that is in the horizontal direction? i'd imagine you need to go left or right depending on some kind of 'measure.'
what's the solution concept? is it some kind of dynamic programming, or is it something completely different?
I didn't solve D but I can answer your queries about the problem .
You view the images on a phone which is initially in the vertical orientation , so if you encounter an image which is of the opposite orientation than your current phone orientation you need b seconds to change the orientation of your phone .
UPD: My bad !
This is wrong, you are not allowed to rotate phone, only pictures. Trying to rotate phone because I read problem before clarifications is why I'm orange now :(
Почему 500000 в задаче E? Олимпиада вроде всероссийская, а не польская :) Сдать эту задачу на контесте на джаве, по-моему, было практически невозможно.
Regarding question C Watchman. Codeforces says wrong answer on test case 3 as wrong answer expected '33', found '39' But my computer machine gives the 33 answer and on codeforces the same code giving 39 answer on 3rd test case ..I also cross check on Iedone.com .It also giving me 33 but codeforces give 39 and hence not accepting answer ....please have a look to my submission no 16580949 or visit my submission ..pls help ..
Yeah, pretty weird. Let me check...
Did you find any error ?
It seems right. In my PC give 33 too. I don't know! Make sure you don't have unespected runtime error. I heard sometimes system give WA but is RE instead (also in ACM ICPC Regionals).
// while(i < n && v[i]==v[i-1]) // while(i < n && v[i].first==v[i-1].first) // while(i < n && v2[i].first==v2[i-1].first) remember to check the boundary when using while. BTW, I really don't like your coding style
I mean it IS obvious, but still... is tourist even human anymore? :/
Could anyone help me find the bugs in my code of Problem C(Div. 1)? It always got
TLEontest #14and I am confused about it....Here's the code, Click
You are not allowed to view the requested page
Когда выйду официальные результаты первого тура X Открытой олимпиады школьников по программированию ?
Заранее спасибо.
Is it possible to solve div2A with the formula? The 2 steps forward, one step backwards thing looks too darn familiar...
Click.
Thank you.
By the way, I've found an interesting solution that uses DFS!
div2A — DFS
How did you come up with that?
This is sentews2's code.
I don't know whether he'll answer your question, so I'll tell you my version of the story.
First, take a look at this rain water barrel:
You see, there are 2 paths for water to go out. The throughput of the lower tap is 1 liter per minute and of the upper tap is also 1 liter per minute. Let's imagine that, when we open both the upper and the lower taps, the barrel will lose 2 liters of water every minute.
Now, we'll do the following trick. Let's connect the upper tap with the hose and return that water, running from the upper tap, back into the barrel. On one hand, the barrel still loses 2 liters of water every minute, but on the other hand, the barrel now gains 1 liter per minute from the upper tap. This image clears the things out for me, so I can see that the barrel now loses 1 liter per minute in total.
The key moment, I think, is to consider the whole system. That is, how much water (or energy, in the case of the div2A problem) does the whole system lose? If we think about the joysticks as a single system containing some amount of energy, we see that the amount of energy contained in that system is
a + band the system loses 1 unit of energy every minute.If we could just drain the energy from 2 joysticks to 0, the amount of time the system would survive by losing 1 energy unit a minute is
a + bminutes. Since we cannot drain it to 0, when we are getting close to complete exhaustion, the internal structure of the system of 2 joysticks becomes important, i.e. the distrubution of energy between the two affects the answer. Exactly for this reason, we should also consider all the cases of relative energy distribution in joysticks (when energy is near 0):0 00 11 01 1I think it is simply a DFS on states! The states are acyclic you can prove it on the basis of transitions( They only take you to larger or smaller number) . Hence the states form a DAG. But there might be multiple ways to reach a state I cannot understand how is he taking care of that! I think if we can prove that the first time we reach the state, the value we maintain is optimal then we can prove his solution! Edit: Yeah If I change that max taking condition to work only when we visit the state at first it gives AC then too. So probably anyone who can prove the hypothesis by me can prove the solution :) Any Red People, correct me if I am wrong?
I was asking how to come up with this one http://mirror.codeforces.com/contest/651/submission/16563831
We can notice that: if the remainder abs(a — b)%3 equals 0, it would keep 0 after each minutes. Otherwise, it can change between 1 and 2.
For the first case, the final state is (0, 3) or (3, 0). (why no (0, 0)? because ever time the total energy would lost 1 percent, but we can't get (0, 1) or (1, 0))
For the second case, the final state is (0, 2) or (2, 0).
So the answer is max(0, a + b — 3) or max(0, a + b — 2). 16601248
I used a recursive function:16582603.
I wonder if tourist is going to reach 4k this month. Just looking at the slope of that curve.
Seems like new rating system is more appropriate for those who often takes top1. tourist did the same good for a few last years, but there is no such jumps on the graph like for last 4 contests.
Is there any editorials?
Bring a new rating category, tourist is close to breaking 4000 limit :D
Can anyone please explain the idea of Div1/C or Div2/E ?
build a graph G with n * m vertices that each of them correspond to a cell in the table. add an edge from vertex u to vertex v if u and v are in the same row/column and a[u] <= a[v];
now find every SCC of the graph and create a new graph H in which every vertex is a SCC of G. note that vertices of a SCC of G should have the same number in the final table. now find the topological order of vertices of H(I leave it to you to prove that there is a topological order for vertices of H). the vertices that are not endpoint of an edge(note that since the edges are directed, start points and end points are different), can be assigned value 1. erase those vertices from H and assign values to the other vertices recursively.
note that this solution uses O((nm)^2) edges to construct graph G. you need to use some ideas to reduce the number of edges(I leave it to you).
let me know if you need any more help.
I'm already sure that you forgot to let us the permission to see the tests or someone's else source (as we don't have the permission during the contest). Please let us. I've been looking for a bug in my source for a couple of hours and it'd be much easier if I could see the test (as we usually can). It's my third comment about this problem ans I hope someone will see it. I don't know where to post it...
badass is here for help
try this test
correct output:
I've just found what's wrong but I don't know exactly how to solve it now. I may have an idea but the code is already very hard to understand and it's very complicated what I want to do. I think I'm going to quit. Still, badass, can you tell me what is your idea?(BTW, I guess you've just found a new nickname :)) ) Actually, I'd like to hear ideas from anybody about div1D. It seemed really nice at the beginning(the answer is either M — 1, M or M + 1 where M is the maximal length of a maximal increasing subsequence). Now I've tried to check whether is M + 1 (this was easy). Now I have to check if it is M — 1 or, if not, to print M. But my idea for checking whether M — 1 or M is a solution is very hard and I'm almost sure that this is not the solution.
Let the length of longest increasing sub-sequence(LIS) in original array(before any update) be S.
we need to find for each element in the array whether it's included in at least of the LIS or not, and if yes does removing it will decrease length of LIS by 1 or not.
let L[i] be length of LIS ending in i and R[i] length of LIS starting in i
it's clear that if L[i]+R[i]-1 == S then element i is included in at least on of LIS, now how to know if we remove i then S will decrease or not?
it's a bit tricky, removing i will decrease S if and only if there's no j such that element j is included in at least one LIS and L[i]==L[j] (i.e. element i is the only element which have the value L[i] among all element which are included in LIS)
after we know for each element if removing it will decrease S or not it's easy to answer the queries now :)
I've just got AC. I made the arrays L and R as you said but for being sure wheter its elimiation decreases S by 1, I used some hashes(yep that's right=)) ). I just counted in how many ways optimal L or optimal R can be built and it should be equal to the total number of optimal increasing subsequences. Anyway, thanks :) I understood your observation and it is a better solution(because mine can give a wrong anser in case of collision)
LE: I've implemented your idea and got AC: faster and shorter code. Thanks :)
Nice :)!
Nice solution! I was struggling to get track of which element is in LIS during contest time, and finally came up with a weird method when the contest was over...
Hi, I'm looking for a big dick! <3
Need some help with problem C Round 345.Any editorial soon??
At first, solve it mathematically.
Set a = xi — xj, b = yi — yj
Result solution: We must to calculate count of x-coordinate and y-coordinate repeats, and calcuate unique combinations PROFIT!
P.S. Sorry for my english))
anyone can explain me ,, div2 D,,,,plz...
i make comulative sum,,, from first to last and then last to first ,,and the bainary search but some cases still mistake,,,
plz explain me what it says,, i am trying to read from first or reversly,,is it possible to start from center?
There are many details in this problem which need quite a bit of careful handling. You can find the cases where your program gets WA (either in the system test or created by yourself) and think it over, or take a look at others' code.
The announcement has div1 tag only. Can you tag div2?
Guys, please publish the editorial !!!!!!
My code for div2 C get right wrong for "3 1 1 7 5 1 5 "(the first sample) but get WA on codeforces... Could someone explain me that? Here is my code: 16575774
Just as compiler said: no return statement in function LL cal( LL x);
thanks... How silly I am..
Почему до сих пор недоступен просмотр решений других участников?
Странно, я могу без проблем
У div1 недоступен.
OMG !
still can't see others codes :|
When will the tutorials be available ?
The problems are very difficult to hack ,so very bad.
Someone can give me simplified version of 19 test in "D" problem (div 2), please. Or explain, problems with binary search.
Thanks)
5 2 4 13
hhhwh
Answer : 4
Please serve Editorials. Been a long wait.
Zlobober : " I'm sorry but this will be a round with delayed editorial. All editorials for problems will be posted no later than March 9th, most probably on March 8th evening. "
and here it is toturial
Hi I solved this problem without topsorting(it's implicit in my dinamic programming function "solve") and also I didn't use union find to compress equal values, I compressed all values at the beginning,then I made a graph with those values.
I can't see my mistake i was using my dinamic programming function in any order. I think It should work as topological sorting.
code:
have thought over it for hours still not able to find the testcase I am failing. http://mirror.codeforces.com/contest/651/problem/D
http://mirror.codeforces.com/contest/651/submission/16641326
Here is your corrected code: http://mirror.codeforces.com/contest/651/submission/16641625. It seems that in your last loop, you are forgetting that we must see image 0 before we see image n - 1. Also, you are forgetting the case where we only move left or right and therefore do not need to take a * (i + 1) seconds to move back to the first image. I hope this helps!
Difficult to hack！！！！！！！！！！ TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!TOO BAD!!!