Всем привет!
13 сентября в 19:35 MSK состоится рейтинговый Codeforces Round #371 для участников обоих дивизионов. Это наш первый раунд и надеемся, что не последний.
Задачи готовили я (Антон Цыпко) и Sonechko (София Мельник). Большое спасибо GlebsHP (Глебу Евстропову) и Sereja (Сергею Нагину) за помощь в подготовке задач, MikeMirzayanov (Михаилу Мирзаянову) за системы Codeforces и Polygon, а так же iSlava (Вячеславу Очеретному), AllCatsAreBeautiful (Марку Михно), BigBag (Матвею Асландукову), winger (Владиславу Исенбаеву) и AlexFetisov (Александру Фетисову) за прорешивание задач.
Участникам будет предложено по пять задач и два часа на их решение. Мы рекомендуем участникам ознакомиться с руководством по интерактивным задачам. Разбалловка будет объявлена позднее.
Надеемся каждый найдет себе задачу по вкусу. Всем успешного раунда и повышения в рейтинге!
Разбалловка:
Div 2: 500 — 1000 — 1000 — 2000 — 3000
Div 1: 500 — 1000 — 2000 — 2000 — 2000
Upd: Поздравляем победителей:
Div 1:
Div 2:
UPD: Приносим прощения, что задача Div 1 C очень похожа на эту, но раунд будет рейтинговым.
Hope the Codeforces remain stable unlike last Div2 round.....
Hope so.. last round was pain :(
Good day, good Codeforces, and tonight I will be a purple Coder.That is really great.Thank you everyone!Thank the is world!
tomorrow, eid day in bangladesh. we can celebrate eid with contest. hope it will be a great contest.
In previous round contain Interative problem I lose 100 point on problem C because fflush :)) I hope nobody wrong like this :))
How you passed the example then?
my code have many if and one of them I forget fflush :((
My strategie usually is make functions to interact, one for reading and one for writing. You can do this almost in all cases and you won't have to be worried about flushing or parsing at every moment.
in the name of allah, most merciful
which rounds contain interactive problems?
i hope somebody says numbers for practice.
have good contest.
680C - Bear and Prime 100
in Codeforces Round 356 (Div. 2)
Oh no!!! Interactive problems again :(
hope for a stable Codeforces.
Eid mubarak for all muslims!
Eid Mubarak you too :)
Eid Mubarak Bro :D
Eid Mubarak Bro.
Eid mubarak
Eid Mubarak for all !
Eid Mubarak :D
Amin.
the holy Eid mubarak guys.
Eid Mubarak ^_^
Eid Mubarak brother!!!
Наконец-то интерактив, уже соскучился.
I so want this round to be rated and hassle-free.
I feel very interest in interactive problems :) but can't solve well :( All though, good luck to me for this Contest! and today is also Eid Day for in Bangladesh! Hope good luck in this Eid Day Conteset :D I think Everything will be okay During the contest Time.
Hope you solve the interactive problem. and also Eid mubarak. :)
good luck to everyone :)
Можно пояснить для новичка: что такое дивизион? Самостоятельно не нашёл..
все кто выше синего цвета — див.1, остальные див. 2
2-ой дивизион -- рейтинг от 0 до 1899. Там 2 задача не очень сложные, а 3 сквозные с первым 1-вий дивизион -- рейтинг 1900+. Опять три последних задачи из div 2, и 2 сложные.
Помнится, опытным путём было доказано, что не от 0...
Пишу отталкиваясь от того, что "говорит" codeforces, а именно: "Рейтинг должен быть от 0 до 1,899 для возможности регистрации на это соревнование". А по поводу "опытным путём было доказано, что не от 0", не могли бы вы дать ссылку)
worse
How to hack the interactive problem?
If you're on Linux, write
sudo rm -rf /. Make sure you have root access or it won't work!If you're on Windows, make a file named something.bat, type in it
save and run it. It really works!
No one is such a arse I think!
It isn't funny.
3ib da enta red
I'm shocked! what the number of downwotes!
Isn't saliii you ?!?!
I'm shocked!yes, exact! he is me! but how you got it!? actually I can't have virtual on the contests that I have participated before and I have such a fake account!
Actually, we have common friend (;
You must submit hacking program which will interact with target
It depends on particular problem. Instruction for writting hacking program always present in an interactive problem statement.
It will be described in the statement.
Eid Mobarok Everyone <3 from Bangladesh <3
Best wishes for Codeforces <3
Wish the Internet&server will be better..........
Wow! Interactive problems this time. Expecting Stable CF round this time :)
why interactive man?
I have problem with registration to contest... I register and then I click to list of participants and I still see "Register Now" although I was registered...
It will be a rated round ?
yes
I'm shocked this comment is so far down, considering how it usually goes...
it's 10 left minute to start the round and the score distribution is not announced yet !
UPD : now it's 1 min and nothing announced :(
Relatively few people registered(in both divs). I hope that means a working website!
Is everything working fine for everyone ?? For me on main codeforces page top menu is invisibile like in mobile view
No. I wait 5 minutes each time for submit page to open.
Eid mubarak to all :) hoping a great contest
লাইক দিয়ে পাশে আছি, ফ্রান্স।
I'm not able to submit You should be registered for the contest to be able to submit but on the contests page it says registration completed.
I am having the same problem.
fixed
Cannot submit.It says should be registered for the contest even though I registered.
I cant see other codes when block my problem :(
cant open room, random pages are loading ! clicking on a submission, it says soln already hacked or resubmitted ! but thats not the case
Not able to hack solutions
Can't submit any solution.
when I click submit button, I just see
nonsense err.
How can I test interactive code on ideone? Any help will be deeply soulfully appreciated :D
Write some code which will answer the questions automatically instead of answering them in stdin
It is just unfair to include problems like this div2E/div1C
as you can see a lot of people had it passed in around 20 minutes
there is one who solved it in 4 minutes ( after he solved A )
13C - Sequence
it's here :)
too much creativity
Man! Now I get the reference. I thought it was a joke only I didn't get!!
Pasting link to the same problem, with visible solutions, during the contest... genius.
The problem is not the same.
You are right of course, but the only difference is non-decreasing vs. increasing, what is handled by line
t[i] -= i;. So, almost the same problem.It is genius!!! Way to protest like a boss :p
it was actually posted here blog about 1 hour before the end of the contest so posting a comment before 10 minutes isn't that genius
Omg, make it unrated pls
And your comment here fixed the whole situation.
At least don't make it unrated just remove the question from consideration.
Great idea !!
Yeah if you just solved the C or smth you better be GO TO HELL IT'S THE PERFECT IDEA EVERRRRRRRRR!!!!!!
Seriously, it looks like "great idea" to you?
Oh I forgot that it would be unfair for those who solved C only.... or maybe I didn't forget and it was just sarcastic comment.
the real genius is the problem setter i mean i wouldn't have pasted anything if it weren't some old codeforces problem
Do you remember all problems that ever been on Codeforces? Neither do I, GlebsHP, authors, MikeMirzayanov or anybody else. Posting such link during the contest makes things only worse; you (and all who did the same thing except you) could've posted such a link after the contest ends so that results of people wouldn't be affected.
After all, there is no difference between knowing a solution of problem because you studied many algorithms (even unpopular ones) and knowing the same problem beforehand. It's your advantage, use it. Posting it in public is equivalent to spoiling the solution during the contest.
I just checked the thread by Pepe.Chess. It appears this comes on the first page by a simple google search. Sure a co-ordinator shouldn't be expected to do this, but it's mind blowing how the author didn't even spend few minutes checking if it's original or not by a simple google search.
After all checking if your ( as an author ) 5-8 tasks are original ( as in not easily googleable) or not has nothing to do with you knowing the whole problem set on CF.
I agree with you. Still, this is not an excuse for ruining contest for everybody else. This is not how the contest ethics works.
But let me ask you a question. You may often see a problem in div2 and even in div1 that may easily be reduced to a shortest path problem in directed weighted graph. You type in Google "shortest path algorithm" and it suggests you "Dijkstra" even until you press Enter. Does that frustrate you in the same manner?
In this case it is not even the same problem; one should come up with replacing a[i] with a[i] - i trick to transform it to that problem.
ok dude , you don't remember any and you don't need to actually remember all problems on codeforces
but that doesn't mean checking if a problem is googlable or not :)
You are intentionally ignoring my point :) I'm not trying to find excuses for authors and coordinator, it is indeed a fail from their side.
What I'm talking about is that you and the guy who posted something at the middle of the contest did the wrong thing. In the conditions when this fail already happened, posting the link to the problem is a wrong move. Do not do that. Post it after the contest ends.
And yes, I know you were the second one to do that. This is not an excuse for you. Hope it is now clear what I mean.
At this moment I stop this conversation.
Is this a[i] — i trick a trivial transformation? Enough to deem the problem non-original? (Genuine question — I didn't know the trick — I was wondering how common it is).
Not exactly trivial, but it was obvious to me and should be to most people who are at the level of usually solving div1C. Basically, subtracting 1 from every difference.
ok i am the guilty guy
some guy just copies an old codeforces problem and include it as a div1C problem
and some pedophile posts the solution one hour before the end of the contest
and i am the one who is guilty
i just commented here 5 minutes before the end
go paste the statement into google and you will find a post on quora
thanks people
We can agree that it's impossible to know all problems. But Google does. IMHO every setter before the very beginning of preparing the problem should try to find it on the internet. Otherwise, such situations will surely happen
But Google knows so many things it is hard to specify what are you looking for. Googling tasks is not easy. I copied my code from my high school's online judge, but was unable to find a thread on CF about that task which I know I have read.
Change a[i] by a[i] — i, it becomes 13C. Is it correct?
Yes I just realized -_-
12 or 13 ?
UPD: fixed
I accidentally down-voted your comment while trying to up-vote it and Codeforces won't let me change it. Sorry.
Also A isn't very original, I am sure I have seen easy variations of it twice in recent contests.
Waiting for rated contest for infinity time and now it will be unrated with almost 100% probability. That's fun.
It is still funnier than losing a lot of ratings because of not Googling the solution :P
No, unrated is fine for me, because I didn't google the solution. And got too much trouble with Div1B.
I think it didn't affect so much because people are not accustomed to reading blogs during contests. Div 1 people would not google and for Div2 the number os submissions show people being unaware of it. Around 300 submissions should have raised suspision.
Div1 people would not google? You'd be surprised...
I've been told that nowadays most valuable skill is not to know a lot of information, but rather to be able to get information you are missing in a short time :) (Ideally — without bothering other people with your questions while doing it)
Me too. But from now on google and I will be best friends.
Wait, I didn't get it, your reason for unrated event is "there was a problem in a contest which is rather well-known", right? :) Not technical issues, not problems being badly prepared, but the fact that some problem doesn't contain brand-new idea?
Maybe it is time for me to hope for round being unrated as I didn't manage to solve D which is also well-known and classic :)
I believe it was sarcasm, right? :)
Anyway, why is D well-known and classic? I didn't come up with a solution with reasonable running time asymptotics and submitted parallel binary searches with 2D Fenwick tree and heavy optimizations that works in O(nmlog3n). Though, on pretests and my own tests here on CF it runs for <4s.
UPD: ok, I got it. The solution is to do a binary search and then make a 2d-minimum query in the small rectangle. What exactly here is well-known and classic?
If you mean first part of my answer — I missed the fact that there were some comments about this problem and discussions right during a contest, yet I don't think it is enough for making it unrated.
For a second part — my solution is far from being cool, it is similar to your idea, and there is high probability that it will fail:). Even if it will pass — I haven't actually solve problem in terms of figuring out proper solution, and that makes me sad anyway. For me "find maximum in a static submatrix (using sparse table)" sounds like a very classic problem.
UPD. Oh, it seems that for other people transition to binary search + max.query was not so obvious, while I got stuck on a part about finding max in O(1).
It's quite funny that 713C is similar to 13C. Maybe it was intended joke? lol
How to solve Div.1 C???
Let b[i] = a[i]-i. Then it can be thought that you're to make non-decreasing sequence instead of increasing sequence. From that, a dynamic programming idea comes out. D[i][j] : minimum cost of making b[1] ~ b[i] sorted, such that b[i] = j: D[i][j] = min(D[i-1][k]) + abs(b[i]-j) for k <= j. j has to be one of the initial values of b, so the time complexity is O(n^2).
http://mirror.codeforces.com/contest/713/submission/20589839
How does b[i]=a[i]-i convert strictly increasing problem to non decreasing?
"a[i] is increasing" and "b[i] = a[i]-i is non-decreasing" are equivalent.
Okay it founds an answer but how to be sure it's the smallest one? We convert our array, how can it be the right answer?
Suppose not. Suppose there is a set of moves that's smaller than our answer. use the same set of moves on b[i] = a[i] — i. It will be a non decreasing array. Which will cause a contradiction.
Div1C: go left to right, increase values greedily up and count how much you add. Also maintain a sorted vector of best costs for moving down the current stairs by one. E.g. you pay 1, 1, 1, then 2, then 3, etc. Costs are groupped so vector consists of pairs (cost, number): (1,3),(2,1),(3,1),...
When next element is larger than current height, you increase all costs by 1 and push (1, h-1-x) to the vector's back.
When next element is smaller or equal, you increase it by d to make it higher. Then you reduce the latests d costs by 1 (you may need to split some group in vector into two groups). And you increase all other costs by 1.
Then you take all non-positive costs from vector's back and "use" them: decrease current answer and height.
So this vector grows linearly, leading to O(N2) solution. This can also be seen as DP.
Missed the registration...a pity.
I figured out a solution via MCMF.
First we can consider another array: a2 - a1, a3 - a2, a4 - a3, ..., an - an - 1.
Let's consider this new array as bi, and find the impact of increasing ai to bi.
For increasing a1, we get b1 decrease by 1.
For increasing ai (1 < i < = n - 1), we get bi - 1 increase by 1, and bi decrease by 1.
For increasing an,we get bn - 1 increase by 1.
Notice that we can add arbitrary number to ai.Let's view bi as n-1 piles of stones(allowing minus stone number), then we can perform 2 types of operations.
1.Generate 1 stone at pile 1 or pile n-1.Cost is 1.
2.Exchange 1 stone between adjacent piles.Cost is 1.
Out goal is to make every pile at least 1 stone.
Let's solve this model by MCMF.
Categorise bi as three types A(for piles with number more than 1), B(for piles with number less than 1), C(for piles with number exactly 1).
Connect SOURCE to b1 and bn - 1 edges with infinity flow and cost 1.(Meaning generating stones.)
Connect SOURCE to type A vertex edges with (bi - 1) flow and cost 1.(Meaning redundant stones.)
Connect type B vertex to DRAIN edges with ( - bi + 1) flow and cost 1.(Meaning required stones.)
Connect bidirectionally between adjacent vertexes edges with infinity flow and cost 1.(Meaning exchange.)
Perform MCMF and you are done.
Problem B. Filya and Homework ***** In this problem, Filya is allowed to pick any integer X, even x = 0. For each element of the array he can decide whether to add x to it, subtract x, or do nothing. He can choose to not add x at all, or not subtract x at all, or just do nothing at all. For each particular element he can add x to it (or subtract) no more than once.
This costed me 3 WA -_-
Yes, same here. I got 1 wa and waited for an announcement to clarify this. :/
fml.
.
No, 3 1 2 4
I had taken care of this case, and mistakenly typed > instead of >=.
fml, lol :D
That was a lot of hacks!
I have a complicated solution for div2D, too easy to make bugs...
Yeah i hope it had strong pretests...
Could problem C div 2 solved using simple bst? I represent the structure using 1D array.
It's just simple trie problem.
Trie sounds like an overkill. Can't we simply use maps here?
Lol, I just copied my implementation of trie and changed it a little bit.
I think no because of anti-hash test!! not sure though!!
I kinda worried about maps speed so I'm using array instead. So the root of tree is 1. If current node is x and the digit is odd, then we visit node number x*2 + 1, else we visit node number x*2. I'm taking advantage that the maximum number of digits is 18. So 2^18 < 600000.
Can't we just use an array of size 2^18 ?
Now I feel stupid for coding a trie from scratch -_- .
Did you trie your best?
I can't even... you're the odd one aren't you?
I am unable to think of a story for these comments.
Yes. I know I'm different :)
Problem C isn't just old — it's a classical min cost flow problem. :(
Very weak pretests for A and B, especially B. My solution is completely wrong, but when I noticed it, it was already locked...
C can be solved in O(Nlog N) by using the fact that abs(x-k) is convex function, I think. (I have made almost the same problem and used in Japanese domestic contest.)
I also gave the problem with very similar trick about convexity to the Yandex Algorithm 2016 Finals (problem D).
I solved that D problem, but have no idea how that relates to this problem. My codes to those 2 questions have literally nothing in common (even headers are not common xD). Could you elaborate a bit?
Replace a[i] with a[i] - i to transform problem the non-decreasing variant (this is not a necessary step, everything else may be done even in original statement, but it makes things easier to understand).
Consider two DPs: E[i][x] = minimum penalty for making i-th number be equal to x and S[i][x] = minimum penalty for making i-th number be smaller or equal to x. This obviously does not fit in TL and ML, but we will deal with it.
We have: E[i][x] = abs(a[i] - x) + S[i - 1][x] and
. Actually this means that E[i] and S[i] being treated as functions of real variable x are piecewise-linear, convex and S is obviously non-increasing. This allows us to store only the vertices of the plot of E[x] in map and simply recalculate them in O(n) (with extra logn factor from the map).
This may be simply improved to O(n2) by storing the points not in the map, but in the array, and furthermore, by storing them in some data structure that allows adding a linear function and binary searches (like segment tree or Cartesian tree), the running time may be improved to
. The code is literally 40 lines.
Could you elaborate please? Ternary search for the first value would work?UPD: I see it's not enough to determing the full sequence.
Hard Work Today XD
thanks for the nice contest =D
For Div2 A, most of the hacks included the cases when there was no intersection between the time intervals like [1, 2] and [3, 4].
Some other were due to the silly mistakes by the users.
Nice contest though.
Too bad it is going to be unrated .
If it is unrated....Good for me...I got a lot of penalty in B. Misread it completely -_-....BTW it is not helpful if there are too many unrated contests
Interactive problems look fun until you get WA and then you need to write more code to have a chance to find a bug(or spend even more time working as interactor while debugging).
Totally agree!
I think it's better to start with writing your own ask_query function, what should lead to something like this (version after changing it to the submitable version):
How can my solution for 2B be hacked?
https://ideone.com/L9PBla
3
1 1 2
The answer is "YES"
Damn, C was already discussed on CF few times :/. And in
xdd. Copy pasted 4 years old code (like probably many people).
yeah there is genius who got it in 4 minutes
Can you provide a link with the thread where it was discussed in O(nlogn)?
I tried to find it right now, but wasn't able to do that. I remember that it was on USACO and someone mentioned super short solution by ecnerwala, but it wasn't sufficient for me to find it :(.
I knew the problem before as well, but not the NlogN solution (just the easy N^2). Can you please explain me the more efficient one or provide a link to some solution? I've been thinking for a while at it and was unable to solve it that fast.
Eid Mubarak Everyone :)
how to solve div 2 E
Can anyone share with me his solution for Div2/C using a trie data structure? My solution using trie exceeded the time-limit I am not sure why.
why not use stl map? trie is difficult to code, maybe you have some bugs
What is your approach to use stl map?
you can also use Array[1<<18] to save the binary system number , and then find the count
http://mirror.codeforces.com/contest/714/submission/20576143
Here is my solution , using trie data structure.
http://mirror.codeforces.com/contest/714/submission/20581318
a nice contest
when judge ? i am newbee
when judge? i am newbee
You'd better go and do something else instead of waiting, because it can be (very) long. :P
it is 2:52 in china.... i want to sleep but i also want to know rating!!!!!!!!!!!!
When will the ratings be updated?
Takes hours at times. Relax. Come back after a sleep.
How to solve Div 2 D, binary search for each corner of each rectangle? I get stuck on finding columns of second rectangle, it is just too many cases? Anything simpler?
Binary search for each edge of each rectangle: http://mirror.codeforces.com/contest/714/submission/20603361
What is the intended time complexity in D? I wrote 10^9 solution and it passed pretest in <2s.
And my 10^9 is giving TLE on pretests :(
My solution is O(N * M * logN * logM)
Finally it passed.
У меня на домашнем интернете посреди контеста вылез Bad Gateway и до сих пор висит, остальные сайты нормально загружает. Сейчас сижу через VPN, к которому я подключен всё через тот же домашний интернет, значит дело не в нём. У кого-нибудь такое наблюдалось?
I failed to hack someone 3 times on problem B cause he put that
:( :(
LOL, should notice it :P
i didn't notice that cause i was in hury :\
It is his loss, not yours.
People regularly put
#define long long int intto disturb hackers.Update : see the comments below. :P
#define int long longactually...Indeed, sorry.
Don't you guys run their codes on your machine at least??????????
That takes too long to copy down. If you mean do that automatically, it's against the rules (and also kinda makes hacking silly as you could script the whole thing).
So, you'll rather lose points than test? Odd....
no of cours it takes so much time
Problem B's constraints are within 10^9, why would long long be necessary?
sorry i mean on problem A
Also notice when in someone's code there is an "if()" which it is wrong he might did this : if();
In problem D, the answer is 0 when there is no valid square i.e the region is empty, which I think should be noted in the statement. And I got WA on pretest 4 due to this issue.
When will the ratings be updated and system testing be done?
What is the solution to div.2 B?
We can make all values equal to either maximum value, minimum value or average of maximum and minimum(if (max+min) is divisible by 2).
Could you explain me why still am i unrated after finishing Round 370 and 371? I wnat to get my color...
370 was unrated due to server issues. 371's ratings are yet to be updated.
wait for it ..... system testing is still going on!
It seems Round 371 is gone from the contest list.
div1 E++: What if the directions can change during the game? (And I mean something better than
.)
EDIT: changed "j-i" to "j-i+2", sorry for mistake.
I misunderstood a problem first and tried to solve such a version. My guess was that we should change the input to distances between consecutive owls and then print:
where $S[a,b] = d[a] + d[a+1] + \ldots + d[b]$.
The reason is that numbers in an interval of length d can be decreased by only d + 1 owls (other owls will never help because it's stupid to overtake/outrun an other owl). So, only j - i + 2 owls can fight against an interval of length j - i + 1. And there is also a case when we consider a whole interval, what explains
in the formula.
I don't know if it's enough to print the above formula. And it's quite known how to compute it fast — one must binary search the answer first (and then it isn't hard).
I looked at E at some point in the contest, immediately recognised binsearch (it's quite common in this type of problems with parallel actions) and also misunderstood it as that at first. It seems harder to me than the contest problem — the optimal strategy within the binsearch isn't very clear.
Consider the case where the owls' positions are -2,0,2 with M=11. The optimal answer is 3 when the owl in the middle takes the two chairs next to it. Does that work with your formula? (Your "distances" are actually the number of chairs strictly between two owls, right? And j - i should be |j - i| + 1, right?)
You test produces distances 1, 1, 6. My formula considers an interval with the number 6 only with fraction
, what is correct.
(j - i) means (j - i)%n, because we are on the circle.
In your test I take maximum of 1 / 2, 1 / 2, 6 / 2, (1 + 1) / 3, (1 + 6) / 3, (6 + 1) / 3, (1 + 1 + 6) / 3. Reminder: taking the whole circle is a special case with dividing by len instead of len + 1.
I was confused by the denominator j - i primarily because of division by zero. So it's
Unable to parse markup [type=CF_TEX]
according to what you write, or [number of owls in the summed interval including the two border ones].If the distances are 2,4,6, then your formula gives 4, right?
Oh, there should be S[i, j] / (j - i + 2) everywhere, I'm sorry for that.
I managed to think j - i + 1 + 1 = j - i, which isn't really correct.
Yes, my formula gives 4 for 2, 4, 6. Is it wrong?
Yeah, it is. You'd need everyone to take a chair in every move since 2 + 4 + 6 = 4·3, so nobody can turn around (the answer to the contest problem would need to be 4). That won't work for the pair with distance 2 and the 2 chairs between them.
Oh, we have two different wrong ways to understand the statement. I thought that a chair is removed and each time we choose to move to one of two neighbouring chairs. While your version has empty places where chairs used to be.
Lol, so this wasn't the actual version -_-? Something is wrong if all of us misread it (either with us or with statement).
The statement is correct, it's probably that people good enough to solve E read statements too quickly and don't notice that step 2 is out of the loop.
Usually numbered list in this kind of problem describes one turn, and it fitted here very well.
Div2 is still going to be rated right?
there are only 28 accepted solutions on E.
Problem C appeared on round 13 (http://mirror.codeforces.com/contest/13/problem/C). The only change is the resulting sequence must be 'strictly' increasing, but the idea is the same.
I can't believe this I didn't get a notification that my code on B was hacked I found that out when I was checking my friends standings.
:(
Fun fact: An O(n3 + n * q) solution passed all test cases for D div 1. Bet that wasn't intended.
http://mirror.codeforces.com/contest/713/submission/20595881
My 10^9 also passed. I think it is almost impossible to distinguish between O(NMlog Nlog M) and such a fast 10^9.
Setting TL to 2s would solve the problem. I can't see any reason for it to be 5s inviting stupid solutions to pass
Decreasing TL will cause some O(log2) solutions to fail. It isn't true that all O(n3) solutions are faster than O(log2) ones.
I prefer a contest where there is a gradual increase in the difficulty level of the problems....In this way you get a fair judgement. Just my opinion :)
Can we get the editorials ? Also will the contest be unrated ? At least for Div 2, it should be rated I think. My last 4-5 contests on CF have been unrated.
It will be rated. Don't worry.
Hi everyone!
I have a concern regarding problems given, so need your advice...
In a problem A. Meeting of Old Friends it states: The only line of the input contains integers l1, r1, l2, r2 and k (1 ≤ l1, r1, l2, r2, k ≤ 10^18, l1 ≤ r1, l2 ≤ r2), providing the segments of time for Sonya and Filya and the moment of time when Sonya prinks. Please note on the statement l1 ≤ r1, l2 ≤ r2.
However, in the Test #3, in the input given l1 is actually bigger than l2, which should not happen by problem statement.
Test #3: 6 6 5 8 9
It is said that L1<=R1 and L2<=R2 ! In the test case that you gave
L1=6, R1=6, L2=5, R2=8, k=9
Answer should be 1
So, is it rated or not ?
I hope no.
You didn't even participated!!??
UDP.You participated but you're not even showed in my friends standings,is it a bug?
perhaps he(she) was participated with his(her) other account.
Yes it's rated, blog updated!
http://mirror.codeforces.com/contest/714/submission/20582567 Submission in python (during contest) http://mirror.codeforces.com/contest/714/submission/20597376 Submission in pypy (after contest) Even though both are same codes i got TLE for python and AC for pypy. Can anyone explain why this happens ?? If pypy is very good why is codeforces not removing python ??
For some rare cases Python 2 is faster. And Python is more standard. It is good to have a choice.
http://mirror.codeforces.com/contest/714/submission/20597794 -> I used int(i) where i is a digit http://mirror.codeforces.com/contest/714/submission/20598043 -> Instead of int i used ord(i)-ord('0') First submission is TLE, but second got accepted both in Pypy. Can anyone explain ?
Does anyone understand how I got this compilation error:
For this submission: http://mirror.codeforces.com/contest/714/submission/20581077
I get that println believes it can't be sure what the ternary operator is returning (either an Object of class Integer or int), but I would have thought the ternary operation would resolve first with the associated type. Is this simply not the case?
For Div2C, time limit was 1 second for my submission in python. Is time limit same for all the languages?? If that is the case, isn't it unfair?!!
I thought the time limit given in the problem statement page is for languages like C, C++ etc., and for slower language like Python, Java etc. the time limits are longer. For example, for Python it's around 5x, for Java it's around 2x etc. Could someone please clear my doubt?
I have to say, ur knowledge of languages and their TL is very very bad. First of all, before you participate in a contest, u are expected to know the judge environment and the rules. Do you want somebody to come to ur place and explain to you in detail? And secondly, python is much much much slower than Java, if its 2x for Java, its 10x for Python. Did u get it?
three 0 rating changes until now... (actually, thanks god I didn't get negative rating change!)
didn't get *
@arsijo and what about the spoiling of the problem......
It's totally unfair to leave it rated.
Why was it unfair? Everybody could google the problem.
Errichto this is sarcasm or what :D
Said someone who thinks that using an already known problem means that "guy just copies an old codeforces problem and include it as a div1C problem". It was hard to say if you are joking or not.
ok sorry
i know you don't mean it ... and i was pissed off there so i wrote "copies" in fact it is not really far from copying
So instead of being concentrated on thinking of problems , we keep searching on google ... I don't think this is the goal of making contests and participating in ....
Nobody said it's good that such a problem was used today.
Actually , It was fair. But it wasn't right and correct. so since it wasn't right, this contest should be unrated
Please, does anybody have any idea why this code doesn't work? I spent over an hour trying to debug it and even now when I see the test it fails on, I can't figure out what it is. When I enter the second test locally, it works. I
flushthe output everytime and the code to simulate queries seems fine as well. I also had an assert to check if it doesn't use too many queries and it does not.On your output line 22:
? 1 2 0 9 -> 0Notice
x2 < x1but the task says(1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n)Thanks a lot, still not sure where it happens, but a simple if fixes it. Didn't even know that you would get WA for that, but I suppose it makes sense.
In problem D, you pass first 3 pretests if you swap x and y values in input... I think that might be really misleading during contest especially when the order of x and y are nonstandard. Fortunately I had also another bug in my solution xD
I passed the first nine pretests of E reading n and m in the wrong order. I guess pretests were a bit weak this time around.
Div.1 Problem C was new for me and I got accepted it in O(N^2 log N).
My code : 20594137
Div.1 Problem C was new for me and I got accepted it in O(N^2 log N).
My code : 20594137
That was a great round :D Became pupil for the first time. ( another one was decreasing pupil :P ) Thanks round 371 :D
I mean why can't problem setters just google the question before adding them to problem-sets , because no one runs a script to match keywords with problem , people just google it. Its third time i have encountered a similar situation .
1 ) That pythagorean triplet Question, people pasted it from quora link .
2 ) That trie question, copied code from other sites
3 ) Today's problem C
I will deliver one nonpleasant spank for every problemsetter that denotes rows indices as x and columns indices as y :(.
I am unable to understand problem B div 2. why is the case that if there are only 2 distinct numbers then answer is always yes? also why the condition as mentioned in the tutorial for the case 3?You can choose a number only once so say for example 1 10000000 so i choose 1 then i can only substract or add to 10000000 ,no way we can make these 2 numbers same by choosing any of the number and add or substract from other number.
You don't have to always add or subtract numbers. In the case you mentioned, you can add 9999999 to the first number and do nothing to the second. Then, both numbers will be equal to 10000000.
is it not necessary to choose from the given array itself?
No, x can be any number.
Problem Statement Says that l1 ≤ r1, l2 ≤ r2 But apparently test case 3 is 6 6 5 8 9 Isn't the problem statement wrong. I got 4 WA for this constraint during contest time. :(
6 <= 6 and 5 <= 8 so those constraints are valid.
Спасибо за еще один день без ML!
Please help me!
here is my code for problem C http://codepad.org/zrZTXOBM
everything is ok in my compiler. but CF shows it's giving output '0' at every testcases!