[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4756: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4758: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4759: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4760: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
Dev Skill Forum • View topic - Coding Contest-15 Editorial

Coding Contest-15 Editorial

All contest related discussion goes here. Both Dev Skill and Non Dev Skill contest related discussion is allowed. (But please keep the forum clean)

Coding Contest-15 Editorial

by BishalG » Fri Apr 28, 2017 8:34 pm

User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest-15 Editorial

by seyedssz » Sat Apr 29, 2017 4:38 pm

Problem E:
The problem distribution "DCP-315" says that :
total summation of favorite chocolate count will be at most 200000.
But This value at Editorial is 20000.
Which one is wrong?
 
Posts: 17
Joined: Sun Jan 01, 2017 12:28 pm

Re: Coding Contest-15 Editorial

by seyedssz » Sat Apr 29, 2017 5:03 pm

Problem E:
What do you do in each binary search?
Assume that you set the day=mid and you want to check it.
Do you get the sum of number of chocolates in each of favorite boxes of person Xi on day-mid?
 
Posts: 17
Joined: Sun Jan 01, 2017 12:28 pm

Re: Coding Contest-15 Editorial

by BishalG » Sun Apr 30, 2017 12:57 am

@seyedssz, the actual value is 200000. There was typing mistake in editorial. Thanks for correction.
And , of course after fixing mid in binary search, you have to calculate the total summation of chocolates in each of favorite boxes of person Xi on day-mid.
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest-15 Editorial

by seyedssz » Sun Apr 30, 2017 11:19 am

So The time can be :
O( 15 * max_Ti * log(D) * log(N) ).
log(N) for segment, log(D) for BS , 15*max_Ti is the number of elements you should check for a person Xi
that can't get AC as max_Ti can be about 10^5 and so your binary search trick can't change the time complexity and optimize it just a little.
So if you want a single element of your array from segment, it doesn't need lazy propagation.
 
Posts: 17
Joined: Sun Jan 01, 2017 12:28 pm

Re: Coding Contest-15 Editorial

by BishalG » Sun Apr 30, 2017 6:55 pm

@seyedssz, Thank you for curiosity regarding complexity. Notice that N,M,D are limited to 50000 and on every BS of 15*max_t, range is reduce by some constant factor so after all (15*max_t*logD) will be ( max_t*logD*constant ) . Also, there are lots of optimization that can be performed to pass within limits as time limit was too tight.
For your convenience, we increased time limit to 4 sec. Hoping to see you in leader-board of ranking :)
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Re: Coding Contest-15 Editorial

by seyedssz » Tue May 02, 2017 10:44 am

So,a nice problem thanks to setter. :)
It can solved with a BIT and Parallel binary search too.
 
Posts: 17
Joined: Sun Jan 01, 2017 12:28 pm

Re: Coding Contest-15 Editorial

by BishalG » Wed May 03, 2017 11:11 am

@seyedssz , Nice to see you in leader-board of the problem-E.Also, Nice to know you solved the problem with different logic. :)
User avatar
 
Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm


Who is online
Users browsing this forum: No registered users and 1 guest
cron