### Блог пользователя _kun_

Автор _kun_, история, 5 дней назад, ,

Всем привет!

Летняя компьютерная школа (ЛКШ) — это летняя школа для учащихся 6-10 классов, увлеченных программированием. ЛКШ ориентирована в основном (но не только) на школьников, участвующих в олимпиадах по информатике — от начинающих до участников международных олимпиад. ЛКШ проходит в две смены (июльскую и августовскую), в каждую из которых приезжают около 200 школьников со всей России и из-за рубежа. Более подробно об ЛКШ можно прочитать на lksh.ru

Сейчас идёт августовская смена Летней Компьютерной Школы и 11-го августа состоится традиционная командная олимпиада ЛКШ. Мы рады представить рейтинговый раунд на её основе!

Раунд будет рейтинговым для обоих дивизионов, пройдёт в 11.08.2018 16:35 (Московское время), в каждом дивизионе будет 5 задач и 2 часа на их решение.

Задачи раунда и олимпиады были придуманы и подготовлены преподавателями ЛКШ: izban, achulkov2, Schemtschik, i_love_isaf27, senek_k, asokol, WreckingBall, burunduk2. Также спасибо Dembel за помощь с организацией олимпиады.

Спасибо _meshanya_, burunduk2, gritukan, niyaznigmatul, manoprenko за тестирование задач!

Спасибо MikeMirzayanov за системы codeforces и polygon!

Да, мы знаем о том, что контест пересекается с ProCon Junior на codechef. К сожалению, учитывая расписание ЛКШ, а также приближающийся финал VK cup, мы ничего не можем с этим сделать =/.

Желаем удачи!

UPD: На раунде будет одна интерактивная задача для обоих дивизионов. Пожалуйста, прочитайте пост об этом здесь: Интерактивные задачи: руководство для участника.

Поздравляем победителей!

Div1:

Div2:

Upd Спасибо за участие! В связи с проведением вк-кап пересчёт рейтинг состоится немного позднее обычного.

Upd Опубликован разбор!

Можете также обратить внимание на неоффициальный разбор, который написал neal.

•
• +342
•

 » 5 дней назад, # |   -37 Ok so now CF will host contests prepared for middle school students. Kill me now!!!!!!
•  » » 5 дней назад, # ^ |   +14 Don't underestimate the complexity of this contest :).
•  » » 5 дней назад, # ^ |   +7 I hadn't been surprised if you would solve nothing from a SIS hard olympiad :)
•  » » 5 дней назад, # ^ |   +2 Says the guy who has solved only two problems in CF and has rating <1500 (No disrespect to lower rated guys but being that arrogant calls for such a response)
•  » » 5 дней назад, # ^ |   +5 Why underestimate middle school students? There are quite a lot middle school students who rates more than 2400 on Codeforces.
 » 5 дней назад, # | ← Rev. 2 →   -8 This will hopefully be a good contest for those of us training for olympiads :)
 » 5 дней назад, # |   -18 Which problems are going to be based on the olympiad?
•  » » 4 дня назад, # ^ |   -30 Gotem??
•  » » » 4 дня назад, # ^ |   -34 hi sguu
•  » » » » 4 дня назад, # ^ |   -16 hi :D
»
5 дней назад, # |
-46

# But Is It Contributed?

•  » » 5 дней назад, # ^ |   -18 Yes, it is. Your contribution will decrease.
»
5 дней назад, # |
-37

# Or Is It Rated?

 » 5 дней назад, # |   -6 The start time changed from 16:05 UTC+8 to 21:35 UTC+8... At least I can go to bed before the next day.
•  » » 5 дней назад, # ^ | ← Rev. 2 →   -31 I thought that I can participate in this Round before I noticed that the start time had changed.The disadvantage of training during summer vacation in boarding schools.
 » 5 дней назад, # |   -30 mathforces?
 » 5 дней назад, # |   -19 Hope no server/hardware problems will occur this time :)
 » 5 дней назад, # | ← Rev. 3 →   -40 round #503 and error #503(unavailable Gateway).. another coincidence??... hopefully..not this time :)
•  » » 5 дней назад, # ^ | ← Rev. 5 →   -43 Shouldn't it be 502 Bad Gateway & 504 Gateway Timeout?(UPD: Comment of hrOarr is fixed)(BTW, why didn't the server down in Round #500(Server Internal Error)?)
•  » » » 5 дней назад, # ^ | ← Rev. 2 →   -27 hope #service unavailable fact... btw error may b unpredictable...
•  » » » 5 дней назад, # ^ |   -21 I saw 500 error yesterday, it lasted for a very short time, then changed into 502 error, and then the announcement.
•  » » » » 4 дня назад, # ^ |   -14 I just said the truth I saw that had already happened. I also hope that it will not happen again.
 » 5 дней назад, # |   -13 I guess despite the original contest being IOI styled, this round will be CF styled, as always?
•  » » 5 дней назад, # ^ |   +3 Original contest is ACM styled like most team olympiads.
 » 5 дней назад, # |   -34 Hope to be a good contest as it seems to be, wish you all guys better ratings...
•  » » 5 дней назад, # ^ |   -33 You don't know how much I love you, when you down-vote for nothing!!!
•  » » » 5 дней назад, # ^ |   -36 I wouldn't recommend you posting here without any serious reasons. Any controversial and/or "meaningless" comments are very likely to be downvoted.
•  » » » » 5 дней назад, # ^ |   -12 I don't know how those memes can be serious, anyway I won't comment anymore...
 » 5 дней назад, # |   -13 Great to see izban is one of the problemsetters!
 » 5 дней назад, # | ← Rev. 3 →   -21 Are there any shared problems between both divisions ?
•  » » 4 дня назад, # ^ |   +5 As always
 » 5 дней назад, # |   -42 Пересекается с днём физкультурника в Архангельске
•  » » 4 дня назад, # ^ |   -14 Пересекается с моим привычным временем ужина, можете перенести на полчаса пораньше?
•  » » 4 дня назад, # ^ |   -22 Пересекается с олимпиадой ЛКШ
•  » » » 4 дня назад, # ^ |   -32
•  » » 4 дня назад, # ^ |   -13
 » 4 дня назад, # |   -90 Everybody jump on the downvote train!
 » 4 дня назад, # |   -36 Можно ли участвовать, если ездил в ЛКШ.Июль?
•  » » 4 дня назад, # ^ |   -54 Судя по всему можно
•  » » » 3 дня назад, # ^ |   -15 R.I.P. Вклад
•  » » 4 дня назад, # ^ |   -37 да
 » 4 дня назад, # |   -63 Great round! The time really fits me.
 » 4 дня назад, # |   -13 As the prizes of the previous round is postponed, will there be prizes in this round?
•  » » 4 дня назад, # ^ |   -15 I think it will be on div1 + div2 round so no.
 » 4 дня назад, # |   -64 I hope time limit will be enough
»
4 дня назад, # |
-132

Trains of Downvote.

# metoo

 » 4 дня назад, # |   -88 I hope it won't be unrated like Round #502 (Laugh
•  » » 3 дня назад, # ^ |   -16 Oh ,hope that won't happen again.
 » 4 дня назад, # | ← Rev. 2 →   -43 this blog full of downvote comments
 » 4 дня назад, # |   -68 Is it UNrated like round 502?)) Just kidding, is it rated?
 » 4 дня назад, # | ← Rev. 2 →   -62 _kun_ Is it Mathforces?
 » 4 дня назад, # |   -20 Why are you people downvoting every single comment? Just for fun? It completely ruins the whole discussion, because if anyone says anything, he will get downvoted to hell.
•  » » 4 дня назад, # ^ |   -89 Also for reading most of the comments I need to click on "here" all the time. Sign of something special gonna happen in this contest I guess (can be negative/positive) ;)
 » 4 дня назад, # |   -44 Пересекается с Codeforces Round #503 (по олимпиаде ЛКШ)
 » 4 дня назад, # |   -78 Is it disrated on downforces?
 » 4 дня назад, # | ← Rev. 2 →   -29 Why most of the comments in this post are hidden?I can't find the reason why you downvote so much.(Because of this I upvoted all the comments)
•  » » 4 дня назад, # ^ |   -71 And I downvoted your comment
 » 4 дня назад, # |   -30 It is a shame all comments have a huge number of downvotes, I hope people leave more constructive comments and vote more logically.Please, don't destroy such a great community !
 » 4 дня назад, # |   -89 I challenge you to Downvote me..
 » 4 дня назад, # |   -73 I challenge you to upvote me...
 » 3 дня назад, # |   +217 Why are all comments downvoted?
•  » » 3 дня назад, # ^ |   +78 Someone made a bunch of alts to downvote, probably. If not manually, I'm guessing someone used a bot. (I'm surprised codeforces doesn't have some countermeasure this)
•  » » » 3 дня назад, # ^ |   +80 Codeforces uses reCAPTCHA to prevent bots, but it can be passed automatically with little money.
•  » » » » 3 дня назад, # ^ |   +64 Hosting VK Finals now, I do not have enough time to investigate the situation. But definitely they are not simple bots. Probably, it is some kind of flash mob or hacked accounts.
•  » » » » » 3 дня назад, # ^ |   -29 So how to deal with these downvotes?Keep them polluting the contrib. of everyone?
 » 3 дня назад, # |   -37 please delay/starts it 15 min later than scheduled time because there is a contest at atcoder also.. please this is a request.
•  » » 3 дня назад, # ^ |   -32 you can AK ABC in 85 minutes and take part in CF
 » 3 дня назад, # | ← Rev. 2 →   -72 Downvote is raining Here ...!!!
 » 3 дня назад, # |   -232 HiI made 10 accounts in Codeforces and downvoted some comments here, and of course others saw that and kept downvoting the comments. Some of you may already knew this but my purpose was to show that lots of people here are just dumb followers and they don't have any brain to decide what to do, they just copy others' actions.So to the guys who got downvoted in this community or as some guy in other blog said are not a clown to make others laugh, don't worry, it's not your issue.Thank you for being idiots.
•  » » 3 дня назад, # ^ |   -62 Did you know that you are so funny?? That's not being an idiot, when someone sees everyone is downvoting him/her, he/she starts downvoting others... you are the only idiot here... Hey idiot, now go and make more accounts and downvote me..
•  » » » 3 дня назад, # ^ |   -22 They did not claim to be funny. when someone sees everyone is downvoting him/her, he/she starts downvoting others... Why would that make sense?
•  » » » » 3 дня назад, # ^ |   -16 Mob mentality/conformity, people follow the crowd, when they see a lot of downvotes they are already ready to agree with the majority. I think this is a real effect, but I don't think that downvoting everyone to "prove a point" causes any real change... it is just an annoyance
•  » » » » » 3 дня назад, # ^ |   -16 That is not what I asked. Tour_guide claimed that when someone is downvoted, they start downvoting others.
•  » » » » » » 3 дня назад, # ^ |   -15 Sorry, I misunderstood. I suppose he means that person gets very mad and wants to take it out on others, but I think most of the codeforces community is better than that
•  » » » » 3 дня назад, # ^ | ← Rev. 2 →   -10 Why not?? Don't you feel bad when everyone is downvoting your every single comment?? Less people can accept others disagreement and don't react...
•  » » » » » 3 дня назад, # ^ |   -10 I might, I just don't see how downvoting others would help whatsoever...
•  » » » » » » 3 дня назад, # ^ |   -12 I don't really know and can't explain, something instinct, I think. maybe you're right...
•  » » 3 дня назад, # ^ |   -13 So do you think this is the right way to tell them they're wrong?
•  » » 3 дня назад, # ^ |   0 Good job. Most posts above had 50+ downvotes even though you casted only 10. Time for people to wake up.
 » 3 дня назад, # |   -16 flood of downvotes!!
 » 3 дня назад, # | ← Rev. 2 →   -20 Why someone was so bored to downvote everyone?
•  » » 3 дня назад, # ^ |   -13 I think that means bored.:（
•  » » » 3 дня назад, # ^ |   -21 Yes,I mean bored...
 » 3 дня назад, # |   -15 I have short by the way.
 » 3 дня назад, # |   +326 That one person who'd like to comment but too afraid of the downvotes.
•  » » 3 дня назад, # ^ |   -25 hhh
•  » » 3 дня назад, # ^ |   +21 It's lucky that you still have the chance to be afraid.
 » 3 дня назад, # |   -53 Can i get more than 100 downvotes ?I'll appreciate it :D
 » 3 дня назад, # | ← Rev. 2 →   +71 If you want to see the comments in this thread without clicking on every link or you have a strong will and always want to see every downvoted comment, then install my brand new super duper userscript created in the last 5 minutes: https://openuserjs.org/scripts/mraron/Codeforces_Show_Bad_Comments (you may need something like tampermonkey addon to get it working though)[/END of self advertisement]
•  » » 3 дня назад, # ^ |   +13 ads are getting smarter
 » 3 дня назад, # |   +28 Hope the description of the problems can be concise.
 » 3 дня назад, # |   0 Scoring?
•  » » 3 дня назад, # ^ |   +14 Will be announced later.
 » 3 дня назад, # |   +32 Freaking A >(
 » 3 дня назад, # |   +19 problem c is much harder than problem b
 » 3 дня назад, # |   0 Was C not Knapsack ?
 » 3 дня назад, # |   0 How to solve problem D?
•  » » 3 дня назад, # ^ | ← Rev. 3 →   +8 You can calculate the cost for other have less or equal than k votes, and i have greater than k vote in O(NlgN). then test for all k = 1 to N/2+1----------------- Sorry I confused C/DIf N % 4 != 0, answer is -1If N % 4, Let's think about the sequence of A[1 to N/2], A[N/2 to 1]. ex) 1 2 3 2 3 4 3 2 1 -> 1 2 3 2 3 / 3 4 3 2 1Then Since diff is 1 or -1, it it guaranteed existance of answer. Then you can find it by binary search. I want to explain more but i should leave now sorry :(
 » 3 дня назад, # | ← Rev. 2 →   +5 How to solve div.2C?
•  » » 3 дня назад, # ^ |   +10 Iterate the number of votes we want from party 1, then get the minimum cost required for this number of votes to be the majority. Answer is the minimum of the result from all the different number of votes required.
•  » » 3 дня назад, # ^ |   +1 1 <= k <= n, you need to calculate cost (k = 1; k <= n), k is votes, then min of these cost is our answer, firstly you should cut k <= votes[i] (1 <= i <= m) x = votes[i] — k + 1, then cur_votes += x; second need_votes = k — cur_votes then first sum of need_votes added your cur_cost
 » 3 дня назад, # |   0 Can anyone explain problem C && D please?
 » 3 дня назад, # |   +7 Interesting problems, how to do Div1C?
 » 3 дня назад, # |   +1 For div2c the idea is to always select the minimum voting cost until it's time to choose the last voter... is this approach right? and if it is, how to implement the last part of it ?
 » 3 дня назад, # |   +5 Div.2 C is bunch of priority queues and sets and maps. I was not able to finish it in time :'(
•  » » 3 дня назад, # ^ |   +28 You can do it without any of those things.
•  » » » 3 дня назад, # ^ |   +1 I did not come up with a more simple idea so I wrote a bunch of these things mixed. XD
•  » » » 2 дня назад, # ^ | ← Rev. 2 →   0 Can you please explain what does cost[i][j] denotes in your solution for Div1 A ,it's computation part ?
 » 3 дня назад, # |   0 Problem C make me simulate the same example again and again for 1.5h but I finally found nothing qwq.
 » 3 дня назад, # |   +127 Does every interactive problem on CF have to be binsearch :P? (OK, I know there are many counterexamples, but number of such problems is too high and they are rarely interesting)
•  » » 3 дня назад, # ^ |   +26 This was exactly what I thought when I saw 60 in problem B :)
•  » » » 2 дня назад, # ^ |   0 I didn't know how to solve. Saw 60, and that two queries are definite for as for i and i+n/2, I was sure it was Bsearch. I coded for both way, one was working, submitted and accepted. I don't even how that solution is correct but its working.
 » 3 дня назад, # |   +23 Any idea for Div1 C?Btw, C is a bit too hard, but today's problemset is good. Problems are balanced between thinking and implementing. I enjoyed B a lot.
•  » » 3 дня назад, # ^ | ← Rev. 2 →   +3 Btw, C is a bit too hard, but today's problemset is good.The kinda converse to Div 1 C (that too not constructive, but just the existence of such sets) came in Tuymaada 2010 Junior Problem 8 but it's still unsolved on AoPS ! I hope the answer to this problem (Div 1 C/Div 2 E) will give some hint on that problem, because that one is bugging me for a while.
•  » » 3 дня назад, # ^ | ← Rev. 5 →   +49 This seems to be exactly a constructive version of Chvatal-Lovasz theorem about semi-kernels in directed graphs. The simplest proof is indeed constructive and should yield a linear algorithm: pick some vertex v, delete it and its "positive neighbourhood" (the set of all vertices u such that there exists a v → u edge), recursively find a solution in the remaining graph, add v back if you may do that without breaking independence of the set of the picked vertices. Now you have a solution for the original graph (to verify that, just consider two cases: you added v back or you did not).Link to the original paper: Chvatal-Lovasz theorem.For implementation details, you may refer to this submission: 41500579.
 » 3 дня назад, # |   0 can anyone tell me an idea/solution of pb "C. Elections" in recursive + memorizing
•  » » 2 дня назад, # ^ |   0 You mean DP? Because I'm pretty sure a DP solution is not available for Div 2. C, as in the states you don't know which party have how many votes in order to reach for an optimal state.
 » 3 дня назад, # |   +52 My story in A
 » 3 дня назад, # |   +2 Unlucky round for me.I started by quickly solving A, then moved to C. Wrote a solution in 20 minutes, and only then red the second sample. I really need a browser extension to replace "loop" -> "self-loop". Then I moved to b, and got 2 WA's in test 16. What is the problem? int answer(int i = -1) { if (i > 0) i = (i%n+1); cout << "! " << i << endl; exit(0); } I solved the problem zero-indexed, so I had to fix the indexes by adding 1. But if i = 0, it outputs 0 giving WA. I didn't realize this was the mistake, shuffled some code around, and got "pretests passed". Then only later I realize this and had to resubmit.But yeah, I couldn't solve C, so I don't mind losing rating.
 » 3 дня назад, # |   0 Does anyone know what's the issue causing WA on pretest 5 in div2C?
•  » » 3 дня назад, # ^ | ← Rev. 3 →   +1 You get WA with below input.2 2 1 1 2 10for(int i=n-1;i>=0;i--){*for(int i=n;i>=0;i--){
•  » » 3 дня назад, # ^ |   0 Maybe you select the voters who originally support Party 1 to let them change. Before I fix it, I got a WA5
 » 3 дня назад, # | ← Rev. 3 →   +4 Hi i thought I found someone violating the rule of codeforces contesthigu and adityasr share the same solution for Problem C of Div 2
 » 3 дня назад, # |   +23 This the first time for me to enter a contest , in fact I couldn't solve any problem as I misunderstood many points and also I haven't practice a lot ,but I hope to do better than this the next time.....
 » 3 дня назад, # |   -45 See!!I told you everybody that Benq is going to be the next world conqueror of CP.rip everybodyBenq wil beat you all!
•  » » 3 дня назад, # ^ |   +40 This is false; C was incorrect. :/
•  » » » 3 дня назад, # ^ |   -7 I'm so sorry :(Next time you will get it :D
•  » » 3 дня назад, # ^ |   +54 your alts are all boring srsly
•  » » » 3 дня назад, # ^ |   -29 What are you talking about ko_osaga i have only this alt to support Benq to win this IOI . So don't generalize by saying your "alts".
 » 3 дня назад, # |   +3 could any one tell me what is that system testing that have started after finishing the contest,please??
•  » » 3 дня назад, # ^ |   +8 In the pretest, only part of test cases are run. After the contest, the system judges all the solution with all test cases and test cases used in hacking
•  » » » 3 дня назад, # ^ |   +9 Thanks a lot! ,I do really appreciate your comment....
 » 3 дня назад, # |   0 How to solve Div1 C? I passed pretest but I'm not sure my solution...
 » 3 дня назад, # | ← Rev. 2 →   +25 I think today's problems are very nice.But,I think the difficulty of solving B and the difficulty of solving C is too different.QAQ
 » 3 дня назад, # |   +8 How to solve Div1 C? I passed pretest but I'm not sure my solution...
 » 3 дня назад, # |   +79
 » 3 дня назад, # |   +66 Is DIV1A/DIV2C same as http://codeforces.com/contest/458/problem/C
•  » » 3 дня назад, # ^ |   +8 That's crazy. Even the same legend. After more than 1000 contests, it must be really hard to find these coincidences.
•  » » 3 дня назад, # ^ |   +78 I think every time there is an election in Russia, someone "comes up" with that problem. That's why it has already been in a contest.
•  » » » 3 дня назад, # ^ |   +3 lol. Cool satire.
•  » » 3 дня назад, # ^ |   +1 The main difference is the constraints. My O(n^2) solution was accepted, but in this problem, it will fail as 1<=n<=10^5.
•  » » 38 часов назад, # ^ |   +13 We were not aware about this problem, sorry =/.
 » 3 дня назад, # |   0 For div2 C, first lower down every other party to at most k votes, then we can get enough votes from those who need least without considering if he is from the most voted party. Check every k from 0 to m, we can find the minimum cost.I pass pretest with this solution in 1900ms, and reducing time to 1100ms using priority_queue.Hope it won't get a TLE on the system test :p.
•  » » 3 дня назад, # ^ |   0 Wrong answer on test 21……QAQ
•  » » 3 дня назад, # ^ |   +5 I should check every k from 0 to n, not m……:(
•  » » 41 час назад, # ^ |   0 Hi. What is K? and why do we have to reduce other parties? Can you please elaborate?
•  » » » 34 часа назад, # ^ |   0 The number of votes that you give to party 1. If you fix the number of votes, it is easy to calculate the min cost. So fix the number of votes (k), but try all possible values.
 » 3 дня назад, # |   +8 Did someone passed Div1D with O(n3)?
•  » » 3 дня назад, # ^ |   +16 Just found 41488961.
•  » » 3 дня назад, # ^ |   +26 I did, but it took quite some iterations (== random changes to the code) to make GCC on codeforces to compile it as I want...It would be awesome if the "run on server" tab provides an option to download the compiled binary. One can at least see what exactly the compiler is doing.
•  » » 3 дня назад, # ^ |   +8 Yeah, but in my case, with a dirty trick. See my comment below.
•  » » » 3 дня назад, # ^ |   0 Yeah that's insane. I have to trust more in CF servers.
•  » » » » 3 дня назад, # ^ |   +8 As ilyakor's comment above tells us, trusting can be pretty dangerous. It's best to be sure, and testing in a local environment similar to CF servers helps greatly.
 » 3 дня назад, # | ← Rev. 2 →   +1 In div. 1 C, about 70% submissions that passed the pretests, failed later on test 20. Why wasn't this test added to pretests?
•  » » 3 дня назад, # ^ |   +47 To don’t help people with heuristics I guess. Pretests should help you catch bugs.
•  » » » 3 дня назад, # ^ | ← Rev. 2 →   +17 Maybe I don't understand the idea of pretests, but in my opinion, they should help contestants check if their solution is mostly correct. In general, I believe that most heuristics and/or brute-force solutions should fail on good pretests. Also, stupid corner cases should be included in the pretests as well.
•  » » » 3 дня назад, # ^ |   +8 Pretests should help you catch bugs. No, pretests should give you some idea if a solution is correct. You can catch bugs by stresstesting, but can't realise you're missing something essential by doing that. To don’t help people with heuristics I guess. Only if you expect a lot of solutions with heuristics that wouldn't pass some type of tests, which isn't very realistic in problems like this one. I'm sure there weren't many heuristics among the failing submissions.
 » 3 дня назад, # |   +113 Looks like most of the solutions to Div1 D (1019D - Большой треугольник) are with binary search. I didn't come up with the right solution, but managed to squeeze an O(n3) one (41491248) instead, using 1950 milliseconds out of 3000. It involved a trick and a dirty trick. I'd like to elaborate on that, to increase awareness of such tricks for contestants and problemsetters alike. The trick is just loop unrolling, which is around this part: enum span = 4; for (v = j + 1; v + span <= n; v += span) { // instantiate 4 identical blocks at a time static foreach (r; 0..span) {{ // so that they can be computed in parallel auto t = pjx * p[v + r].y - pjy * p[v + r].x; // pjx and pjy are p[j].x and p[j].y ok |= (t == sp) || (t == sn); // t can be positive or negative }} } The static foreach is expanded at compile time into 4 blocks with r = 0, 1, 2, 3. In C++, one way to do it is to use a #define inside the loop, and instantiate it manually 4 times instead.The dirty trick is doing all of the above in signed int32: as the program is run in a 32-bit environment, it helps greatly. If we find the triangles which have area equal to s modulo 232, only then we check again using true but slow int64 multiplication and comparison. Now, as a problemsetter, you can't really do anything against loop unrolling. In fact, in simpler cases, a good optimizing compiler does that itself under the hood.Against the using int32 part though, it is possible to construct a test case. Make all coordinates divisible by 216, and s divisible by 232. This way, all multiplications modulo 232 will result in zeroes, and the actual O(n3) work will be done by the int64 part of the solution. In this case, making it run for five or six seconds.
•  » » 3 дня назад, # ^ |   +20 I also did it in O(n^3), and without the dirty trick (I did consider it, but figured it was at risk of being attacked). My tricks were to - use pragmas to enable more aggressive compilation - precompute the signed area of triangle (P, Q, origin) for every P and Q, after which the area for a triangle (P, Q, R) can be computed purely with addition (which is less expensive than multiplication on a 32-bit system).It would be nice if Codeforces would move to 64-bit one day — these days even the chips in your mobile phone are 64-bit!
•  » » » 3 дня назад, # ^ |   0 Argh. I wrote essentially the same code as you, but without pragmas, so it got TLE. I guess I will know what pragmas to use next time.(I also tried putting the points into buckets depending on the coordinates modulo 11, and then only comparing those buckets for which the area is correct modulo 11. But it got WA due to a silly bug.)
•  » » » 3 дня назад, # ^ |   +7 mind sharing any good resource on learning these pragmas? Thanks!
•  » » » » 3 дня назад, # ^ |   +15 I read them in a comment on some previous contest (might have been a different architecture pragma, I couldn't remember so picked something that looked sensible), but I don't recall which contest it was.
•  » » » » 3 дня назад, # ^ |   +2 Pragmas are instructions or information for the compiler embedded in code, e.g. pragma once (ignore all include-s for this file except the first one) or pragma GCC target() for setting target architecture. Obviously, they're compiler-specific, so you have to read the documentation for a specific compiler. For example, I found this in about 5 seconds, so don't ask for shit you can look up yourself.Function attributes are more interesting. You have the optimize attribute, with which you can tell the compiler to aggressively optimize just one function — very useful, since Ofast on everything can slow down some other part of your code. Then there's always_inline attribute, with which you can force inlining of a function that the compiler would usually skip because it's too long (e.g. a lengthy arithmetic expression that's used very often).
•  » » » » » 2 дня назад, # ^ |   0 Thank you for the useful information. Sorry that you get downvoted for helping :(
•  » » » 2 дня назад, # ^ |   0 I did the same with you, but got TLE with C++11. After the contest, I submit the same code with C++14/C++17 and get a Accepted. :(
•  » » 3 дня назад, # ^ | ← Rev. 3 →   0 What do you think about the following idea: pick random p < 2^16, begin by taking coordinates mod p, and compute hash of triangle areas mod p using integer type.EDIT: Never mind, mod is probably slowerEDIT: okay, seems like Gassa got it to work.
•  » » » 3 дня назад, # ^ | ← Rev. 2 →   0 I tried it now but realized that, yeah, we seem to need a modulo operation in the innermost loop.I've tried to make the calculations modulo mod-squared. But, if we take the coordinates modulo mod, their product is correct modulo mod, but not correct modulo mod-squared. For example, 1 (modulo 2) times 1 (modulo 2) can in reality be either 1 or 3 (modulo 4), we don't know. So, seems we have to use the slow % operation.
•  » » » » 3 дня назад, # ^ |   +10 What about a memory access, keep array f[x] = 1 if x is a multiple of p and 0 otherwise?
•  » » » » » 3 дня назад, # ^ |   0 Now I'm confused. How would it help?The example modulo 4 does not work even for non-multiples of 2.
•  » » » » » » 3 дня назад, # ^ | ← Rev. 2 →   +10 No, just do the original thing, to check if area + S is a multiple of p, just access f[area-s]. (maybe pick p < 2^12 and have bitset of size 2*p^2?)
•  » » » » » » » 3 дня назад, # ^ |   +20 Hmm, that could have worked, but doesn't for me (attempt: 41503640).When the mod is too small, we would have too many false positives. When the mod-squared is too large, the array does not fit into processor cache. I've got TL with mod = 997.Actually, scratch that. With a bit of refactoring and mod = 107, this passes: 41503762. Thanks for the idea!
•  » » » 2 дня назад, # ^ |   -10 This can still be easily hacked. (it's mostly safe against system test, though)
•  » » » 2 дня назад, # ^ |   0 Maybe we could do something like this:Pick a random p ~ 2000. (see note)As suggested, we want to find all solutions mod p (of which there are hopefully ^3/p) and test them individually.Our basic loop is as follows:for each pair of points (P1, P2): determine all P3 which gives right area mod p test these trianglesLet ABCDEF be some constants. Let P3 = (x, y)Now, after fixing P1 and P2, we know that the area mod P is given by Ax+By+C. We want Ax+By+C = S. If A=0, we handle it separately. Else, we divide the equation by A, giving x+Dy+E = S, or x+Dy = F.To find all such points such that x+Dy = F, we can precompute x+Dy for each point and each D. That is, we can store a vector of points for each pair (D, F), representing points such that x+Dy = F.The complexity for random points should be O(n^3/p + np). Choosing p~n gives O(n^2).Note: Of course, a given p can be easily hacked. Just choose S = p^2 and all coordinates multiples of p.I'm not sure if a randomly generated p can be hacked; there are not that many good choices of p too.
•  » » 3 дня назад, # ^ | ← Rev. 2 →   +34 I got TLE with O(n^2 log n) in Java during contest so was thinking the TLE was too tight, but I guess this proves me wrong.
 » 3 дня назад, # |   0 Feeling so uncomfortable in this round.
 » 3 дня назад, # |   0 Are you planning to change this feature/bug with bomb on sample other than the first one? It cost me a victory...
•  » » 3 дня назад, # ^ |   +12 It's truly a feature. It's meant to prevent you from failing in very simple ways as sending wrong file or wrong formatting of output/input. It's not meant to not penalize you for WA on third sample.
•  » » » 3 дня назад, # ^ |   +11 I was formating output incorrectly on second sample.
•  » » » » 3 дня назад, # ^ |   +16 Obviously wrong formatting of I/O. Or submitting a wrong solution or forgetting to delete random input generator from your code or other silly mistakes. It's extra lenient, but worth having despite that IMO.
 » 3 дня назад, # |   +11 How to solve Div1D
•  » » 2 дня назад, # ^ |   +10 Just brute force, as discussed above.
 » 3 дня назад, # |   +11 Nice TOP3! High five Marcin_Smu and Radewoosh :))Btw, it seems that many people tried some heuristics to C and all fo them failed. I have to admit that I also pushed some shitty solution... But it seems it was less shitty than others :P. I basically keep all the time some set of vertices that is an independent set and when I see a vertex that is not reachable in two steps from others I delete all its out-neighbours from set and add itself. And I do it until I run out of time or until I get a solution — whichever is sooner. And it luckily turns out that second case is always sooner :P
•  » » 3 дня назад, # ^ |   0 Don't piss me off...
•  » » » 3 дня назад, # ^ |   +13 Fortune favors the bold xD
•  » » » » 2 дня назад, # ^ | ← Rev. 2 →   +33 5 5 2 3 3 4 4 1 4 5 5 2 
•  » » » » » 2 дня назад, # ^ |   0 Nice! I admit I was lucky!
•  » » » » » 2 дня назад, # ^ |   +55 Why doesn't a problem like this with lots of heuristic solutions just have all directed graphs of size <= 5 as tests? There are only (24)5 = 1048576 directed graphs of size 5, so filling every test with as many size-5-or-less graphs as possible would only require like 10 tests.
 » 3 дня назад, # |   +18 I opened problem E after the end of the contest, and found it was actually an extension of my recent CSA problem. (That extension completely changes things, so it's not a copy) Although I don't have any good ideas, I regret myself of not opening E :)And big thanks to setters for the great round! Problems were really interesting. It looks even better because last round was very poor. Thank you so much for the effort!
 » 3 дня назад, # |   +30 I'm currently suffering from Post-Codeforces-Round-Depression :P
•  » » 3 дня назад, # ^ |   +17 I'm suffering from Continually-Refreshing-The-Page-Every-37-Seconds-Even-Though-I-Already-Know-How-Badly-I-Did Depression :/
•  » » » 3 дня назад, # ^ |   +1 Im suffering heavily from post system test depression....
 » 3 дня назад, # |   -16 Runtime error on codeforces, same test case works perfectly on my pc. Same compiler. This isnt first time its happening. just wow
•  » » 3 дня назад, # ^ | ← Rev. 2 →   +11 That happens, for example you over bounded when seeking an element of an array and there happens to be a zero (or anything "make sense") on your PC.
•  » » 3 дня назад, # ^ |   +3 The compiler option may be different. Try to compile it with "-O2" ?
•  » » 3 дня назад, # ^ |   +8 Run your program with Valgrind with a small input, you'll probably find you're reading something out of bounds or uninitialized. Usually that happens to be a 0 in your PC but random data in CF, so it seems to work but doesn't
•  » » » 3 дня назад, # ^ |   0 I solved it, thanks everyone :)
 » 3 дня назад, # |   0 Rating changings ?
 » 3 дня назад, # |   +81 For anyone interested, I wrote up solution sketches for a few of the Div 1 problems from today -- take a look: http://codeforces.com/blog/entry/61144
 » 3 дня назад, # |   +26 Editorial ??
 » 2 дня назад, # |   0 Can anybody tell me what is the complexity of this code? for problem Div2 C My idea : To get answer there are only 2 possibilities 1) We change the perception of person with minimum cost 2) We change the perception of person with minimum cost of the party which has maximum followers.I am using string s to store which people are followers of our party(i.e. party 0). Then either the first condition holds or second conditions holds for getting the correct answer. I think to find the answer we need to change at most 1500 characters in s and so my solution should work in O(2*1500*N) where N = overhead for calculation of each dp = O(n). So final solution should work in O(n^2).I don't know why it is showing TLE on testcase 46 which then I had to add an exception in code:p and get it accepted.
 » 2 дня назад, # |   +10 I'm finally back to red and not at all happy about it. I'd much rather get a good place because I did well than because almost nobody did well. What's even worse, D is solvable by very optimised bruteforce, A is a ripoff and C, D are "write a heuristic, maybe you'll pass lol" problems.
•  » » 47 часов назад, # ^ |   +10 Well, unfortunately we underestimated the squeezability of the dumb solution in D.But what is wrong with C?
•  » » » 45 часов назад, # ^ | ← Rev. 2 →   -8 http://codeforces.com/blog/entry/61087?#comment-450850Also the number of failed solutions on tests 20-21.
 » 2 дня назад, # |   +3 Got TLE for three times on div1.A with an O(n^2logn) solution, which made me upset and unwilling to do anything...
 » 2 дня назад, # | ← Rev. 2 →   +8 Is the tutorial of the round coming soon? It seemed that some solutions of Div2.D can be hacked.For example, use this data to hack Onuz's solution: 16 0 1 2 1 2 1 0 1 2 3 4 3 2 3 4 5 or use this to hack usachevd0's solution: 24 0 1 2 1 2 1 0 1 2 1 2 1 2 3 4 3 2 3 4 5 6 7 8 9 So I have a little doubt that if the data need to strengthen.upd: I am so sorry that I had not seen the constraint condition that |a1 — an| = 1.
•  » » 2 дня назад, # ^ |   +5 difference between first and last must be +/- 1 (it's a circle)
•  » » » 2 дня назад, # ^ |   +8 Yeah >u<
 » 2 дня назад, # |   0 Please, share the editorial of Round #503(SIS Div.2)
 » 2 дня назад, # | ← Rev. 2 →   0 Why this submission works weird? I submitted the program that only prints ? n 6 times, and then ! n. But the judgement protocol shows me that for the first testcase the program(submitted) prints 7 and 6. There isn't even ? character.For the second testcase, the program is expected not to print -1 at all, but the judge says so.Did I misread the problem statements?
•  » » 2 дня назад, # ^ |   0 The first value is the answer. The second value is the number of times you asked.
•  » » » 2 дня назад, # ^ |   0 You mean, 7 6 from "output" section of Test #1 means "the answer" and "# of queries"? But I can't understand why the value 7 pops up. The code only prints n, which is 8 for the first test...Also, the second case gets me confused even more. The code never prints the answer, -1. But the judgement says it does, and the test is passed.
•  » » » » 2 дня назад, # ^ |   0 The first value is the answer(0-index). for example, with test case 1, first value must be 3 or 7.about second example, you should read your code carefully.  if(n/2&1) { puts("! -1"); fflush(stdout); return 0; } 
•  » » » » » 2 дня назад, # ^ |   0 OMG... Sorry for my carelessness.The root of the problem was my mistake from code. I wrongly printed "the value" instead of "the position".To my shame, I doubted the judging system. Thank you Oumae_Kumiko !!
 » 2 дня назад, # |   0 разбор будет?
 » 2 дня назад, # |   0 Please, share the editorial of Round #503(SIS Div.2)
 » 2 дня назад, # |   0 Please, share the editorial of Round #503(SIS Div.2)
 » 2 дня назад, # |   +6 Thank you for preparing the problems and round. :)
 » 43 часа назад, # |   -24 This round should be unrated, problem A was absolutely copypasted!!!!
 » 39 часов назад, # | ← Rev. 3 →   +3 Hello there, I'm new to Codeforces. Few days ago I tried to take part in this contest as my first one. When the contest is finished, I checked my code again but couldn't find any problem, so I asked my friend to help with me but we found that with different compiler selected, the result is different. Why and is it unfair?The following pictures shows that the result of same file submitted with different compiler. My code could be viewed/download here
•  » » 26 часов назад, # ^ |   0 After the contest you can see the test case your submission failed on at the bottom: http://codeforces.com/contest/1020/submission/41532464It looks like abs() is returning a floating-point value for you in the older version of C++, but it returns an integer in C++11. In particular, this line is the issue because you are actually printing a floating-point number: cout << abs(f1 - f2) << endl; Also, I recommend against using endl. See this comment for an explanation.
•  » » » 25 часов назад, # ^ | ← Rev. 3 →   0 Thanks, that helps a lot!But I am still wondering why it behaves different from the C++ Standards which refers here(cppreference.com) when using GNU C++(v5.1.0). int abs( int n ); long abs( long n ); long long abs( long long n ); (since C++11) Is it a BUG of the compiler? And why this happens only when the result is very big?
 » 32 часа назад, # |   +2 well,I'm still waiting for the solution for this contest,it's so slow QAQ