Good day)
Welcome to the last Codeforces round in this year Good Bye 2013. This round will be unusual because it will be common for participants of both divisions.
The problems were prepared by authors Gerald Agapov (Gerald) and Svechnikov Artur (ikar). Pavel Kholkin (HolkinPV) and Vitaly Aksenov (Aksenov239) also help us to prepare the problems. Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.
UPD: Score distribution is similar to standard — 500-1000-1500-2000-2500-3000-3500
UPD2: Thanks to all participants, we hope everyone enjoyed prepared tasks. Problem analysis.
UPD3: Congratulations to the winners of the last round in this year. Rating will be changed in a few hours.
1. BaconLi
2. Egor
3. liympanda
We wish everyone good luck, high rating and excellent mood)
Is there a handle changing feature?
No, you can only choose the handle name when you register, then you will not be able to change it later.
Maybe you misunderstand him, usually at the end of every year there's a gift from codeforces to its users, last two years it was allowing to change the handle and ahmed.korayyem asked if codeforces will allow changing handle this year too.
BTW, why are you surfing codeforces in incognito mode?
Oh, sorry for my misunderstanding.
Actually I use normal mode when surfing on codeforces, but when I want to visit codeforces "register" page without logout I have two options, open other browser software or use incognito mode, but it's faster to use incognito mode, so I use it :)
Actually it happened last year. (http://codeforces.net/blog/entry/6290)
I would like to change my handle this year too as a Codeforces gift.
Hello, but gifts are things other people give to you. They are not things you request, and then get.
I mean, I could be happy if I see a Mike post saying: "You can change this year your handle as a Codeforce gift like last year. Enjoy it."
It seems this contest would be rate?
Yes, for both the divisions.
Although have lessons tomorrow morning, going to take the one of the most important contest:) That's why I love Codeforces!
Just want to get a good ending for this year.
ahh... at last a post about 'Good Bye 2013'.
will the problems be as hard as div2 contest or div1 contests?
happy new year to all ... last contest of this year ..... so get highest rating .. wish u all the best for all
Good luck!!!
Advanced Happy New Year to everyone :)
Can we have hints on problems' difficulty? I can't imagine how the contest is going to be rated and the same problems will be for both divisions!
Good Luck to everyone...!!! And Happy New Year...!!!!!
how many problems there will be??and i think as the contest for the end it would be better to have extra duration.
Well, actually it's good bye GPA! Having an exam tomorrow out of 30% and I still don't know what the course is all about and yet I'm taking part in this contest :D :D
Me Too :D
LOL :D :D
Me Too :D
why BaconLi got +25 and xa.mohsen got +2 only with same comment????? ( ! )
I have got GPA of 4.
like a boss.
Good for you :D Mine is 3.66 but it will drop like hell after this semester :D :D
GL HF everybody :D Happy New Year 2014
Also, good fun && have luck!
I never really understand why the score distribution is announced during the last minutes before the contest? Can somebody explain me this? :)
One million dollar question !
For this contest, obviously to hide the fact that there are 7 problems instead of 5 :3
"Score distribution will be announced before the contest."
contest starts in 30 seconds!
Happy new Year! Good luck in new year!
Can anyone tell how solve 379F - New Year Tree ?!
http://codeforces.net/blog/entry/8929#comment-146418
Should we check every most distant from the root vertex?
I think this is a old problem, as you can find it here http://www.codechef.com/COOK38/problems/RRTREE ( Editorial in this link too)
I enjoed the contest, but the problem F is really well-known.
UPD: english one take a look at problem H
And problem A is from Codeforces Gyms (2013-2014 CT S01E01, problem J)
Well, I can excuse Div2-A =)
On problem C I made this:
while (vet[u] <= l) ++vet[u];
I realized that it would time out after locking :/, but then I remembered that GCC might optimize this stupid mistake I've made, and it did! :D Bye bye 2013!!
Holy random? I successfully hacked person with
while(v[i].a<=v[i-1].a) v[i].a++;
and g++ too:)I failed to hack someone's code that had a similar loop and I was wondering how did his code pass! Now I've got the answer!!!
can u please expain what is wrong in this loop ?
Simulate the code with this test:
Good bye
Codeforces Round
for this year...Insha'allah... we will meet again... :)
We get "Happy New Year!" instead of "Accepted". So nice!
At first, thanks for this great contest! I enjoyed it very much except for one thing.
Because of "Codeforces is temporary unavailable", I lost some hack points that I should be able to get... Although it's my fault that I came up with a powerful corner-case late, but why codeforces server have been weak for a long time in spite of much demand? I really want codeforces team to strengthen the server...
Any better idea on D than a hardcore DP + Euclid's Extended Algorithm (which i didn't manage to implement, by the way).
My solution was something like this:
Let X = s1, Y = s2. We count the number of appearances of X, Y, XY, YX, YY (you can prove that XX doesn't appear). In the latter three, at most one "AC" can appear, so you bruteforce all 8 possibilities. You don't need Extended Euclidean; the bounds n, m ≤ 100 are very forgiving for an immediate brute force.
(I'm not sure what you mean by hardcore DP. In my opinion, my solution above is not DP at all, so probably different solutions.)
(My solution turns out to fail, so it might not be the correct approach. Take the above with loads of salt.)
WA 23?
I have the same solution and got wa 23 : \
You must prevent overflow while calculating count of AC's in tested variant.
No, your solution seems ok, I simply missed the fact that I can brute-force through all cases in ax+by=x, your solution was the same as mine. What i called hardcore DP were some recurences I used instead of simple formulas to write the solution faster in order to calculate the number of X,Y,XY,YX,YY,XX (that's why I used DP, I didn't have to treat cases like nu XX and different formulas). Somebody else also told me about this solution and his also failed because of www.wolframalpha.com/input/?i=50th+fibonacci+number (int instead of long long)
Yes it is correct.
AC sol: http://codeforces.net/contest/379/submission/5585945
note, I for some reason also take into account XX, YY :|
how to prove it?
My solution has a recursion to calculate the how many AC are in kth term, inside a dp that generates a possible second starting string, inside another dp that generates a possible first string. Is that hardcore enough? :p
Yes, it is. Your recursion used memoisation I supose? Can you explain a little bit more of your solution, please?
Well, at first I thought knowing the number of AC in each of the first string would be enough. If no. of AC in first is 3 and in second is 4, then the third will have 3+4 = 7. Then it will continue like fibonacci sequence. But then I realized, what if the string is like this ABBBBBA and CBBBBC.
Even though the first and second string has count zero, third string has count 1. So, in order to generate the sequence, I must know the starting and end letter of each string, along with the count of AC.
So I used dp to generate the first string. Only three letters would be used in the string, A, C and any other letter ( I used B ). So the parameter was dp ( first letter, position in the string, last letter used until now, number of ac ). At each position I could place one of the three ABC. I proceeded accordingly.
Once I reached the end of first string, I called for the second string right from there. I had to carry few information from first string to the second. The first and last letter and number of AC in the first string. Apart from these, everything else was same for the second string.
So the second dp parameter was this dp2 ( first letter of first string, last letter of first string, number of ac in first string, first letter in second string, position in second string, last letter in second string until now, number of ac in second string ).
Once I reached the second string, I called a function to calculate kth term. I passes the following info to the function recursion ( f1, l1, ac1, f2, l2, ac2 ). Using this info, I could calculate kth term in O(k).
Here is my submission: 5581341. Seems like a lot of calculation but it's really not a lot. Each of the table is filled only once.
Bruteforce. Count of "AC" in s1, count of "AC" in s2, first and last letters of both strings ('A', 'C', or any other). And then for that information we can calculate count of "AC" in k-th string.
And total time is (n / 2) * (m / 2) * 3^4 * k ~ 10^7.
Can someone explain why my submission to D fails?
http://codeforces.net/contest/379/submission/5584738
3 1 1 1
Answer is:
A
C
Thanks,yes I forgot to take into account the case (n==1) || (m==1)
hey, how did u move to the next line without leaving an extra line (between A and C)? i didnt know it was possible to do that without using
Block
option.All we need is just some
magic =)
the
Accepted
verdicts have been changed toHappy New Year!
how cool is that? :)Now, if someone had 0 accepted submissions, they're also in for a bad year :)
Did you guys notices that in status page instead of accepted, it is showing happy new year ??
Happy New Year!
instead ofAccepted
....Nice way to wish us... :)
Like this innovative idea ... :)
What a perfect contest! I loved it so much! I would like to thank all of the authors and the preparation team! Happy new year to everyone!
fail of the year? 5573462
how? o.O
It is not enough time to write 300000 long long numbers with cout. His solution wrote only the part.
sync_with_stdio to false?
he didn't use cin/cout, so sync_with_stdio wouldn't take affect must be the sort function with terible random then o.O
rep(i,0,n) cout << A[i].ans << " ";
oh, sorry my bad :p
I try it with sync_with_stdio(false) but still TimeLimit :-??
with sync_with_stdio 5586030
with scanf and printf 5586108
both of them TLE :D
Try it one time with
int
instead oflong long
.In general case using
long long
costs so more thanint
.Wish it works in your case.
It is surprising, I used cin/cout and it passed
There are two sort in this, which accounts for double the runtime. And then adding to that, there is the cout function.
It's surprising. I got accepted with two sort functions and using cout : 5578740
He didn't pass references in sort comparator.
Problem A is exactly same as uva 10346 — Peter's Smokes.
lol, there is at least 6-7 similar problem like this at UVa. That's why it is the giveaway problem of the contest :)
LOL, the fan in your profile image moves while looking on the screen and not directly looking to it, and it stops when just directly look at it :)
Happy new year~ However, who can tell me why I WA at test #22? 5584508 I can run a correct answer on my computer. TAT
I have submitted the problem C in java7 5577222 it got runtime error during the contest and I realized that why it got RE? so I submitted the same code in java6 in practice,it got accepted.5585065 Did it consider as accepted or not?
Your Comparator do not adhere to comparator contract — it should return 0 on equal elements. Java 6 sorting algorithm is implemented in the way that for all compariosions any outcome is possible, but int Java 7 sorting algotrithm (which is TimSort) sometimes only 2 outcomes are possible and when 3rd one is returned it is assertion error
Thanks thats why you are such a good programmer we learn the use only and you know the implementation of the method too.From next year I will use the library method when I know about it completely. As for my solution whether it will be considered as failed or passed because it got accepted in Java6(in practice though).
My this code for problem C has given me TLE in 11th case ... As the input is very big, I'm unable to know the reason... would anybody help please ???
There's a while loop inside a rep(i, 0, n). The while loop may be executed as many times as the size of the bi's, which is O(n). Hence the overall complexity of this solution looks like O(n^2) which is not good enough since n could be 300000.
In while loop value of 'i' is being increased... it should be just like 'i++' portion .... total complexity should be O(n). Shouldn't it ??? Or am I missing something which isn't known by me ???
And the 10th case is big too... n=299999 ... I haven't got TLE in this case... :O
Actually I want to know the reason ... while submitting, I never thought about this verdict ... But I've got !!! Please clear me... :(
nevermind.
The variable comes from ai and is as big as 10^9, so even a single while loop may not end in time. The ai's in the 10th case is small but is large in the 11th case.
But I'm astonished that, I submitted without using that while loop... and got TLE too, at the same case ... :O
My submitted code without inner while loop is 5589598
what is the reason behind this ??? :O
I even didn't use STL map too ... :O
your solution with int instead of long long: 5589677
Thanks a lot... riadwaw
Now my code submitted in the contest time is AC too... while loop was not the problem... The reason is only
__int64
...Too frustrated... didn't want such finish in this year ... ;(
Just for not knowing that __int64 takes more time than int...
Anyway, good thing is it's not in any onsite contest... (trying to take it positively, though failed) ...
Also you could pass the arguments of cmp by reference, like 5589749.
Thanks johnathan79717 ...
known another thing by you ... :)
You're welcome :)
I would have passed F, if I would have used scanf instead of cin.
I did not expected that time limit would be kept so strict.
May be I should start using scanf and printf for each and every problem :(
Feeling very very bad :(
It is not a good gift at all :(
http://codeforces.net/contest/379/submission/5585325
http://codeforces.net/contest/379/submission/5581511
You may find this interesting: http://codeforces.net/blog/entry/5217
I know this, But most of the time, I use cin here in codeforces because they give a lot of margin in time in solutions, but this time I was wrong :(
I am wondering why they give 5*10^5 queries, they can simply give 10^5 queries as it is normally done, it would be possible to solve the problem without IO or constant optimization.
I have the same problem, but the problem is not in input, but also non-asymptotic optimize allowed to pass tests =(
Does anybody have any idea how will they give the ratings? Because this contest was very different from other ones. Div1 contestants were in the same place as Div2 contestants and the contest was rated for both of them. Will there be considered a Additional points for Div2 Participants? (Hope so!)
Since normal rating formula calculates the expected position based on your and everyone else's rating , there is no reason it wouldn't work fine in this match.
why it is wrong answer http://codeforces.net/contest/379/submission/5584330
You don't need this
ans='\0';
when dealing with strings.thank you .....
Surprised to see Petr and tourist not try to solve number F!!!!Instead they were busy in hacking!!Whats the secret behind this???
maybe they didn't realize there are F and G?
They can't resist that when there are lots of gray and greens and blues in their room :)
I've spent more than an hour trying to solve F, but couldn't.
may be you were distracted by seeing lots of grays and greens and blues.. just kidding :)
This problem is almoust same with RRTREE.
Oh the last luckiness for 2013, I submitted my F in the last second :)) I had done F before, but at the last moment I realised that I got wrong range :< I resubmitted and lost about 600 point :'( However alright <3 Happy new year everybody <3
So sad:(
5583857 on contest
5585359 upsolving
A diff of the files would be more useful :).
actually you are peter50216 or rng_58 or not :)
or peter58?
Egor was real quick in problem D :D
Can anyone explain 379C - New Year Ratings Change New Year Ratings Change why 5579353 gives runtime error ] while submission id 5585888 gives accepted answer... Thanks in advance...
I think that your bool cmp is wrong. The bool cmp must return the value that a < b You can have more detail in here Sort
Still not getting why this is resulting in runtime error
A usual line in the quicksort function is like:
Now, consider an array of equal elements. For the above line to work, the
a[i] < a[x]
part must of course return false for equal values. Otherwise, the indexi
just walks outside the array (which may or may not result in Runtime Error). Your previous version of thecmp
function however violated this, resulting in incorrect behavior for equal values:It returns true when a is equal to b, which is an error.
Addition: this error is similar to writing a comparison function which always returns true or always returns false. You can try for yourself to design an efficient sorting function which accepts such a comparison function and does not generate nonsense in this case.
Thanks for your response and information.
But wont our lives be easier to implement operator for structures and easily use sorting ? 5576735
If one day i decided to use two function to sort an array i would rather to var static variable in my class and a switch case in my operator<.
C++ allows to do it either way. It's up to the programmer to decide what's more convenient.
Such a bug can occur in a custom comparison operator operator as well as in a standalone comparison function, and will have the same consequences.
I don't know exactly how sort() works but the comparison function you give must be a strict weak ordering function, so in particular
cmp(x, x)
should return 0.but why would that result in RTE?
Egor says this for same problem in Java — http://codeforces.net/blog/entry/10161#comment-156164
I hope that has nothing to do with same variable names for array a[333333] and rating a.
I had submitted this code in the contest
http://codeforces.net/contest/379/submission/5581511
and after the contest, I submittted this.
http://codeforces.net/contest/379/submission/5586307
And when I submit it after the contest, it gets accepted
May be time limit decisions are affected from the load on the server at that time.
Please tell me what reason could be for this undesired behaviour.
too bad, looks like load is the cause of that 50ms difference that took that away from you :(
I think this has made me learn few things
1. use scanf/printf everywhere.
2. try to do low level optimization when time limit of your solution is tight.
or better in case of cin and cout, use ios::sync_with_stdio(false). as scanf can be slower in case of "%c" and in that case we have to use getchar() for speed.
but that again has some issues, you can not interleave scanf/printf statements, As I have habit of using scanf/printf cin, cout alternatively, I will not prefer to use ios::sync_with_stdio(false);
pls update the ratings:)
F can be solved by either Heavy Light Decomposition or maintaining Diameter Pair with LCA. (HL: 1100ms, LCA: 550ms in C++) I had hard time implementing HL decomposition, I couldn't make it in time.
cognition solved problem A,C,B in 4:02 , 4:18 , 5:00 min !!!!!
LOL. seems he was not alone XD.
Yeah, seems strange. In problem B and C indentations are different. In B 2 spaces are used and in C tabs. Or he just wrote the contest on two different computers coding two problems simultaneously with each hand on each keyboard :D
The indentation is also different in problem A, so I think there actually were 3 computers and he coded with his feet or any other part of his body (I don't want more details :-) )
Does sharing an account break any rules? Though it's probably hard to prove.
Though he was not alone, he is not in the top 10...
I've conducted an investigation and banned him. There are multiple evidences that he took part unfairly :(
Round statistics
pls change the ratings
I wonder, will cognition get banned?
Check the final standings again. cognition is no longer there. Probably removed. Also, setters congratulated Logic_IU for winning the round.
He was there, just before I posted the message.
Yes, removed. That's good.
Are they planning to update the rating next year or what?
Happy New Year to everyone!
I think if we have more problems in contest the results will be more reliable...
Wish we have more of these contest (Both Div , 7 Problems) in future...
i just noticed that
Accepted
has been changed toHappy New Year!
even in contests other than today's round. i wonder if this is intentional, or some kind of bug with the site?They probably replaced the string globally (the value of Accepted string) and hence the effect. :)
I doubt they intended it for all but maybe there's no easy way to do it for just one round.
Yes, the same message is in Russian interface. And how it could be a bug? :)
cant wait for the year end rating anymore :(
well by the server time it's the new year right now(happy new year) but the rates aren't updated yet.
It's still 24 hours left from this year.
please update the rating, I want to see the rating before sleep,TAT
UPD3: Congratulations to the winners of the last round in this year. Rating will be changed in a few hours.
You just shouldn't go sleep for a few ours.
hope ratings will be updated this year :D
please update the ratings quickly, wishing only a "Happy New Year" will not work
where are the ratings?! :(((((
it was really nice contest!
but is it possible that rating gonna be updated this year? or we'll have to wait for the next year? xD
being specialist, how did aangairbender manage to solve all the problems especially Problem G of Good Bye 2013 (which remained unsolved in the contest) in virtual participation? who is he?? who helped him (if someone helped him)
He used FPC to solve the problem. A bit unusual.
He seems to copy other's sources.
Where would he find the solution to G?
Here http://codeforces.net/contest/379/submission/5585359
from here :D
http://codeforces.net/contest/379/submission/5585359
Just finished coding problem G — it got accepted right after it passed the examples, but one hour spent coding it was so non-exciting to say the least.
How about a non-proliferation treaty on cactus problems? :) They rarely are conceptually different than corresponding problems on trees, but they are so much more painful to implement.
Actually, I had twice as much code as if it were problem on tree. And the extra code is almost the same, just new parameter when handling the cycle.
Well, you also have to find the cycles in the first place, correctly handle cases when several cycles share a vertex, etc. That's exactly my point — nothing conceptually different, but harder to implement.
Best formula to create
trashsomething "non-exciting to say the least" from the great problem.Really good formula, explains everything!
In this case the problem on the line would probably be worse than on the tree, though :)
I would say, that you can add one more step: instead of "problem on tree" use "problem on tree that contains the only cycle".
If possible:
Could you share your approach to problem G? At least an overview to be able to read your solution. Thanks.
OMG!!! i finished watching two movies after the contest, and rating is not yet updated. i dont have patience anymore. going to bed hopping that i will see updated rating in the morning.
Ratings are updated. Check it out :)
Finally after ~5hours waiting, Rating has been updated! Now I can sleep :) Happy New Year!
Great match! And I have got the highest rating in this round. It will be better if Welcome 2014 Round which has the same rule as Good Bye 2013 were added.
thanks for this awesome round! :D happy new year everyone...:D
Thanks for the round and interesting problems!
Congratulations for everyone, who's color was upgraded :)
actually, red to yellow is a downgrade of rating, not upgrade.
but yeah, good idea about the photo! :D
I think that's purple to yellow. To be more accurate, pink to golden perhaps? But we get the idea. It's cute.
+203 points, it was impossible :D Thank you Codeforces for the good year!
Happy New Year's Eve!
Screencast
Which soft do you use to grab screen? Does it work without fails and crashes?
CamStudio. Never crashed so far
Good bye 2013, good bye Div1!
Same with me ;) . But anyways Happy New Year in advance !
Next contest will be Welcome 2014?
for problem A, tests 16-21 are all same. why?
This was such a nice contest! I crashed D because I used some variables as int instead of long long.Still,I managed to get ABC pretty fast and as a surprise, the rating increased over my epectations.So, thank you for the contest, and also thank you for the site, it really made my day.Happy new year to everyone!
Hello, 2014!! (in Japan)
So easy!
Great round to say good bye to 2013, I am equally hopeful for great contests this year!