Приветствую сообщество Codeforces!
В воскресенье, 19 октября, в 13:00 MSK состоится очередной раунд для участников обоих дивизионов.
Раунд будет основан на задачах регионального этапа Всероссийской командной олимпиады школьников, который в то же самое время будет проходить в Саратове. Мы знаем о пересечении раунда с этапом открытого кубка, но не можем перенести раунд, так как мы привязаны к олимпиаде.
В подготовке задач принимали участие HolkinPV, gridnevvvit, danilka.pro, Avalanche, IlyaLos, Fefer_Ivan и я.
Разбалловка стандартная: 500-1000-1500-2000-2500 (в обоих дивизионах).
UPD: Опубликован разбор задач.
Повезло, что не пересекается с Bayan Elimination round
I feel and i am sure that this round will be great and interesting :D
However, Unfortunately I wouldn't be able to participate in it because of its timing :\
May be I will try it as a virtual contest later in the evening :D
This might be good for my rating, I have just been a candidate master with only 9 points ;) :D
I'm sure that this round will be interesting too. ^^;
good luck for everyone!!
I wouldn't be able to participate in it because of its timing too.
ICPC rules?
codeforces rules.the contest's email mentions it.
you're right, codeforces rules! :)
Какой-то неполный анонс, даже страшновато. Какие правила? Пять ли задач вообще?
Это будет обычный раунд codeforces для двух дивизионов
And I would like to thank MikeMirzayanov and Codeforces team for this fabulous platform. :)
Жаль что пересекается с opencup :(
Maybe a little off topic, but due to the timing I'm really hoping for a 3-0 SSW sweep at world finals.
Context
a Russia's contest again !!!
Nerevar,thank you !!! your last contest had good problem :)
OPPS! I have to miss this contest. Unfortunately it will be at my EXAM time.
You can actually miss your exam for codeforces round because it is more important. sorry for my bad english.
HEY MAN IT's MY SEMISTER FINAL EXAM.
Don't say like u really care about it
Exam on Sunday? Quite strange. Sunday is generally a holiday.
roman28 , In Bangladesh, Friday is weekly Holiday :)
ohh! I didn't knew that. Thanks for letting me know.
You can virtual participate in this contest when you are free, though it is unrated for virtual participating.
Yes will will participate in virtual contest.
My first Div. 1 contest!! :)
Mine too!!! :)
yojainsochu
So copied comment got downvotes? Roger that.
Good luck and Have fun in div.1
"To wake up at 5 am, or to stay up until 5 am, that is the question!" -Hamlet, adapted
I think that second option is much less painful, though the first one will result in better performance.
2b||!2b
Well, I just woke up at 5 am. (You could never stay up until 5 am :D)
раунд будет рейтинговый?
The comment is hidden because of too negative feedback, click here to view it
Oh Got it !
Why this ^^ comment can't be seen! It has +44 vote. It's quite strange! May be codeforces have some technical issues.
You're kidding , right ???
I understand now. hahaha :v He got me :v
NO, This is not Codeforces Technical Issues, This is I_love_tigersugar's issue
I have registered but how to watch the questions?I am unable to get it last time when I entered.Where should I check for the question at the contest time?Please help me.
Now the contest is pending... So you can't watch the problem now. After about 3 hours the contest will start. You can participate it if you have register this contest.
Just visit this when the contest starts Codeforces Round 274 (Div. 2)
Good luck to every one!!! Its time to coding! Just believe! You can increase your rating! All of we can be grandmaster just we must trust! We must practice! We must start to solve difficult question! If we try to solve more difficult question solving question A B C will be easy! Sorry for my pure English. I wont to give some motivation sentence. Indeed person is able to do every thing. Just we must believe us.
I forgive :D
Pure means perfect. I think you misuse it. May be you wanted to say Sorry for my bad/poor English. BTW never mind :) We should learn from our mistakes :)
i am new on codeforces and i am lovin it
Thanks perfect time for me, hopefully for some others also. More contests at the same time please ;-)
And I problems were also interesting, great contest today. I had a little problem to understand C today, but that's my problem only...
It's 5PM now in China, and I'm quite hungry now..
I hope you are hungry for problems.
We can eat problems as dinner :)
Интересненько будет поучаствовать...
Wrong answer in B problem — Div 2. For the third example the answer should be 3 2, not 3 3: 8-3-2-6-3 1)7-3-3-6-3 2)6-4-3-6-3
There's no requirement that the number of operations used is minimum.
Oh, thanks! I'm sorry for the stupid question!
but 3 2 must be right also as 3 3! is it really so in test system?
This problem took me 20 minutes. I misunderstood it. I thought like you that the second number should be minimal. And then I saw this example... . It took me far more time to see that second number shouldn't be minimal.
Good bye yellow color!
Then you should change your avatar as well :)
I will :(
I won't :)
+1
Can't understand how to crack another participant's submissions. no button, no link...
You have to lock your problem first on the Dashboard page. Only then can you hack other solutions.
Why wasn't I able to copy-paste my hacking input(that I had generated seperately) to hack another solution ?
You cannot do that if the input is so long, you have generate input when you try to hack.
there is a file upload option also, you could use that.
So the intended solution of C Div1 was an O(n^2) DP?
i think it is, cuz my solution with segment tree was hacked
My solution is O(nk), but yes, it's DP.
Sorry, I meant O(nk), anyway, k is O(n). Thank you for reply.
can u tell how to do it ... my solution was n^3 dp .
Just recalculate sequence of its partial sums sum[] on each iteration.
a[i][l]+a[i][l+1]+...+a[i][r-1]+a[i][r] = sum[r]-sum[l-1]
I'll see whether my solution passes or not, but basically I compute the number of ways to end up on floor i after j steps for all possible i, for j = 1, 2, ..., k. Or more precisely:
a-1and never onlya.)Well I think so, pretty sure that there is no soln in less than O(nk) and O(nk) surely exists.
What is the solution for Div 1 A?
I just sorted them in descending order by a[i]. Have a variable that keeps track of the current day, let's name it day. Starting case is day = b[0] (zero indexed, already sorted) Now for all elements (starting from the second):
if b[i]>day, day=b[i]
else if b[i]<day, day=a[i]
Just print day at the end. It's a simple O(NlogN) solution that I believe works (hasn't been hacked, can't know for sure before grading).
EDIT: Forgot about the sorting when mentioning complexity.
Here's my solution
O(NlogN) due do sorting
What is the Hacking testcase for C ?
Many people assumed that when the pairs are sorted by a, the resulting permutation of b must also be sorted in order for the answer to be bn (otherwise an). This is not the case, as shown by the test case above. (The answer is
5; many people give6.)Also, another good hack is:
I managed to hack 2 solutions with this test (probably the ones which worked on your test above). Solutions which only sorted by a will fail on this test.
Damn it, why did I write
sorted(a, key = lambda e: e[0])instead ofsorted(a)>.<What answer should be 4 or 5, mine is giving 4??
Answer should be 4
A guy in this room reaaallly wanted to hack the room leader's solution...
it's like gambling, you play, you lose but play again hoping to win what you have lost, until you end up being completely homeless.
At least, Rostislav_the_great can now be sure his D submission is correct.
As always, unrated coders take over: 3 out of top 5 in Div2 are unrated
What were the hacking test cases for B div. 1? I found only one more or less common mistake — not checking whether the additional labels belong to [0 , L] interval.
Well, my solution didn't pass pretests when I wasn't checking if new added dot < L, so maybe it's only the left if it's positive
I found this (which also failed my locked submission):
Some people that made searching whether a distance exists in the array made it a function and thus only returned the first occurrence. In this case, the first occurrence of y - x is (9, 10), and with bounds they go over the ruler. However, there is another occurrence (16, 17), which fits; a new mark can go to 2, so the answer is 1 new mark. Those unlucky people (read: me and a couple I hacked) answered 2.
wow, that's unreal. This got me too
can u tell why my solution was hacked.... on your test case as well i am getting 1 2 as the ans . http://codeforces.com/contest/480/submission/8311510
i will try to explain my approach . first find if any of x or y exists or not . if they both exist than output 0 if only one exist than output the other one if none exist than starting from every point find arr[i]-x,arr[i]+x,arr[i]-y,arr[i]+y keeping in mind about the overflow. if any of them occurs twice than output that coordinate else output given x and y. did i miss any case ??
try this 4 33 5 7 0 6 16 33 ans should be 2.
thnx got it .. did mistake in checking ... so stupid of me..
well ..., next time will be because my D solution is broken with this case.
My solution had the problem that I was introducing only the new values of
arr[i]+xorarr[i]+y. A case likewould fail.
The Constraints of div1A were misleading :\ Made it look like an O(n^2) solution was the best when O(nlogn) is the most common solution.
Well, maybe the setters wanted that even a O(N^2) sort can do.
How to solve Div 2 B?
You can just take k times,in each time you work for the maxium-1 and the minium+1,notes the ans. And then it'll be solved:)
How do we solve the problem D (div2)?
Solution can be 0,1 or 2(its obvious). Now, you can check if answer is 0(There exists both x and y). After, you can check if you can add a dot somewhere and make both x and y. If you cannot, just print 2 x y. Time Complexity: O(NlogN) logN is for using map/set/binarysearch. Space Complexity: O(N)
I did the same thing by using a hash table, but it didn't pass the 4th test. Do you know the reason?
You missed the possibility that the distance x + y or y - x might already exist.
Correct answer is
1: 4(you use the pairs of marks (1, 4) and (0, 4)); some people give2: 3 4.Meanwhile, that's not all of it...
Time Complexity should be O(N)
You are need to check 4 cases once by shifting check bounds http://codeforces.com/contest/479/submission/8327088
То чувство, когда копипастил код в задаче Б и забыл поменять один плюс на минус :(
АПД: То чувство, когда понял, что этот случай никогда не реализуется на практике :)
why haven't the system tests started?
From the post at the very top: UPD: System testing will start at 15:30, because local school competition is not finished yet.
it's already 15:38 server time
now 15:38 but...
15:30 but in which time zone?
TESTINGTASK asked me during the contest for soln of Div2 C,stating " I'm new to codeforces and im struggling a lot. Can you tell me your solution to task C? ". Please "BAN" this guy!
Edit : Image Attached [Image Link]
Уважаемые организаторы! а можно добавить такую фичу: после конца раунда удалять из списка зарегистрировавшихся людей на раунд тех, кто не сделал посылок. В этом случае можно можно будет примерно прикинуть свое "ожидаемое место" для расчета рейтинга и понять, как ориентировочно измениться рейтинг, что сохранить нервы участников)) особенно в случае такого долгого ожидания тестирования, как сегодня... + это просто реализуется и не требует больших временных затрат
It's already 15:30,but why didn't the testing happen?:)
it's already 15:40 :(
We are working adding hacks into tests. It seems it will be a looooooong judging.
I thought you want to hack the task C(DIV1) using bit?
On problem D on Div.1, I think O(Sn^2) solution is easy but doesn't pass, but someone said it will pass.
If it will pass, what a sad...
Has the olympiad ended? Can you publish an editorial?
Editorial usually takes a couple of days
I saw Nerevar writing a editorial.
It depends on the author of the round. Some prepare an editorial before the round and publish it right after it's finished.
nice
finally system testing has started!
And also stopped.
started again :D
System testing is too slow today.
What about Div. 2 problem E? I thought of a O(n^2) dp solution though sadly the contest had ended by then.
Why is gcd(185,230) not a valid answer for pretest 1? please help in Problem-D Long Jumps Div2!!! We can measure in multiples of 5. What's the problem with that?
answer can be 0, 1 or 2. Re-read the statement.
It's not a valid answer because it doesn't use the minimum number of marks.
The number of marks is 1 only but the value is 5.
Oh, I misread; I thought you meant there are
marks.
Reread the problem statement; you may not move the ruler while measuring the distance. In other words, the distance must be exactly the distance between some two marks, not the sum of several such distances. If you measure with the GCD, you need to move the ruler to construct the distance 185 and 230, which is not permitted.
What about problem E of div. 2? I thought of a O(n^2) solution, though sadly after the contest.
Just doing DP with using consecutive sums.
Интересные задачи, спасибо организаторам за прятно проведенное время :)
Excuse me, I open CF website very slow on chrome, even can't see other people's codes after locking my problem B (I double click on other's scores of problem B in my room, but nothing happened). But it works well and very fast on IE. Can anyone tell me what will be the reason?
Why not use IE instead of Chrome？ :）
Can someone help me to understand this?
I solved C at 0:47, so I should have less points than wzyjerry. I missed somthing?
Might be he had wrong attempts.
EDIT : Indeed. He made a re-submission to the problem. Check his submissions.
Ok, but I cannot see those in history for C (not sure if it should be there or not), he had both hack attempts for C.
EDIT: you were correct, I didn't know what state "skipped" is
-50 for failed attempt.
the person mentioned might have had a WA/TLE on a previous solution, thus reducing 50 points from what they should have got.
This test #11 for DIV2, problem D is a killer :-D
Longest System test ever !!
Anybody can explain me why Bailando's 8304577 Div2 B problem works in 61 ms with this code:
2*k times sort n elements!
N is up to 100 only, you can sort them 10-100 more times and that will still pass the TL.
why is the system test taking too much time :/ ?? thats weird
why is the system tes taking too much time ???n thats weird !! :/
It seems there is 111 tests for problem DIV2 D...
There were a lot of successful hacking attempts today. So number of final tests is also very large.
More than half of our judging machines were switched off from Codeforces because we need them on High-School Contest and Saratov ACM-ICPC Subregionals Contest.
I thought this contest was going to clash with codechef's. I missed it. :(
Any hint with DIV-2 E ?
Thanks in advance
DP
It was asked here before...
Make DP in O(n3) and add presum for make it O(n2).
A simple DP solution in O(n2k):
Let dp[i][j] — number of sequences of length j which end with number i.
Then it's easy to make forward DP propagation:
dp[t][j + 1] += dp[i][j] for all t reachable from i.
We can also notice that all ts for some i form a subsegment (or two), so we can use something similar to partial (cumulative) sums in order to achieve O(nk) time.
Thanks so much, very well explained
(time zones in EST) Contest duration: 5:00 — 7:00 Addition of Hacks to System tests: 7:00 — 7:45 System Tests: 7:45 — past 10:15 Rating Addition: past 10:15 — ???
Russia School Competition pwned Codeforces Testing System's head for 254 gold !
wrong answer ,753 gold since the testing systems had a streak!
А когда начнется тестирование задач с дорешки?
Div2 Rating Changes posted but Div1 has not been updated yet.
Back to purple again! :)
These are two of my submissions, 8318803 and 8319108, the only difference between them is that in the first one I have used a macro at one place and in the second submission I havent used a macro at that single place. The observation is that when I didnt use a macro, the solution got faster by 31ms, so does a macro slow down a solution to that extent?
A macro is only processed by the compiler's preprocessor, so it won't affect your runtime. This is just a result of inconsistent judging.
Looks like my prayers for red were answered. 2201!!
Ha-ha, same here, 2202!
congratulations chaotic_iak, 2200 exact
edit: wait what? he is shown as orange
It seems that chaotic_iak is showing red in the "preview" option but yellow when you actually click submit.
Very weak tests for Div 1. A!
The solution before I submitted, which is wrong:
http://codeforces.com/contest/480/submission/8322271
gets AC.
My correct solution (http://codeforces.com/contest/480/submission/8307803) also gets AC... but it seems I shouldn't have resubmitted D:.
That
elseblock will never occur. Read the problem statement again; the first element will always be greater than the second element, sodead[g].first >= lastwill always be true.Need some help in Div 2 C or Div 1 A 479C - Exams. This submission 8310177 got WA for test 18 while this submission 8322341 got AC. Both codes are similar- the first one uses an array and the second one uses STL pair. Can someone please explain what went wrong in the first one. Thanks in advance.
Sort stinks. Try sorting with cmp1 first, then with cmp. But I'd rather write all this into one comparator.
if(x.a<y.a) return 1; else if(x.a==y.a) return x.b<y.b; return 0;
Try.