Hello everyone!
Today, there will be another CodeForces Round at 18:00 (Moscow time). It is a Div. 2 contest, but Div. 1 participants can take part out of competition also.
My name is Vuong and this is my very first CodeForces round. Hope that this is not the last one. I would like to thanks Maxim Akhmedov(Zlobober) for help me preparing the round, Maria Belova(Delinur) for translating problems into English, and Mike Mirzayanov(MikeMirzayanov) for such a great Polygon and CodeForces.
Be sure to read all problem statements before contest ended. Hope you enjoy the contest.
Good luck and have fun!
UPD The contest is over! Thanks all of you for participating!
Here is top 5 participants:
The editorial can be found here.
Would Score distribution be dynamic?
Hopefully not, last contest was dynamic and it was not rated (even if those two are not related)...
yes , all the problems will be about dynamic programming . ok
Thanks for the problemset. Good luck to all! :)
I can go to bed before the system test over!!!! Because my university will cut off the electricity at 11:30, and my computer can last for only 3 hours without outer-power! What nice news!
mathlover is a super star in my heart,can I admire you?
In our university, The building #15 has electricity supply all the night so I can wait for the system test.
Can I go to your dorm and code with you?
My dorm is very mess now... Maybe next time.
Never mind~
How hard to study in China :D Economy))
This is just some of the rules of the school,because the contest time is at midnight in china,but there are still many hard-working students like mathlover got a red name.
it is because of some fool schoolmasters and teachers but not economy...
Китайцы, успокойтесь!
please translate it to English~THX
If I'm not wrong, this is the first round set by a Vietnamese! Good job! :)
I don't think so... http://codeforces.com/blog/entry/8248
ll round =)) you're wrong :p
I have been wndering....how many languages does Delinur know?? :D
Usually, problem statements will be written in English, if the author wants it to be put in an international site.
I know don't the exact answer. But one day during a conversation, she said this "But I can translate your message into 4 other languages if you want :P". It means that she knows may be 5 or 6 languages or more.
22:00 is good time for me to participate. Thank you for your contest.
You didn't even register for the contest
I went to register page at least 3 times but failed to register because of some network problems. After coding problem B, I realized that I didn't register for this contest.
I hope codeforces won't be down today :S
Countdown time and Announced time are Different. I am confused.
Both of them are correct. Which announced time have you seen?
I wonder will the time be at 18:00(MSK) in the future or 19:30(MSK) for mostly?
I hope most rounds are on 18:00 MSK in the future. That 1-hour switch has really some impact on us(Chinese).
...but 17:30 CET is too early for me, and you can guess what is my opinion about 16:00 CET...
I hope for 19-30(MSK)
I think :
codeforces Round 277(Div. 2)== Happy Birthday contest !!(for MikeMirzayanov's daughter)!!:)
bhut fikar hai tumhe mike mirzayanov ki beti ki .-- written in HINDI now translate it Delinur
please write in English!!
I can't read this comment.
He said "Why are you so concerned about Mike Mirzayanov's daughter ?"
I like mike Mizayanov and him daughter. she is funny and smart and cute and ... daughter!!
I just translated it Majid, reply to terminated .
See previous Edit
i wish we won't have hack or other problems in this round
I bet that there will be one more blog post by DmitriyH after this round.
Punish him/her please! (S)he wants solution
Кто-нибудь до раунда читал вообще русские версии условий?
Да нормальные же условия че говоришь то
How to solve C ????
You always need to fix only a half of a string you are staying at.
I did exactly that. Got WA on pretest 2. I am sure its a silly mistake on my part. :(
Was a silly mistake... :(
But How to do it by minimum operation ?
Assume we are in the first half of a string. You are to find the segment which you must fix (leftmost and rightmost positions in the first half). Now you can choose the best way to visit all the segment, there are only two of them:
right - pos + right - leftandpos - left + right - leftOf course, you also have to do
min(abs(s[i] - s[n - i - 1]), 26 - abs(s[i] - s[n - i - 1]))operations for every i=1..n/2What if both left and right are on the same side of pos?
You can take the absolute values, giving
min(abs(right-pos)+right-left,abs(pos-left)+right-left)Well, my implementation ( 8656932 ) was a bit different. So I had to give that extra check, where both left and right were on the same side of pos. Lelby also gave that check ( 8659477 ), but he commented differently. That's where I got confused.
You have to move from first char which needs to be fixed to the last one (or opposite way if shorter).
For example if number or fixes for characters in string
aaaaacdefgis 0, 3, 4, 5, 6. Then if you are on position 2, you move to position 5, if in position 3, move to 2 and then to 5 and if on 3, then move to 5 first and then to 2...We need to operate only with one half of string. Consider we choose left one. If p > n/2 just reflect it. Them found two indicies — 'l' first letter which need to change and 'r' — last letter which need to change. Minimum action for movement will be
min(r-p,p-l) * 2 + max(r-p,p-l)if p inside[l;r]. If p is outside first we need to go in this range. Now we know how much ticks we will spent only on movement, during this movement we'll be on each letter. So just calculate cost of each change in range[l;r]. Result will be movement cost + change cost.O(n)
I hope my approach is right :)
How to solve D ?
Define root of a set as the node with minimum (av, v).
Now we can consider all the sets with that root (each of them will be counted once).
It can be done via simple dymanic programming.
http://codeforces.com/contest/486/submission/8659287
Take a fixed minumum number low then maximum value is low + d.
Find number of sub trees which has at least one node with minimum value and does not has any node that bigger then low + d or less then low. It can be done with dynamic programming in O(N).
Overall complexty is O(ND)
Thank you both very much! I've got it.
Идея решения по Е:
Не смог реализовать, потому что не знаю как оптимально искать наибольшую возрастающую подпоследовательность; как быстро искать все элементы, которые могут заменить данный; устал и хочу спать.
В последовательности 3 4 1 2 этот алгоритм не работает. Правый элемент 4 подпоследовательности 3 4 никуда нельзя сдвинуть, однако 4 содержится не во всех наибольших возрастающих последовательностях.
Ну вот еще одна из причин, почему я не стал писать это решение)
Why some people didn't get overflow in first problem when they calculated sum of first n div 2 even numbers and calculated sum of first (n+1) div 2 odd numbers?
I don't know. I made an unsuccessful hack because of this!
Same here :(
It overflows, but both overflow the same, so when they subtract the overflow is gone. If you can find a case such that one overflows but the other doesn't (very unlikely and might not exist because 1018»1015), I think their solution will fail. I spent the last 15 minutes on W|A (Wolfram Alpha) trying to do just that, but haven't succeeded. A program would probably do it faster though.
EDIT: Actually I think now that even if one overflows and the other doesn't, subtracting them will again mean the overflow didn't matter. 281474976645119 makes one overflow and the other not, but it still works as the overflow is ignored.
Yeah I noticed this after my first unsuccessful hack :D
let's hope for system testing!
Apparently some solutions failed for the input "3037000499"
This doesn't seem to break one solution I'm looking at. Can you show me a submission that fails it?
This one fails (i failed to find this test in time). 8652729
Ok thanks. It's different because they find the sum of all numbers and subtract twice the sum of the odds, and since they divide by 2 after overflowing, subtracting no longer always removes the effect of the overflow.
How to solve problem D(problem D is very hard!!)?
My sol is to DFS each note as that node is the max node, then use DP.
Every valid set can be uniquely determined by the smallest node in it.(If there are more than 1 node has the smallest value, we choose the one who has the smallest id). So let's choose an node to be our special node, and starts to dfs under the limit that our special node has the smallest val and smallest id and the gap is no more than d. We get a sub-tree of the original one. And considered sub-tree, You can use dp to count how many way you can choose a set which contains the root (our special node)from the sub-tree.
It's a classical dp problem on trees. dp[node] means the ways to choose a set which contains the root and the others node come from the sub-tree of it. And you want to calculate dp[x] for the the node x, you just go through his son, and we can either not choose the part from this son's sub-tree or just take it, which has dp[son] ways. So in total (1 + dp[son]) ways. Multiply the sons choices up. And we get the ways to choose a set from the sub-tree of x which contains the node x.As we can let every node in the tree to be our root(special node), we can get the answer for the question.
Check my code hope that helps.
A was easy, B was interesting, C was time-eater and interesting too.
+100 to persistency
nice
Wrong answer on test 156... :D
You scared me great ... Luckily there are only 40 tests!
:D did you get any point from this question?
I did the same thing recently. But I was submitting my OK solution to A LITTLE DIFFERENT PROBLEM and got AC after 30-40 changes.
Ban Samsung please.
Translation: he asked me to send him solutions of A, B and C
wow the request is so interesting
this site has no report system?
Nope.
Did you sended him smth? No? There is no reason for ban then. Yes? Then both should be banned.
I don't think temak would've asked to ban him if he has sent something o_o
It's very same situation as — "You got SMS message: 'Mom! Please, send me 300$ to X-XXX-XXX-XX-XX I'm in big trouble!!!'. You can ignore it, and then there is no criminal. But it's possible to find the owner of this number, send the money and then arrest him, because his attempt was succesful". So there is no chance that Samsung will be banned, because solution wasn't sent! But still, temak posted this image and waiting for something.
that's why Iphone better than samsung:D
дорешиваю codeforces training season 2 episode 7.
внимание вопрос: это специально так сделано, что пока идут систесты, ничего другое не тестируется?
У попыток одинаковый приоритет. Вперед тестируются те, которые были сделаны раньше.
how to print negative number (A problem) from squee_sp00n's A
It seems that nobody solved E using large prime modulos like me.
What was the intended solution?
I solved it in that way :)
I think it is to count the number of indexes belong LIS of length i :) If there is only one index of length i then it must be type 3, otherwise type 2.
Could you explain what do you mean by "large prime modulos" ?
I solved it simply using segment tree for some calculations.
Quite surprised there's an antihash testcase for 2^64 modulos :|
While constructing testcase for string hashing is not so easy — hacking similar solution for this problem is very easy (and it is well-known olympiad problem). Just take a look at sequence 2 1 4 3 6 5 8 7 10 9... How many LIS it have? :)
Yes, i realize it's not hard to make such testcase, my bad for assuming anything modulo something is hard to hack :)
Will the contest also be unrated as the past contest???
No :)
Don't think so. Last one was unrated because of problems with servers etc. Rankings are just always updated few hours after the contest.
Sigh
Top4 are once again unrated, two of them registered in the past 24 hours. I'm not saying they are cheaters, but that happens way too often lately :\
Awesome problems by the way, solved all 5! Thanks, author :)
why getting wa in test case 16 in 486A - Calculating Function .. my soln 8655625 it gives correct output in my compiler
Overflow problem. N can be 10^15 so N*(N/2) will be something like 10^29. You can read this comment, to understand why it may work on you compiler http://codeforces.com/blog/entry/14672#comment-196477
I HAVE A COMPLAIN IN CONTEST IT SHOWS PRETEST NOT SHOW WRONG OFTER CONTEST ITS SHOWS WRONG ANSWER WHY YOU WOULD NOT SHOW AT THAT TIME?
Welcome to CodeForces :D
PRETESTS =/= TESTS, obviously.
This is the format of the competition. Your solution is tested on some part tests that usually do not cover all corner cases and maximal constraints. After the competition your solution is graded on the official tests.
pretests are a very small fraction of the entire test
I don't know the exact reasons, but if I need to guess, there are probably three reasons for that:
1) Because of pretest/test separation, there's less need of computation while we're in contest; that's why we can get faster feedbacks.
2) It's much more exciting and fun to wait for system testing to see your actual results.
3) Hacking mechanism is based on this feature; this is also related to second reason since hacking is fun.
what a joking u its not fun always you show wrong answer at contest but today you cheat me it;s not fare.I wana my full points its your mistake not mine otherwise i'll never participate in your contest
What's going on in your head?
This is not your first contest, right? There are few tests when you submit, but all tests are tested during system tests...
this contest is unrated ?
Why are you asking?
for Funny :D
that My_First_Lady seems to have used different templates on C and E. and submitted C after E in two minutes.
just saying.
Yes, that's very suspicious indeed. Sadly I've never seen anyone banned for such reasons which is why we have tons of unrated accounts and/or teams ruining top5 of Div2.
Очень понравились задачи. Получал удовольствие во время решения задач. По чаще бы таких раундов! )
see this two code for 1'st question whats differnt.
include<stdio.h>
include<math.h>
int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));
} else { i=n/2; k= i*(i+1); j=pow((i+1),2); printf("%lld",k-j);
}
} 2.
include<stdio.h>
include<math.h>
int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));
} else { i=n/2; k= i*(i+1); j=(i+1)*(i+1); printf("%lld",k-j);
}
} but first shows wrong answer and second shows correct answer what the difference between them
...
In case the guy really doesn't understand smth and not trolling: The first programs uses pow function (http://www.cplusplus.com/reference/cmath/pow/) The declaration of this function:
double pow (double base, double exponent);— that means result for even integer numbers could be 255.99999999999 instead of 256 since for float(double) numbers those values are pretty same. But herej=pow((i+1),2)you're doing cast to integer. So result could be 255 instead of 256 and no one can guarantee which one exactly.Most of the solution failed test case 31 and 39 for problem B. They didn't know when to say NO :P
We're lucky that we don't need to output "START" / "STOP". Most of us don't know when to say "STOP" :D
Heh, had solution for C, but just assuming that there's only one turn, not that the cursor always remains in the first half. Much more complicated to write that way : S
codeforces should try to improve their website performance during contest..
8652439 Why can this solution for problem A can pass all the data? It is an O(n) solution!
The loop
is so simple, that compiler (with optimizations on) turns it into
because loop is really just incrementing s by 1 on each iteration, and we know precisely the number of iterations. Thus it becomes O(1) solution.
oh...One of my friend attempted to hack this solution with a big number... two unsuccessful hacks... Sadness
Why my solution to A 8652258 passed all tests? It almost wrong. Can someone answer me
Country wise rankings table has been updated
Mind if I ask why 4 out of 5 top are unrated?? I wonder if multi account is OK!
Why the next round will be called "Codeforces Round #277.5 (Div. 2)", not "Codeforces Round #278"?
Because next contest that will be after 7 day called "Codeforces Round #278", "Codeforces Round #277.5 (Div. 2)" was created after this contest, and will start earlier