Connector's blog

By Connector, 11 years ago, translation,
I'm glad to see you on Codeforces Beta Round # 64.

Today I am the author of the tasks. I'm a student of Tyumen State University.

I want to thank all those who helped me to prepare the round: Nikita Durynin (Austeritas) for the pair ideas for the tasks, Dmitry Bochkarev (Walrus) and Chernenkov Alexey (Laise) for the testing, Artem Rakhov (RAD) for coordinating the activities, Maria Belova for translating and Mike Mirzayanov (MikeMirzayanov) for a great system.

Today you will visit the Walrusland and help the common citizens and government to solve their problems.

Good luck for everybody, let the best man win!

Winner is Petr. Congratulations!

Analysis

Announcement of Codeforces Beta Round #64

• +150

 11 years ago, # |   +14 What if the winner is a woman?I hope this will be a good contest!
•  11 years ago, # ^ |   +18 And I hope we see a woman winning a Codeforces contest.That'll be really nice
 11 years ago, # |   +3 good luck ! :D
 11 years ago, # |   +3 Good rating!
 11 years ago, # |   +13 i wonder how log will it be beta rounds?
 11 years ago, # |   +3 Hi, I'm new to the format... Will prolly crash and burn but i hope to better myself gradually. :) Cheers! :)
 11 years ago, # |   0 can anyone tell me what is idea behind C ?
•  11 years ago, # ^ | ← Rev. 2 →   +7 I think, the main is that if a * b = rev(a) * rev(b) then a / rev(a) = b / rev(b).UPD: Ой, а вот где у меня и была ошибка :(
•  11 years ago, # ^ |   +15 a / rev(a) = rev(b) / b.
•  11 years ago, # ^ |   +3 It should be a / rev(a) = rev(b) / bFor a / rev(a) , you can transform it to its lowest form c / d by dividing numerator and denominator by their gcd and store (c,d) -> a in a map.This way, for each x, you can find all the numbers y, that can form lucky pair (x,y)That was the main idea and after that there were different approaches. I iterated over all x , from 1 to max_x , and for each x , did a binary search on y to find the minimum y in [1,max_y] that has at least w pairs.
•  11 years ago, # ^ |   0 I tried to write exactly this solution, but...> This way, for each x, you can find all the numbers y, that can form lucky pair (x,y)How? And what did you store in the map?It seems it was EPIC FAIL
•  11 years ago, # ^ | ← Rev. 2 →   +5 map, int>pair means a fraction first/second. You must divide first and second into gcd.
•  11 years ago, # ^ |   0 I made it, but I still can't understand how the answer is calculated.
•  11 years ago, # ^ | ← Rev. 3 →   +4 The binary search can be avoided.Let's first solve the following related problem:Given an ordered array of n elements, return two elements that multiplied are bigger than C. If there is more than one answer return the ones with the smallest product possible.The most basic idea is iterating over every pair in O(n^2)A more sophisticated algorithm would be to iterate over each element A and do binary search to find an element B which A*B >= C (equivalent to your idea) O(n*logn)The fastest approach is to keep two pointers, one starting in position 0 (A) and one starting in position N-1 (B)if value(A)*value(B) >= C, B--else A++O(n)It's straight forward the reduction for the original problem.
•  11 years ago, # ^ |   -8 How much memory required , O(n*n) where n is number of primes < 10^5 ?
•  11 years ago, # ^ |   0 Someone gave me negative , what did u not like :P
•  11 years ago, # ^ |   +5 > I iterated over all x , from 1 to max_x , and for each x , did a binary search on y to find the minimum y in [1,max_y] that has at least w pairs.… using a binary indexed tree.  That was a missing part in my case.An alternative way is, as daffes wrote, to do it linearly (starting from (x, y) = (1, maxy), increase x if there are not enough lucky tickets, decrease y otherwise).  I had completely overlooked this approach.
 11 years ago, # |   +17 @Problemsetters   - Can anyone frame questions that  Petr can't solve.?.
•  11 years ago, # ^ |   +7 I think that Petr himself can do it.
•  11 years ago, # ^ |   +6 I think that too Petr will solve in 1/2 hr at most.
•  11 years ago, # ^ |   0 Petr isn't as good as Chuck Norris. Chuck would never finish this round in 1:43 adding 8 Hacks.
•  11 years ago, # ^ |   0 your two statements are contradictory , what did u say ?
•  11 years ago, # ^ |   +19 At least at TopCoder Chuck wasn't that good =)http://www.topcoder.com/tc?module=MemberProfile&cr=22771049
•  11 years ago, # ^ |   +6 oh my God, Chuck is in high school!
 11 years ago, # |   +7 Is it possible to change display names? I would like to have balakrishnan_v
•  11 years ago, # ^ |   +3
 11 years ago, # |   0 Why it's posible input like "wordinput....." in problem B. Text Messaging...Description, i think that limit the end of a WORD with only one ( . , ? , !) or none at all ?
•  11 years ago, # ^ |   0 Or "....." meaning more text that the input that i can see..
•  11 years ago, # ^ |   0 Yes, “...” means that only part of the input is shown on the page.  I do not think that currently there is a way to show complete test cases when they contain long lines.By the way, in this problem, a sentence always ends with one of “.” “?” “!”.  A sentence without these symbols is not allowed.
•  11 years ago, # ^ | ← Rev. 3 →   +1 Ok, I got accepted now. The solution was right from the beginning, my mistake, I do not put a comment on a break instruction that i use to test some cases, before send to the system.A long time lost, searching for an error in the solution, which did not exist
 11 years ago, # | ← Rev. 2 →   +5 Thanks for nice match!I thought that the trap of A is NICE , and hack system of Codeforces is becoming the better event!However, I thought that we couldn't understand the boundary condition about size of one message from samples of B.So I have a simple question to @Problemsetters.Why did you set such number as sample ?
•  11 years ago, # ^ |   0 The reason is probably to make hacking more interesting in the same way as Problem A.  The size of one message must be understood from the task description in the case of Problem B, not from examples.  I defer my own judgment whether that was a good decision or not, but the intent is clear.
 11 years ago, # |   +3 how to arrive at the formula for question 1 ?and what was the logic behind 4rth question ?
•  11 years ago, # ^ |   0 If you look at first three answers - they are 1, 3, 9. It hints the pattern - 30, 31, 32.
•  11 years ago, # ^ |   +3 Another way to interpret the formula:Given a block Bk, k ≥ 1 with size 2k × 2k, Bk + 1 is built based on four blocks, each of size 2k × 2k. To get the answer you cannot avoid placing something like Bk at the lower left 2k × 2k block. But for Bk + 1 the upper triangle must be filled, so you can see that the upper right 2k × 2k block must have no space left. What about upper left and lower right ones? Well, you can actually see that their upper triangles are also filled, giving you exactly the same initial setting for Bk, so you must have number of spaces for each block exactly the same as that in Bk. So if Bk has Ck spaces, then Bk + 1 has Ck + 1 = 3Ck spaces for k > 1. That gives you the 3k - 1 formula for k > 0. Be careful in handling the case k = 0.
 11 years ago, # |   +11 can i get editorials(in english) for the problems somewhere ?
•  11 years ago, # ^ |   +3 Yeah just click on analysis and then the brittish flag up right. Only yet A-C though
•  11 years ago, # ^ |   +3 thanks,
 11 years ago, # |   0 Can anyone highlight why this is always true "Notice, that any point from the triangle based on first three points will be into the convex hull in the future".Thanks.
 11 years ago, # |   +2 that was good contest
 11 years ago, # |   0 i'll be waiting for next one. :)