— Hey, It's me again. Plain to see again...
— Oh crap, it's PrinceOfPersia again :|
I'm here to introduce you: Codeforces round 362. It's gonna take place on 196th day of 2016.
I'm the writer of this round. Not as always, there are 6 problems. I hope you enjoy.
I want to thank LiTi and Haghani for testing this round, danilka.pro and GlebsHP for helping me prepare the problems and MikeMirzayanov for legendary platforms of Codeforces and Polygon.
The main character of this round is Barney Stinson (high five ;)) and you're gonna help him with his problem.
I wish you all lots of Accepted solutions and hope to see no Skipped solutions ;)
Scoring will be posted soon.
GL & HF!
UPD: We decided that the contest has 6 problems (in each division, 4 shared). Duration will be announced as soon as we decide, but It's gonna be between 2 and 2:30 (inclusive).
UPD1: Duration is 2:15.
UPD2: Scoring is standard in both divisions: 500 — 1000 — 1500 — 2000 — 2500 — 3000
UPD3: Check out the editorial!
UPD4: System testing is over. Congratulations to the winners!
Div.1 Winners are:
Div.2 Winners are:
Why are you talking to yourself? :/
You know I am Chinese, and I hate to read the foreign names such as Stinson.It is too hard for me to pronounce, so I decide change it in to “诗汀尚” in my mind.it is good for me to understand the meaning of problems!
But I it is barney.... I improve...
Nice to meet you again.
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
announcement shud have been --
The main character of this round is .... wait for it..................Barney Stinson
Please do not put minuses :(
You always share photos with hands... :D
;D
Depends on problems, for example the last round was quite easy for tops.
I agree. I wrote
sometimes it's not enough time:)It is Rated ??!
I think if this round won't be rated, they would write Codeforces Round #362(unrated).
hoping for an interesting problemset.. :)
I hope non of the problems statments will be "you have to help Barney Stinson to meet your mother"
Hope to See a Problem about the Brocode now that is going to be interesting to solve :D
I hope the problems are translated properly to English. Some of the problem statements in the previous few contests could have been better.
I extremely believe this round will contain less math problems than your past ones.
Is it rated?!
Will it be possible to connect to codeforces.com during contest?
I counted, Barney Stinson is truly have two hands and ten fingers, let's high five :P
Today is 2016/07/14, and it's 14^2 = 196 day of year =))
Wish all contestants luck =))
anw, this contest is my 40th contest, and I nearly get Expert =))
So long that rng_58 has participated on CF. Waiting to see Petr and tourist too.
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
I hope problems will be prepared better than Hackerearth June Clash 2016 (which is still haven't been rejudged)
Not my fault. shef_2318 prepared the checker for approximate problem(NOT ME) and we told admins to rejudge it and they did nothing :|
Your fault is that despite my warnings during the contest you haven't found bug in your checker. It was very easy to find, you just mixed up 1-indexation and 0-indexation.
Actually I don't want to offend you, just want to say, that quality of those contest was not high, despite the fact that the problems were the cool. Hope that this one will be better.
It's nice etiquette to say "sorry" instead of "that guy fucked up". It's not the first time I see your comment saying that sth is someone else's fault. Do you want to be necessarily mentioned by other organizers after you make a mistake?
i'm excited for this unusual round with 6 problems i'll try my best to solve atleast 3 of them.
Hope that, Barney Stinson face easier problems than the previous (#361) Div2 Round.
hope to get plus rating. I can't progress and getting frustrated :(
I think it's going to be an awesome round because the awesome man is its main character!
is it just me whose codeforces is working very slow and sometimes not even opening? its working slow since last night's contest, every other website opens instantly except codeforces.
Hope for 6 problems involving queries... :D
I hope to turn to cyan color ! :D
I have two wishes: 1. The English statements being clear. 2. Problem A loads up before 10 people get AC and we are like loading.. :/
I'm lol about the duration time)
You were the author of round #326 and now it's round #362. Pretty much awesome :D :D :D
It will be awesome if he canbe the author of round #632 :D
нестандартненько
It's going to be legen- wait for it......
Except for maybe two rounds years ago, it's going to be my first round on Windows. I'm trying to install some IDE right now. Wish me good luck!
#mylaptopbroke
Codechef has an online IDE if u need one :P :X
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
People should problem E first it has got 25000 points :P
Thank you, fixed.
there's a typo in the scoring
there is an extra zero in "25000" :P
I just captured a legendary pokemon
On 19th, SRM and CF Round back to back! :D
Congratulations to yao981113 for getting a perfect score on IMO! Celebrating by doing cf
Congrats ! Who is he IRL ? My student got silver and I'm also really happy.
'Barney consider a girl x to be better than a girl y if and only if: girl x has weight strictly less than girl y...'
That's how K-pop fans harm their idols by putting them on a diet and making them skinny. I miss their healthy bodies.
1 kilogram is the ideal weight.
You should be able to resubmit your hacked solution even after you've locked it. I feel like this is unfair for all those people who either lock problems for fun or by accident. Please bring justice. I know some people may copy other people's code, so maybe say able to resubmit up to 10-15 minutes after solution was hacked?
Wut?What if you copy someone's code? and btw you can't "lock" it by accident.
Well if your solution is hacked, shouldn't you at least be able to have a chance to redeem yourself? How about when your solution is hacked, you can no longer view other people's solution for that problem? I feel bad for losing 750 points because of unable to resubmit...
You should lock your code if you are really sure. I just lost ~950 points because I missed one case.
I guess you guys are right. Unfortunate, yes, but I am new to hacking/locking so sorry for complaint. Was fairly surprised and frustrated when I found out I couldn't resubmit. Ok, will reconsider to lock problems or not in the future.
If your problem is not locked, then you can resubmit if you are hacked. Resubmitting with a locked problem is totally unfair, because you could just upload another contestant's source code. Also, that's the beauty of it: "you can hack only if you lock, do you really want to?"
You can still redeem yourself by hacking other's solutions though.
This would be a very bad idea. If your not confident in your in your solution don't lock it. You can't allow someone to copy someone else's code in the middle of a competition.
Те, кто переводили условия задач, расскажите пожалуйста, зачем переводить все условия и при этом не перевести комментарии к псевдокоду по задаче D? Ответ на мой вопрос по задаче "внимательно изучите псевдокод" меня тоже порадовал. Я считаю, что человек, не обладающий британскими навыками, как, например, я, был принижен относительно самих британцев таким условием задачи. Мне пришлось очень долго из-за этого разбираться, что имели ввиду авторы задачи.
Ох... Вы можете и не верить, но я обнаружил это только благодаря вашему комментарию. В действительности, комментарии внутри псевдокода должны были быть переведены.
К сожалению, я это пропустил, думая: "Это же все-таки псевдокод!", просто забыв о том, что там есть важные комментарии, а ваш вопрос не содержал намеков на то, что комментарии не переведены, как и вопросы других участников. Если что-то из перечисленного пошло бы иначе, во время раунда вы обязательно увидели бы русские комментарии.
Можете считать, что это только моя оплошность (их я все же стараюсь не допускать, но, как видите, не всегда получается). Приношу свои извинения.
0.0e0 made my place Kappa
"**b can not be non-zero if a is zero**" That shouldn't be allowed
read again, carefully
I did, it means that either a or b must be positive, both of them can't be 0.
"b can not be non-zero if a is zero"
maybe this way: b has to be zero if a is zero
so 0.0e0 is totally fine (unfortunately for me... ).
0.0e0 a=0 d=0 b=0 what's wrong? b isn't non-zero
I believe DIV2 D is a really cool problem :D I got the idea what to do but I couldn't finish in time :'( Really nice problem btw :D Thanks PrinceOfPersia
What's the idea behind Div2D/Div 1B? Couldn't find the formula for a vertex :/ Edit: I messed the letter, meant Div 1B :D
Div1A: You go up from each vertex up to their LCA. In query 1, you add cost to those paths, in query 2 you sum and print. I saw a nice trick to go up to LCA — at each step go to parent of the vertex with the largest index, until both vertices converge. But there are other ways, e.g. using set to find intersetction of two chains, or going up to root and then down to lca.
I meant Div1B, I messed up, but thanks though :)
In Div1B, you first compute all subtree sizes; then for each node the expected time will be time of the parent + 1 + (sum of all subtree sizes of siblings)/2. Because by linearity of expectation, any sibling will go before current child with probability 1/2 and dfsing that sibling will take time equal to size of the subtree.
Thanks, I was not that far away from that :)
Thanks for this, I found it much better to understand than the editorial
thanks a lot! :)
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
Div 1 E: Heavy Light Decomposition?
Find the minimum on each path and then set that node to Infinity?
Typing problem in Google gives HackerRank task with editorial available and codes being public as a first link :)
How can I avoid TLE in C? I made a program with matrix dynamic, So My program's time complexity is(KlogN) but It got TLE...
The formula is 1 / 3 * (1 + ( - 1)k / 2k - 1). You just need to exponentiate 2^k modulo. Other computations are fast.
I got it. Matrix Computation was slower than I thought... Thanks!
Alternatively, you can note that it is sufficient to know the exponent
for prime p, so you only need to do log(mod) exponentiation, instead of log(N).
EDIT: 19131411
Hi, does that property works also for matrices? I mean if A is a square matrix and I the identity matris, then A^(MOD-1) = I mod MOD?
Hmm, it seems I assumed it works during contest, and I have no proof or idea for proof. Will try to google around to find whether property is actually true.
I also assumed that, it worked. In yesterday's contest I tried to used in problem C but doesn't work. I already searched and that property doesn't apply for matrices. I would like to understand why in this particular problem it worked
can you explain how to get such formula?
Consider the matrix approach. The matrix is something like [[1 1 0][1 0 1][0 0 1]], and it equals to ([[1 1 1][1 1 1][1 1 1]]-I). Expand it.
Div2C test 3 and Div2B hack? ;(
Div2B 0.0e0
Div2B hack 0.0e0
The one I was hacked on in B is:
2.0e0
answer should be 2
Kind of silly that a linear solution to Div2 A passes when such a nice O(1) solution exists.
Thats why it's Div2 A.
Problem C: 5.0e0 hah. After an hour and before locking i realized my solution will fail such thing so fixed + submitted again. But then another guy in the room already did 11 hacks :| so couldn't make use of this to full extent
I think pretest for problem B is very very not good :( :(
I think Time Limit for Div1\C was too strict, at least my solution is O(k * log(a) * matrix_multiplication), which I thought was fine, but I need extra optimization to pass pretest. 19127740. I guess it will be TLE on final Test :(
I don't know why, but codeforces said that my input for a hack is invalid, however, it is valid, please check.
if a is zero b cannot be non-zero
i found the mistake, thanks.
Thank you for the quick editorial !
Sorry I am wondering what is wrong with these two solutions... Please tell me what is my mistake div2B 19118037 div2C 19132537
Edit: i saw what i missed on div 2 b
Since you are using map, there needs to be a comparator function to compare its keys ie pair of bitset or bitset in this case. Apparently, there is no comparator function. Hence, the compilation error. You can either implement a comparator yourself and use it or change key of map to pair<long long,long long>.
Here is how to make comparator function: here (Although there is error in your logic as that gives WA)
Dayum, first contest in div 1, problem A scared me, I thought I needed to do Lowest common ancestor, then I realized it was easy when 30 minutes remained. but I wrote v/x instead of v%x in my code, and realized 1 minute after contest ended :(
I've always sucked at texting girls, so I didn't even bother with Div1D
Div 2. B: someone tried to overcome
0.0e0hack:"for(; i < posE; i++){ sum += string[i] }; if(sum % 48 != 0){ print '.', ... }";0.888888e0xDwhats the idea in Div2 D ?? how in general to approach probability questions ??
Learn math ;)
There's no "general approach".
But an important thing you should know is that expected value has linearity, i.e. you can add them directly. Then if you want to know the expected order of a node u, you can check how many nodes are visited before this node. There are 3 cases:
u's ancestors: they are always visited before u
u's decendants: they are always visited before u
else: they are visited before u with probability 0.5
Then the answer is simply 0.5(n-u's decendants+u's ancestors+1).
You should improve pretest quality. It really weak this time.
Very strong pretests would make hacking much harder and an interesting feature of CF would be rendered useless. I assume, that in some cases problem setters might even avoid particular corner cases on purpose.
Well your right,But that '0.0e0' ruined my ranking!
Same here
tricky case in div2 B all digits are 0 including answer :)
Couldn't hack Div.2 A C++ solutions with
0 2 1_000_000_000:'(, only one Java.Same with me
Wasted an hour on precomputing
for small values of n and trying to debug this whole thing in Div2 D only to find out that I have completely forgotten about the case when no additional subtrees are visited prior to entering the vertex.
Managed to correct the solution, didn't manage to submit it in time. Damn.
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
I tried to hack two solution on problem A_Div2 which use while loop with this test case :
1 2 1000000000
but I failed , I think it must give TLE on such solutions :\
10^9 simple iterations is easy for CF servers
If I've known this earlier, it could've saved me from getting WA53 with formula :p Thanks for the information.
This round's problems is so interesting! I like this round although i don't get many points
too much hacking in one round
Why so strict limits for div 1 B? I used double variables for answer and O(n) complexity and my solution runs in 750 ms(C++).
Ques 2nd should be rejudged. Your test cases don't contain 0.3e2. The solution 030 is also passed.
if the number before this decimal is zero, then the number after 'e' must be zero. Read the problem statement.
The problem statement on Div1 B says "The second line contains n - 1 integers". This implies that there is a second line (just with 0 integers). Yet we are not given a blank second line. This is the only thing that broke my submission, isn't this test data invalid?
Кодфорц, не лагай. Пока висела страница с отправкой решения, я случайно добавил лишний пробел в код и ткнул обновить. Так одинаковый код отправился дважды и -50 к посылке.
Но все равно, Hello div1, отличные задачи, авторам спасибо.)
The feeling when you have almost coded Div1F when the contest ends, and it would have passed the tests.
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
Can someone help me understand why my B gives TLE? it should be linear.
Your text to link here...
I found it.
what I did was manually add for each node v, the sum S[w]+1 of the number of sons of each vertex w which is a son of the father F[v] which is not v.
I should have just done S[F[v]]-S[v]-1. fail, sigh.
WA on pretest 1 in Div2B. Any ideas?
Maybe it contains invisible characters.
In your solution, line number #52.
It should be "a < len". Why would you like to run till "a <= len"?
Update:
After correcting above mentioned error in your code, I was able to get AC on it. 19134004
You reminded me of this blog when I first started CP
After running your code locally, it has character with code 0 after the output but before the newline.
Ehh... Thank you :/ I thought I would destroy my laptop after 10th submission :P I think that these types of invisible characters should be ingnored by the checker like it is done with "endl" at the end. It would be nice.
hey something is seriously wrong with the final testings.I submitted the same code again after the contest and it gives correct ans on on your system and my PC too.Please recheck it.You could even compare both codes.Problem "DIV2B"
During Contest- http://codeforces.com/contest/697/submission/19126571
After Contest- http://codeforces.com/contest/697/submission/19133631
Yeah. You are right. Codes are same but output of 2 submissions are different. :/
Somebody answer this man ^
Ch is uninitialised, so atoi result might be wrong.
.
Unlucky for me... If you use fermat little theorem on div2E... if you have a multiple of mod-1 then you cant let it stay at 0 to use formula... must say if (n==0) n=mod-1;
Why did I think that all strings are unique in div1D? :-(
Another one easiest way to drop 200 places! 19126039 19134075
Forget to write "if (y < 0) y += MOD — 1" and lost C.
Thought that all strings are unique and wrote c[x] = a[i] instead of c[x] += a[i] and lost D.
GGWP :D
Really nice round, and a great problem set!
As always from PrinceOfPersia :D
Did anybody else find the problem statements, well, just "too much"?
I found it was kind of bitter sweet. I enjoyed the puns ("slapsgiving" in A was also nice). I also did not like that it took the focus out of the problem.
BTW, isn't it the three eyed raven who has time traveling capabilities. Is Jon Snow the next three eyed raven? Can't wait for next season!
How to fuck up your computer in three simple steps:
Read Div2C/Div1A
Assigns two huge vectors after seeing MAXU and MAXV
Profit
I am new to python,and I wonder if there a way to read data like using
freopenincplusplus?if it has, need I delete the input code before I submit the code? Or it there if a way that I don't need to delete the input code like using
ifdefdefinition in cplusplus?You can use sys.stdin.readline().strip() to read your lines.
Hi can someone help me out why this solution for DIV II/Problem C is failing on testcase 39. I tried with lot of smaller test cases but couldn't figure out mistake.
http://codeforces.com/contest/697/submission/19167786
I can't solve your problem. But I want to put forward my idea about the problem. Each edge of a graph can be described as (u,u*2),(u,u*2+1). So we can use the larger node to record the cost of each road. http://codeforces.com/contest/697/submission/19431887