This problem is very similar to 10020.
If you get accepted on that problem, the same code can be used here with little modification.
Search found 34 matches: 10020
Searched query: 10020
- Thu Feb 23, 2017 10:57 am
- Forum: Volume 123 (12300-12399)
- Topic: 12321 - Gas Stations
- Replies: 3
- Views: 3082
- Mon Jun 30, 2014 11:47 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
I have followed this algorithm of the blog : Sort by the starting coordinate of each segment Set shouldBeCovered = 0, while(shouldBeCovered < M) get the max covering length (segment.end - shouldBeCovered + 1) segment that segment.start <= shouldBeCovered If segment found add to the segments that are...
- Thu Jun 19, 2014 1:16 am
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
brainfry - Thank you so much for all of your sample IO. You have helped me so much over the past month or so since I started these problems. I really appreciate it. Anyways, to the rest of the people who read this... the description does not say the input will be integers, BUT I used a greedy algori...
- Tue Oct 08, 2013 3:21 am
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
Thank !brianfry713 wrote:brianfry713 wrote:Greedily choose the next segment that covers the most additional points to the right of those already covered.
- Tue Oct 08, 2013 12:51 am
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
brianfry713 wrote:Greedily choose the next segment that covers the most additional points to the right of those already covered.
- Mon Oct 07, 2013 8:19 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
Can some body help my. I don't know about Greedy :-? . In 10020 problem, in the maximum test case - (Each test case in the input should contains an integer M(1<=M<=5000), followed by pairs "Li Ri"(|Li|, |Ri|<=50000, i<=100000), ) i = 100000, ...
- Mon Oct 07, 2013 8:11 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage.I got TLe with DP Dynamic progr
... bestmin) xp = i; } } if(len[xp] <= 100000) { a[1] = xp; dq_out(xp, 2, len[xp] - 1); } else printf("0\n"); } int main() { //freopen("10020.inp", "r", stdin); //freopen("10020.out", "w", stdout); scanf("%ld", &ntest); for(itest = 0; ...
- Thu Mar 07, 2013 1:45 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
AC. Thanks a lot brianfry713 
- Thu Mar 07, 2013 3:22 am
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
Input: 100 4092 -482 166 4461 7559 -277 1287 -465 7449 742 1638 2919 8657 3603 8123 -418 1739 872 4814 335 2494 1084 8493 1559 1891 4922 6669 887 4118 3031 4811 25 1735 724 4792 -391 -354 2848 8686 878 1862 5627 9421 5034 6580 3753 5108 353 7373 1497 4072 1157 2638 -382 -191 4324 5226 6304 6715 1176...
- Wed Mar 06, 2013 11:16 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
What's wrong with my code ? it solves all the test cases correctly.
Code: Select all
Removed after AC
- Thu Dec 13, 2012 1:16 am
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
... which case fails? The code Java is: import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; // uva code 10020 class Main { /** * @param args */ public static void main(String[] args){ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ...
- Mon Nov 26, 2012 9:43 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
omg. yay. "yay"*1000brianfry713 wrote:Greedily choose the next segment that covers the most additional points to the right of those already covered. You're choosing the maximum length segment instead, which as I pointed out in my test case, won't work.
thank you so much for your continued help
- Tue Nov 20, 2012 3:05 am
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
Greedily choose the next segment that covers the most additional points to the right of those already covered. You're choosing the maximum length segment instead, which as I pointed out in my test case, won't work.
- Sat Nov 17, 2012 8:31 pm
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
Yay brianfry713, I can always count on you :) It seems my approach to this problem is awkwardly wrong... I really need to start over and come up with a new way of thinking... but it's tough :\ because for now, instead of trying to do it correctly (which I'm not somehow) , I'm trying to patch in spec...
- Sat Nov 17, 2012 4:40 am
- Forum: Volume 100 (10000-10099)
- Topic: 10020 - Minimal coverage
- Replies: 57
- Views: 26765
Re: 10020 - Minimal Coverage
Input:Correct output:
Code: Select all
1
10
0 8
1 9
8 10
0 0Code: Select all
2
0 8
8 10