×

# MOSTDIST - Editorial

 4 Transformation is as follows. Hopefully when shown that way, all steps are clear enough... Just two possibilities for each absolute value ...tried both all possibilities... ...reordered and grouped... f1..f4 are defined in editorial above, we can skip fx(P) at the end, because it is the same for all points in S... answered 25 Nov '14, 03:00 16.8k●49●115●225 accept rate: 11% 1 @betlista thanks (25 Nov '14, 15:08)
 1 Codechef should try and fix their Time limits. My first solution printing answers using cout: http://www.codechef.com/viewplaintext/5453096 Second solution printing answers using printf: http://www.codechef.com/viewplaintext/5453133 First one TLE and second one passed :| answered 24 Nov '14, 01:19 570●3●3●8 accept rate: 11% Wow, with sync_with_stdio(0)... Noticed, thanks (24 Nov '14, 01:29) 2 I don't think it's about cout, but endl. When you use endl instead of "\n", it flushes the output, which is incredibly slow. (Also, sometimes the output is flushed when reading with cin, so you should put cin.tie(0) at the beginning of your code to avoid it in situations such as this one.) (24 Nov '14, 01:29) xellos07★ Not surprised since cout is usually more slower than printf. (24 Nov '14, 01:32) yea, maybe its because of endl..! cin, cout with sync_with_stdio(0) works faster than scanf printf. Endl seems to be the only issue here. (24 Nov '14, 12:10) Point noted. Though cin.tie(0) still doesn't solve the issue. Either way ,should try and avoid endl on codechef. One point which I would like to raise would be that online judges like codeforces never have such problems. In codechef, even if you get the complexities right, there is a possibility of getting a TLE. Why involve border line time limits in the first place? I guess reducing the time limit a bit wouldn't hurt or let higher complexity solutions pass. (25 Nov '14, 02:49) Yeah well, if you only use cin.tie(0) but don't replace endl by "\n", it will have no effect - that's why I listed the steps to take in order of priority. Just copy-paste the first 2 lines from my main() and don't use endl (except for debugging), and you'll be fine from the vast majority of cin-related problems. (25 Nov '14, 08:09) xellos07★ showing 5 of 6 show all
 1 Actually, max for F2 is min for F3. And max for F1 is min for F4... But my solution doesn't pass. Weird NZEC...Grmph answered 25 Nov '14, 03:38 6★beroul 111●3 accept rate: 6%
 0 The candidates for distant point are from the maximum of each of the functions. It will be true if we find the minimum too right? Just for a better understanding. Or can someone explain how it is the maximum? I assumed from the formula written for 2 points as f1(P1) - f1(P2) ... , we take P2 to be the point given and P1 the points on the set. EDIT: I used the minimum instead of maximum and it accepted. Hence i could just use a map and do deletions easily too. answered 24 Nov '14, 11:08 56●1●2 accept rate: 25%
 0 can you explain how you have made the transformation and its validity? I can't seem to understand it and it's bugging me a lot. answered 24 Nov '14, 12:01 787●9●15●28 accept rate: 6% @ashwini007k, another way of seeing all of this, which made the understanding easier for me, is that you can consider each fi function as maintaining the most distant point of a particular quadrant from the center. Although all of the points coordinates are positive, and then are in the same quadrant, the f1 function returns the point which is in the most upper-right side of the plane, whereas the f2 function returns the point which is in the most bottom-right side of the plane, and so on. From that you could assume that the most distant point from P is some point which is in one of the four corners of the plane. (26 Nov '14, 23:07)
 0 There are no accepted solution to this problem in python. I implemented the log(Q) per query approach, but it still gives TLE error. Can you check if the problems time constraints are too strict for python? answered 26 Nov '14, 12:31 2★gauravsc 1 accept rate: 0% It might be I/O problem, if there is one + 0 0 and 500,000 times ? 1000000000 1000000000 (109 both) how quick you got response on your local PC? (26 Nov '14, 21:07) I take each query using raw_input() command and give the input as you asked above. It takes 38.27s for the code to finish. I also try by reading the entire input in one attempt using sys.readlines(), but it takes even longer 86.6s. I now think that the bitwise xor operator is the only cause of delay in the output. Here is my code http://www.codechef.com/viewsolution/5458355 (28 Nov '14, 12:16) gauravsc2★ almost 40 seconds is too slow, I don't think it is because of xor, it's slow I/O I'm afraid... Other python guys, are there quicker I/O methods? One more thing you can try, what I'm doing in Java... Instead of print answer for each query, use string concatenation and print this huge string once at the end... (28 Nov '14, 12:32) Something interesting, I mask the output of each xor with 0xFFFFFFFF & (query ^ answer) and because of this the time reduces to 4.3s on my PC, but it still says TLE on codechef. (28 Nov '14, 13:26) gauravsc2★
 0 This problem definitely has too strict time constraints for python. I think the time constraint of 3*1.5=4.5s for python is a little off the mark. It is near impossible for me to bring the time below 5.5s. I think the time limit for python should be at least 6.5s. Please reset the time limit for python or else a lot of other people would end up being frustrated. answered 28 Nov '14, 18:44 2★gauravsc 1 accept rate: 0%
 0 Can someone provide a working link to Setter's/Tester's Solution? answered 16 Dec '16, 13:22 3★adityavk 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×13,419
×2,897
×451
×121
×51
×25

question asked: 24 Nov '14, 00:05

question was seen: 4,027 times

last updated: 16 Dec '16, 13:22