Всем привет!
11 августа в 19:35 MSK состоится рейтинговый раунд Codeforces #367 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.
Автором задач являюсь я. Это мой первый раунд на Codeforces! Советую ознакомиться с условиями всех задач. Надеюсь каждый найдет себе задачу по вкусу.
Хочется выразить благодарность координатору раунда GlebsHP за помощь в подготовке контеста, Yury_Bandarchuk и IvanVan за помощь в подготовке задач и прорешивание раунда, а также MikeMirzayanov за замечательные платформы Codeforces и Polygon.
UPD: Разбалловка 500-1000-1500-2000-2500
UPD: Разбор
UPD: Соревнование завершено. Поздравляем победителей!
Div.1 winners:
1.anta
2.W4yneb0t
3.sugim48
4.uwi
5.Kmcode
Div.2 winners:
2.Shining
4.AwD
5.stjepanp
Автокомментарий: текст был обновлен пользователем NBAH (предыдущая версия, новая версия, сравнить).
kiram to tarrahe in contest
The problems producer is just blue like me.Why can I use those problems to be purple?
Why do your comment is hidden every time.
Simple brief statement, thanks a lot and hope high rating change for everyone =D
Sorry but that's impossible :(
yeah... these are CF contests.... (;
i have to wait 10 minute compiling my answer -_- it was shit not contest :(
RIP English
And as usual... scoring will be announced later! (maybe just before the contest! or after the contest!) Whyyyyyyyyy?!
Does it matter?
then why they announce?!!
It matters during the competition to help you divide your time
Hope this contest will be better than last Div2 only contest. Hope there won't be such a long queue during the contest because of so many people. (Hate the feeling knowing the contest is unrated after a 2hr-hardwork at midnight)
How do you know about last contest? Oh it's your new Div.2 account...
maybe he had new girlfriend ??!
Round he's talking about was unrated. I think that's a reason he is still out of rating.
Look at his profile "Registered: 25 hours ago" -_-
short GL & HF , I hope statement will be short as this :)
short GL & HF, I hope statement will be short as this :))
Hope for nice problems and strong pretests :)
Could someone explain to me the reason for downvotes on this comment?
It's Codeforces. You never know what happens to your comment.
Well said Tweety. (y)
Maybe you are new! but you can use up and down vote buttons instead of this comment!
Well said TD. (y)
In hindsight
FYI, I downvoted
but downvoting others won't decrease your negative contributions.
I hope the community loves me again :) I wrote a lot of stupid downvote worthy stuff to earn -47. Guess I won't be doing that again.
actually we upvote a comment if it is useful, fun, interesting ,... and we downvote a comment if it is useless, spam, ugly,...
if you want upvote then interest us!
That's not how this works. You never know which comment will be upvoted and which ones will get downvoted.
Downvote doesn't seem to work for me whenever I hit downvote the comment rating stays the same, is there any reason for this?
because others upvote simultaneously...
Today, give a stranger one of your smiles. It might be the only sunshine he sees all day.
+1 for pikachu dp
I hope this round will be more interesting than previous one)![](/predownloaded/dd/96/dd9630e2c362657a3ae04a357054c34b3aa6e6e5.jpg)
Sorry, because of unknown reasons, I counldn't upload the picture)
it's not an unknown reason
the reason is that you don't know how to upload a picture
anyway, click (CTRL + P) and put the link of the picture
You're supposed to get the link to the image rather than the google image link https://i.ytimg.com/vi/LNX4dFILlm8/maxresdefault.jpg![](/predownloaded/dd/96/dd9630e2c362657a3ae04a357054c34b3aa6e6e5.jpg)
Ok,thanks)
"Are we poisonous?" the young snake asked his mother. "Yes, dear," she replied — "Why do you ask?" "Cause I've just bitten my tongue! "
I think They are using their time for coding :P so, they don't wanna waste their time and using random comments :P
MSK means??
Moscow Standard Time. Google it or click the link in the contest's description
or ask here!
Round of div2 member?
I hope there will not be an easy task!
cried my contribution ((( Dislike for each my post((( soon the absolute value of my contribution will surpass Errichto
Dislike me who wants to help me!
As u wish
sorry but i upvoted for u :)
Fact : 367 is a prime number
a round without the IOIers ?
Not many of them are Div2 anyways.
Did you just assume their division? triggered
Надеюсь никакой геометрии в С и адекватные D, E. Ну и конечно же без смакования момента после отправки решения до получения результата.
is it rated ??
Why everytime there is someone ask that?
if a contest is unrated, they will tell it in announcement ... maybe as an update
I hope this contest won't have so many commercials for games and movies. Just clear tasks.
You think the one about avengers was with help of commercials?, u think they ask codeforces community to create probs about them?..
Yes,dude ... NEVER :)
Too late for Asia......
Too familiar :)) :))
Ah
I have a dream, that there will be more contests ends before 12 m.n. in my local area for me to get at least a purple... At this rate it would probably take several months to wait for a contest which my brain can function normally.
Randomness of likes and dislikes will one day be used as a random number generator :v
Like if you disagree :v
Today is Codeforces NBA match ;) Wow!! That's great to play on computer too. Thank u very much NBAH. Best of performance for everyone in this match :)
Is there anyone who could help me to solve this problem or give any other approach.Thanks in advance http://codeforces.com/blog/entry/46505
[user:jibancanyang]Come on,believe yourself,and tonight you must be the candidate master!
a;;;;;;;;;;;;;;;;flbgoqwgowqeiufhhdvbka;bdkasbf;efowofowjo#inwohndlandsfl!
I guess you will be hidden again.... 0.0
Anyone here knows how to unregister I'm not sure if I will be able to write codeforces today PELASE HELP
Just don't submit anything or open page of participants >> find your handle >> click the red (X) button to the right of your handle to unregister yourself
If you don't submit, your rating won't be affected.
We should wait 9 days for next contest :((
We should wait 9 days for next contest :((
And two week for next div 1 contest!
So far!
wow! it's a long time for you!!!
You can still practice with div 2 contests, and it's more comfortable since there's no rating on the line.
The Olympic season is here and we have some Codeforces rounds scheduled too. We should have an Olympic themed contest.
Wish Good luck to all :)
Queue is back. :/
my source is still in queue for long time. does this happens to anyone else?
Codeforces queue :/ . Please do compensate for the time we have lost in this and are still losing.
queue 2 : the nightmare
make it unrated:/
Автокомментарий: текст был обновлен пользователем NBAH (предыдущая версия, новая версия, сравнить).
i hope it's not going to be unrated today!
i hope it's not going to be unrated again!
Auto comment: topic has been updated by NBAH (previous revision, new revision, compare).
I guess it's another unrated contest, unfortunately.
Stupid person shut ur mouth
LOL
I thought the queue problem was solved! I submitted B. Waited for 5 minutes, still in queue. Went to solve C, submitted C, found out B was WA. And now C has been on queue for 3 minutes. wtf! -_-
Thank god it's unrated for me. I'm out.
how did you make it unrated for yourself?
he participated out of comptetion.
My solution to C is not even in the queue. I am not able to submit it! -_-
Finally was able to submit by uploading the source file. I am having this problem since many days, not able to submit code that is copy-pasted in the editor.
Please, don't make it unrated.
It would be unfair for participants who got WA after one hour. :/
Who told you life is fair ;)
Besides, it will be unfair to those who got their solutions judged in time. Its just like contest time. Some countries benefit from the time, some have troubles. You won't complain about that would you?
if there's long queue, no one will get their solutions judged in time. and really a wa verdict after a long time makes it unfair for the contestant.
R u sure u got wa after an hour? I really think what ur saying is false..All my submissions passed is <=10 mins...and just look at the number of people who solved each problems.. the stats say ur lying
One hour :o ? I submitted program at 5min, 10min, 30min, and 70 mins. I had to wait for more then 5 mins for pretests only for 2nd (which was at 10 min) Rest all submissions were quick in judging (less then 5 mins for sure)
Congrats, good work! ^==^'
Wow, really great curve of number solved. And this is only halfway through the contest.
Что-то баян задачи...
On a completely off topic, how many people on codeforces follow Silicon Valley (TV show) ?
Well, I don't think you can get your answer if you ask this question here. After some yes/no, people will stop replying due to negative votes (spamming). You should rather create a poll externally and give the link here.
C was a dp problem right? I was starting to get it but I didn't have enough time to debug :(
From the fact that it was called "Hard Problem" and that some people submitted it in 4 minutes, I am guessing there is a non DP solution but sadly I don't see it. Can anyone share their solution?
Can you explain what your DP solution was? Just so I know if I was on the right track (if you don't mind).
d[i][t] = minimal cost with last element i, and t = 1 if we don't reverse it, t = 2 if we reverse i-th string.
Glad to know I was pretty close lol. Thanks for the help.
انت مخنث ؟
Lol I like my hair though so I think I'll keep it (if you're making fun of my hair).
Edit: Also I'm 100% male.
العق مؤخرتي
بندوق مغكر حالك بتعرف تستخدم google translate ?
Don't even bother replying him.
Apparently some people did write dynamic solution in 5 minutes e.g. #19788803. I'm impressed.
Yup. You could view it as a graph problem and then it is finding the shortest path in dag from 1 to n that could be done in O(n + m) There are 2*n vertex and every vertex has max of 2 outgoing edges.
I was considering representing it as a dag too. Thanks for the help.
let's call l[i] is the list of strings and r[i] is reserved string of l[i]. Then we have dp[i][0] means min cost of list from 1->i that l[i] is not reserved, and dp[i][1] means l[i] is reserved. First dp[i][0] = Inf, if l[i] >= l[i-1] dp[i][0] = dp[i-1][0], if l[i] >= r[i-1] dp[i][0] = min(dp[i][0],dp[i-1][1]). Then dp[i][1] = Inf, if r[i] >= l[i-1] dp[i][1] = dp[i-1][0] + c[i], if r[i] >= r[i-1] dp[i][1] = min(dp[i][1],dp[i-1][1] + c[i]). Res = min(dp[n][0],dp[n][1]). If Res = Inf then Res = -1. That is my solution and it passed present test.
I implemented a 1D DP solution. Here is the link to the solution.
I don't like man :P. When I get 20 minutes penalty and a WA just because I wrote a statement twice . :D
And by the way was it only me who took Manhattan distance in Problem A and passed 6 pretests? :D
I used taxicab geometry too, and I found out I was wrong about it on the 7th pretest :/
same same :P
Спасибо большое за интересные задачи!
Got response from judge after 20 min from submission.(long queue)
Also sad as i got to know it was wrong after 20 min. :(
Will this be a rated contest?
How to solve D? Thank you.
I solved it using Trie
It can be solved by trie, easily. I supposed that you know task to find the biggest xor of two elements in array ( you can find solution on internet easily too). Here you only need to story how many times you went through some node ( because sometime you must delete some edges).
Look at Problem 1 in this article: Trie Tutorial
In my solution we write every number in binary using 35 bits, we use leading zeroes if required.
I let the map M[i,j] save how many integers x satisfy that when you only look at the bits in the first j positions you get i.
Both updates and queries can be done in time![](https://espresso.codeforces.com/88294808ad60afb3ad6f759c5dd5d4cceab7aa07.png)
Dang I wish I'd thought of this I made a mess trying to implement a Trie
Use Binary Trie.
This is my idea, haven't tried it yet.
Convert every input(number) to binary system. Put it in BST (1s go right, 0s go left). Make sure that all numbers in binary system are the same size. So 6 -> 110, but if max value is 1e9, it became 0000....110.
When you search start from leftmost digit and go through BST and pick side different than current digit. When you reach the last node it's your answer.
It looks like greedy solution, can you prove that it right in all cases?
2^t > 2^(t — 1) + 2^(t — 2) + 2^(t — 3) + ... + 2^0.
That part is not so hard, because the every bit is clearly more important than all of the bits to its right, combined .
Thanks.
It's efficient for searching. But wouldn't it be hard when we're gonna do deleting operation on the tree?
I would do same as search, when you reach last node, go up.
Wow, CF servers are fast, my first hack on this submission (19791945) takes over 5 × 109 iterations and it ran in sightly less than two seconds.
It's not the "extremely fast servers", but probably the O2 optimization that cut the number of iterations.
What O2 optimization ?
Had no idea Tries were this standard, so many people solved D.
I think my rating will drop to below 900 :/
you guessed right
It is ok I am only doing this for fun for now.
you mean you get fun by solving 0 problem?
I solved 2 actually just couldn't get them right within the contest time and 2A got rejected during testing(WA on test 41) because I didn't set precision to 7 digits after decimal point.
well try to upsolve the rest 3 as well. It won't help unless you gradually develop some new techniques, will it ? :/
Anyone else think that the time limit for E was a bit too strict?
I don't know but if the target was split O(q(n + m)) and
then it was not strict.
There was a solution in q(n+m)? Wow... at least I managed to implement a working treap for the first time
I wrote the same O(q*n*log n) with treaps as well. I think it was a bit too tempting to come up with some online algorithm that uses treaps of segment trees to fairy solve this problem.
Yep, The good intuition to this solution represents the structure as beads that connecting by a thread with a neighborhood, in this case, you can split O(n + m) thread and connect it by another way.
So, basically a quad-linked list? Thanks!
Yes
any full description of "quad-linked list"? is it smth like sqrt-decomposition of list? Google gives smth strange.
Thanks in advance
Tried treap but TA11:(
UPD just wondering how the hell is possible to distinguish fast c++ qmlog(n) from slow java qm...
Basically there is set of nodes representing the fields of the matrix. Each node is connected via a pointer to its upper, lower, left and right neighbor.
Statement that rectangles doesn't share common side makes so much more sense now ;) Actually I'm surprised that not much people came up with this solution, as it isn't complicated at all.
Ok thanks, already read it in solution, seems to me that coded something similar once
Thanks! So trivial yet so hard to think!
What about this O(QNM) solution?
http://codeforces.com/contest/706/submission/19802812
I know, this solution utilizes the fact that modern machines are very good at copying large amounts of memory around.
This just proves that the time limit itself, although the problem and its solution are very interesting, doesn't make any sense.
This round is totaly interesting :) Although I couldn't solved problem D (wish that i could learn Trie earlier) but today it is fine!
That moment when ur solution is in queue for more than 15 min. And On top of that you get a verdict as a wrong answer . Ruins everything :(
i always thought that the feature of rejecting the exact same submission was useless. after this contest i really appreciate it. it saved lots of precious 50-points as i had to submit 10 solutions to see one of them got into the queue.
okay really codeforces what the fuck is happening!
i get WA after 30 min from submit ! :)
it should be unrated like Eran Contest
yup...i got WA after 20 min of Submit.
Same Here :(
Yeah now lucky people who didn't get Wrong answer will vote down this comment :)
if someone solved their solution correctly at one go, it doesnt make them lucky, it makes them more aware and smart
they are smart because they didn't get WA ?
they are smart yeah but they are lucky too because they don't wait 20 min and lose many points and resubmit solution also lose 50 point :)
in 20 min i can solve B instead of fix small mistake in 'A' problem
smart only isn't enough
Just solve all problems and your rating won't decrease:D
u are so genius bro congratulations :D
Does anybody know why my submission 19801619 got compile error? Thank you!
the queue was so long in the start of this contest please consider this.
Who else has used graph to solve C?
I spent an hour implementing D using multiset, so I guess this will be my motivation to learn trie finally :D
Do you mean that you did it using standard multiset? Can you post a link please
http://codeforces.com/contest/706/submission/19810298 It should work, I tested it with a bruteforce solution and there was no difference, but of course I might be wrong. Edit : It works if anyone wonders :)
Can you light upon your solution? Your approach looks interesting. Implementing Trie is too mainstream for this problem. :P
exact same thing happened with me .... difference being that I could debug my solution after the contest ended :(
I see many solutions who got WA#5 in problem D, like me. Good round!
WA in #5 is probably from not considering that 0 is always in the set.
Yeap, you're right.
I knew that the problem D could be solved by using Trie but I failed to implement it ;(
same here...I had bugs in my remove number function...got it working 5 minutes after the contest ended. :(
This is the second time I know that a problem can easily be solved by trie but failed to implement it. I think tries are tricky to implement so people must have coded them once and use their own code every time I guess.
Solved D 5 minutes after the contest ended! I'm too slow!
I think, this contest should be RATED.
I quite don't understand what everyone is so distraught by long queue of +/- 15 minutes. Every major competition. APIO 2016, CEOI 2016, JBOI 2015 all are really famous for their judging fuck ups. Why does CF need to make this unrated simply to prevent decrease of people's ratings, when such major competitions often end up deciding people's future and college etc.
The competitions you mentioned don't have time penalties.
When there are fuck-ups in our local onsite contests, we usually blame the system saying to the organizers that in respectful contests like Codeforces rounds such things would be considered very wrong and wouldn't be allowed. Codeforces should stay an example for a good platform with good contests.
It was a really bad idea to make Eran's contest unrated. Cuz now a lot of people are upset with the system's speed and it would be kind of unfair to leave it as it is.
E was very similar to problem G from Petrozavodsk Winter 2012 (standings)
(the problem is great anyway)
I think this contest should be rated. Judge lags were not bad than past contests.
umm... I wonder how to hack Q1. How did you hacked Question No.1?
of course because u didn't get WA :D !!!
No... This contest is much better than Round #365.
Making this round rated proves how unserious this website is
Submissions are being judged after 20 minutes. I came to know about my run time Error of question after 20 minutes. This round should be unrated. Many people would have been affected by this.
What is the approach for D?
Use binary Trie https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems
Wow! I never imagined a trie can be used in this problem
Same approach :D. I finished debugging my sol two minutes late though.
At least you knew what to do!!
Any idea what Test 41 in A is? I assume it's one of the tests that was used to hack a bunch of solutions in A.
Precision Error,
One of my friend that has almost same solution but used float instead of doubles got WA on this test.
"In queue" for 15 minutes after submitting the question, has becomes a permanent feature of codeforces :(
Make it rated please i have solved A and B under 20 minutes. and i am happy to do that !
19793914 00:20:53 Hazemzz A - Beru-taxi Java 8 Accepted
20 mins, 53 seconds is not ''under 20 minutes'' :)Make it rated please i have solved A and B under 20 minutes 54 seconds. and i am happy to do that ![user:latvian]
Nice contest! Brief statements. Unfortunately, finished D solution two minutes too late :/. Thoroughly enjoyable nonetheless.
In Problem C. I marked my dp[100005][2] with INF as 10e15 it gave a run time error. But when i use INF as 10e14 it works. Language used C++. Can anyone explain ? Thank you.
Edit1 : It's behaving in a weird manner. Sometimes i get correct answer but sometimes i get run time error in custom invocation. I will update once i get to know the reason behind it.
There are 10^5 numbers, so if you add 10^15 10^5 times, you get long long overflow. Maybe that's why
In c++ upto 1234567890123456789 is accepted(>1e18)..then its not possible that 1e15 will give any kind of runtime error :D Check again may be some kind of segmentation fault error must be there.
Always better to keep it as -1 and then add additional checks :). I have made the same mistake before.
Only I get #WA41 on A?
"Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed
1e-6
."cout
just give the answer that its absolute or relative error does not exceed1e-5
.Fuck that shit, I`m out
A solution for D without using trie (though it hasn't passed the systests yet). Let's store all numbers in STL multiset. To perform the third operation, we can find y that gives maximal xor going from the leftmost bit to the rightmost. Given the 10^9 constraint for x, 30 to 0 is enough. Let's say we know some binary prefix of the answer, and that a number in multiset with such binary prefix exists. If x has 1 in this bit, we can just find the the minimal y with such prefix (using multiset.lower_bound()), and if it has 1 in this bit, then add it to the answer. If x has 0 in this bit, we can find lower_bound(answer | (1 << i)) and see if it does exist and isn't greater than answer + (1 << (i + 1) — 1), in order to guarantee the existence of such prefix in multiset, then add to the answer.
It will be unfair towards Eran who has created good problems, if this contest is rated
the lag in this contest wasnt as bad as the lag in the contest you are referring too, at most it was ~20 min, you could have moved on to some other question while it was in the queue
No it won't. Just enjoy solving the good problems and stop complaining. The queue wasn't long enough for the contest to become unrated.
I got a weird WA61 on problem C. I am sure about the idea, and probably the WA is because of checking whether we can have an answer. Why is my check wrong?
I've changed the way for checking the possibility to have an answer and now have an AC. Does anybody know why did this happen?
O(nmq) solution for E. AC in 2464 ms =)
Can be improved to 2121 ms and 1669 ms with SSE.
I did it, too =)
http://codeforces.com/contest/706/submission/19808842
Have you tried combining your second solution with Duff's device?
That will not work for my cycle, because i have not only unrolled it, but also grouped some operations.
Can we expect editorial today itself??
will there be an editorial ?
Here was my approach to D.
It is easy to keep up with the set by using std::set and std::map to count the multiplicities.
The real deal is how to deal with the query ?.
First, change the given number to binary. We notice that we can take the high-value digits greedily.
Therefore, we do the following. We set X as the optimal number in the set. Iterate through the bits 29 0. If the binary form of the given number is 0, we want 1 there. If not, we want 0 there. If there are no numbers in the set that satisfies this, we would have to go with alternate path.
Here's an example.
Assume that 111011, 011000, 101000, 000010 is in the set, and the original number is 001101. We want the first bit to be 1. Indeed, there are two such numbers — they are in the interval [32, 64). How do we check that there are numbers in that interval? By using lower_bound!
So we chose [32, 64). Now for the second bit we want 1 as well. Such numbers are in the interval [48, 64). We see that there is one. We want 0 to be the third bit, and such numbers are in the interval [48, 56). However, there are no numbers in that interval! Therefore, we would have to go with the third bit 1.
Continue this, and we would have our optimal X. Now compare ORIGIN XOR X and ORIGIN and return it. Complexity is![](https://espresso.codeforces.com/056a4e2d6729d83db0128a301ec30357f61ce8a1.png)
I thought of this, but I couldn't convince myself that this is correct :/
Wow! Great idea! I thought about greedy solution but I could not implement it. As for me, you solutuion is better then in ediorial. Thank you!
Where is the editorial???
Kindly have a look at this test case generation program for Question 2 . I was unable to figure out why it was showing (invalid input verdict ) when I tried to hack this submission . (http://codeforces.com/contest/706/submission/[submission:19798157])
#include<bits/stdc++.h> using namespace std;
My code :
Please comment below if any one know the reason. I don't want to do that mistake again. But I was unable to figure out my mistake. (http://codeforces.com/contest/706/hacks/246947/test)
There is should be "\n" after last number.
Have a look at this . It was also showing wrong . i have done that which you said .
http://codeforces.com/contest/706/hacks/246902/test
You're printing extra space after numbers. My generator — http://codeforces.com/contest/706/hacks/246817/test.
Kindly have a look at this test case generation program for Question 2 . I was unable to figure out why it was showing (invalid input verdict ) when I tried to hack this submission . (http://codeforces.com/contest/706/submission/[submission:19798157])
My code :
Please comment below if any one know the reason. I don't want to do that mistake again. But I was unable to figure out my mistake. (http://codeforces.com/contest/706/hacks/246947/test)
I think in hacking, you have to add a new line at the end of input
I tried that also but it did'nt work out .
test
There would be a extra space after printing values of each array in the above link but not in the original comment. Checker is strict for hacking maybe.
Have a look at these :
http://codeforces.com/contest/706/hacks/246936/test
http://codeforces.com/contest/706/hacks/246902/test
In both there is extra space at the end of second line.
Thanks I found my mistake .
You say there are 9999 values, but only print 9998
No I have print
cout<<n;
explicitly after the for loopFor hacking you have to give input, not input generating program.
No , If the inputs are more that 250 Kb size you are required to write a generator program .
Last line should be cout << 2 << endl;
See this
Extra space
in C anyone got WA in test case 18?
Me too, I set
oo = 1e9
, however, it should be1e18
.Hope we will never meet that mistake again.
nice contest ,but slow system testing :P hoping to get high ratings
Sum of lengths of strings <= 100000.
The sum of lengths of all strings is at most 10^5, not the length of every string. So the worst case should contain all the strings with length
, something like 315.
Total length of all string is
1e5
. Incasen = 1e5
, length of each string is just 1. Totally it isO(n)
.It was given in the question that the total length of the strings won't exceed 10^5.
Why did you change your comment? Nobody answered your question so far.
The number of operations is linear because every string is compared a constant number of times.
Thank you guys for making this awesome contest.The difficulty of problems is moderate for Div.2 contestants and have great and beautiful "solved" distribution.I kept thinking and implementing the whole contest.It's really exciting and fun.
Some personal experience: I got 2 RE on D for missizing the trie node pool and got 1 WA on C for a typo.When I start to handle E, I first thought to cope with it by splay tree(considering the difficulty of previous rounds) and failed to finish it.Right after the contest I figured out a better way(maintaining the position of original elements and do some interval add/distract, which can be completed in O(n) time because there is no online requests).
Long queue appear again in this contest.I guess this is caused by problem A.Maybe the special judge part in A make the judging machine laggy.
This contest is made by and for Div.2, this is awesome.Although the difficulty may seems lower than previous Div.2s(finish 3 and you and done, finish 4 for a high rank,finish all to go Div.1 directly), but it is really enjoyable for Div.2 contestants.
Hope you guys can make more great contests.
I don't hate this contest. I'm just expressing my bad opinion about the problemset, which I didn't enjoy, authors did their best anyway.
I do not consider this contest as "good". Here's a yellow point of view:
-A was okay, like normal A
-B was such a standard task...
-C yet another DP with same pattern. There was even a pretty similar problem on CF once.
-D come on, "code a trie" problem. There are many such problems in the internet. Seriously, even "find maximum xor" typed in Google would probably result in finding the solution immediately.
-E that was a fun one. Nah, just kidding :P If coding N treaps is a model solution, then wonderful problem 10/10. MrDindows did something awesome, check it out!
I'm not saying this contest was bad. But IMHO this contest should have been an Educational Round.
Which one?
This problem set is so much interesting. Really I enjoyed it to much.
Somewhat structured and verbose code for D: http://pastebin.com/Md2EtNXF (submission)
Can someone tell me why my solution to C (java) timed out?
I saw some other recursive solutions also passing, so did I make some mistake in the implementation?
Here's the code : 19801924
Thanks.
Edit : I got my mistake.
Задача D. В варианте третьего запроса нужно найти максимум из ксоров данного числа и одного числа из множества. В тестах же возможен вариант, когда мы ни одно число из множества не берем. На мой взгляд это грубая ошибка условия.
Это же эквивалентно тому, что мы берем число 0(по условию 0 всегда присутствует во множестве), а 0 xor x = x. Или я не так понял?
Да, вы правы. Не заметил эту часть условия. Думал, множество пустое вначале. Прошу прощения за комментарий, содержащий неоправданную клевету.
Someone can help me? In problem D, I'm use basicly pointers, in my computer it is ok, but in CodeForces gives Runtime Error.
Submission
Why my all solution change to 'skipped' and I out of competition ?
It happens when someone cheats.
Why I get different answers between custom invocation and problem test?
In 19790402 I got WA on test 79, However, I thought I got the correct answer when I used Custom Invocation.
What the problem is???
I passed this problem by replace %ld with %d, but I do want to know Why I get different answers between custom invocation and problem test?
By the way, I'm glad to know how to cause this WA, since I thought there is no different between %ld and %d in GNU G++11 5.10 :)
Got 141 points, wow!
Помогите пожалуйста. Почему на 11 тесте превышение по времени?( 706B - Интересный напиток
Thanks for such a nice contest :)
where is the problem set ?
here.