Show all threads Hide all threads Show all messages Hide all messages |
WA 4 | Tolchev Evgeny | 1203. Scientific Conference | 25 Nov 2022 03:00 | 1 |
WA 4 Tolchev Evgeny 25 Nov 2022 03:00 n = int(input()) m = [] SIZE = 30001 result = [0] * SIZE for i in range(n): m.append(list(map(int,input().split()))) m.sort(key = lambda x: x[1]) for i in range(n): start = m[i][0] end = m[i][1] fail = 0 for j in range(start): fail = max(fail,result[j]) result[end] = fail + 1 maxn = 0 for i in range(SIZE): maxn = max(maxn, result[i]) print(maxn) what`s wrong ? Edited by author 25.11.2022 03:04 Edited by author 25.11.2022 03:04 |
What is DP solution? Thx | Dmitriy | 1203. Scientific Conference | 30 Apr 2022 18:16 | 6 |
Hi. I wonder, how can I solve it with dp? I thinked a whole day and cant find the solution less than O(N*T). Give me please some hint. Just sort by endtime and use greedy. It's that easy. Why does it work? Can you prove that approach? I don't understand why it does work :(. O(N * T)? What is 'T'? This can be solved using greedy, but the O(N^2) DP solution is as follows: 1) Sort by start times dp[i]: maximum events that can be attended
iterate from j = 0 to i-1, if end time of j-th conference is less than start time of i-th and dp[j] + 1 > dp[i] then dp[i] = dp[j] + 1 answer is max of all elements of dp array You should save dp[max(end_time)]; remember that for each end time there maybe different start times so that (end - start) are different. Save these segments, mp[end].push_back(end-start + 1); now check from 1 to max(end_time) and for each i, if i is end time? then check this segments sizes, for each such segment dp[i] = 1 + dp[i - s]; where s is saved segment sizes for end time 'i'. https://pastebin.com/C3dagNL2 Edited by author 30.04.2022 18:18 |
Easy problem | Anton | 1203. Scientific Conference | 13 Jul 2021 18:37 | 1 |
Use scanline and sort events by right border abd after that just count segments that their l > now so after this make now = r, ans++; firstly ans = 0 and now = 0; Sorry for my English i'm from Russia |
greedy | guilty spark | 1203. Scientific Conference | 25 Aug 2020 06:16 | 2 |
greedy guilty spark 25 Aug 2020 00:06 Read tasks and deadlines from the programmer's handbook. similar greedy approach will work in this one. Also, why is this tagged dp? my dp soln is giving tle My DP solution works in ~0.001 seconds, please optimize your DP. |
Some test, which may help you | DixonD (Lviv NU) | 1203. Scientific Conference | 10 Jul 2019 16:22 | 2 |
5 1 9 14 15 1 11 12 13 10 15 Right answer is 3, but some algorithmes may give answer 2 for this test. P.S. I had this mistake:( P.P.S. Sorry, for my poor English... Thank you! This test helped me to fix WA6 Edited by author 10.07.2019 16:23 |
WA 12 | 4llower | 1203. Scientific Conference | 26 Oct 2018 13:05 | 1 |
WA 12 4llower 26 Oct 2018 13:05 if you use dp, l, r can be (>30000). |
What can it be on the 4-th test? | Soul Reaver | 1203. Scientific Conference | 9 Sep 2018 17:28 | 5 |
5 1 8 2 3 4 5 6 7 9 10 Answer: 4. I have answer 4 on this test! Why WA? Try this: 3 1 5 2 5 3 5 Answer: 1 Check when completion time is equal,then sort it in increasing order of arrival time |
See If you are getting WA 7 | Ashish Nimbalkar | 1203. Scientific Conference | 7 Aug 2018 14:30 | 1 |
If you are using DP, make sure you are using multimap instead of map ( In c++ )
|
Python 3. Code Improvement. | Dhruv Somani | 1203. Scientific Conference | 8 Dec 2017 11:11 | 3 |
I wrote the following code. It takes 0.748 s, 13 524 KB. Can you suggest something faster? [code deleted] Edited by author 01.05.2016 22:19 Edited by moderator 04.12.2019 21:38 Why does this solution work? Can anybody prove that? I dont understand why it work. Thanks! you can replace for x in range(confs): l.append(tuple(map(int, input().split()))) by for x in sys.stdin: l.append(tuple(map(int, x.strip().split()))) |
WA2 cto asipka | Feruz | 1203. Scientific Conference | 5 Apr 2017 17:49 | 1 |
#include<iostream> #include<cmath> #include<string> #include<vector> #include<algorithm> #include<bits/stdc++.h> #define ff first #define ss second #define maxn 10000009 #define pb(a) push_back(a) #define mk(a,b) make_pair(a,b) using namespace std; typedef long long ll; typedef float fl; typedef vector <int> vint; typedef vector <vint> vvint; typedef pair<int,int> pii; typedef vector<pii> pvint; typedef vector<bool> bvint; const int inf=1e9+7; int n; int e[30002], dp[30002]; int main(){ scanf("%d",&n);int ts,te; for(int i=1;i<=n;i++) scanf("%d %d",&ts, &te), e[te]=max(e[te], ts); for(int i=1;i<=30000;i++)if(e[i]==0) dp[i]=dp[i-1];else dp[i]=max(dp[i],dp[e[i]-1]+1); cout << dp[30000]; return 0; } Edited by author 05.04.2017 17:56 |
Tle test 13 with O(n) | Ghiorghiu Ioan-Viorel | 1203. Scientific Conference | 31 Mar 2017 10:19 | 4 |
Hi, I get tle on test thirteen, but i can't find out what I'm doing wrong. Thank you for helping me! #include <iostream> #include <algorithm> #define DM 100000 using namespace std; int n, k, m; pair <int, int> x[DM], a, b; bool cmp(pair<int,int> a, pair<int,int> b) { if (a.second > b.second) return 0; return 1; } int main() { cin >> n; for (; k < n; ++k) cin >> x[k].first >> x[k].second; sort (x, x + n, cmp); k = 1; m = x[0].second; for (int i = 1; i < n; ++i) { if (x[i].first > m) { m = x[i].second; ++k; } } cout << k; return 0; } GCC iostreams are slow by default. Try VS compiler for your code. Or put "std::ios::sync_with_stdio(false);" line in the very beginning of main() Comparator must return false if a == b. Comparator is wrong at all. Code after sort hopes data is sorted by end time in ascending order. So comparator should look like "a.second < b.second". |
I am getting a tle on my dp algo ontest case !11 | suryansh | 1203. Scientific Conference | 21 Jun 2016 10:28 | 1 |
#include "bits/stdc++.h" using namespace std; vector<pair<int,int> > v; int n; vector<int> v1; int dp[100001]; int recurse(int temp){
if(dp[temp] != -1) return dp[temp];
int search = v[temp].second; int lower = lower_bound(v1.begin(), v1.end(), search) - v1.begin(); // cout << search << " " << lower << "**"; int max1 = 0; for(int i = lower; i < v1.size(); i++){ // cout << v1[i] << "/" << search << "\n"; if(v1[i] - search >= 1){ max1 = max(max1, recurse(i)+1); } } return dp[temp] = max1; } int main(int argc, char const *argv[]) { // ios::sync_with_stdio(false); scanf("%d",&n); memset(dp, -1, sizeof dp); while(n--){ int st, en; scanf("%d%d",&st,&en); v.push_back(make_pair(st, en)); } sort(v.begin(), v.end()); for(int i = 0; i < v.size(); i++){ v1.push_back(v[i].first); // cout << v[i].first << " " << v[i].second << "\n"; } int max1 = 0; for(int i = 0; i < v.size(); i++) max1 = max(max1, recurse(i)+1); printf("%d",max1); return 0; } |
what is my problem on c++? (Wa2) | nick nikuradze | 1203. Scientific Conference | 12 May 2016 12:26 | 2 |
this is my code: #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { vector <int> A; vector <int> B; int a,b,n; cin>>n; for(int i=0; i<n; i++) { cin>>a>>b; A.push_back(a); B.push_back(b); } sort(A.begin(),A.end()); sort(B.begin(),B.end()); a=1; b=a; for(int i=1; i<n; i++) { if(A[i]!=A[i-1]) a++; if(B[i]!=B[i-1]) b++; } cout<<min(a,b); system("pause"); return 0; } Test --- 3 1 10 2 11 3 12 --- Your answer is 3, expected is 1 |
It is easy, just sort and one linear cycle | Sanatbek_Matlatipov | 1203. Scientific Conference | 1 May 2016 22:22 | 3 |
1. Sort it by endTime, if endTime equals another endTime then sort them by startTime. 2. Open one iteration from 2 to n, init just check that, is endTime<starTime, if so then ans++; 3. print ans; endTime and startTimes is one array with unchanged same index... Sorry for poor English
I don't think sorting by startTime is necessary. I think we should reverse-sort by startTime. |
this is a famous problem | dingalapadum | 1203. Scientific Conference | 20 Jan 2016 09:20 | 2 |
This is a famous problem known as "interval scheduling". |
TLE16 - Go 1.3 | Evgeny Sibil | 1203. Scientific Conference | 12 Nov 2015 18:58 | 2 |
My solution in Go (library sort + O(N)) got TLE on 16. Wrote in in C++ and got accepted. But I really surprised that someone (gadget, zalick, rozdestvenskiy) solved it in Python, which is slower then Go Finally got accepted in Go Used bufio instead of fmt. fmt is unbuffered and might be very slow |
Here is the sample of the test for the WA13 | esbybb | 1203. Scientific Conference | 20 Jun 2015 04:05 | 1 |
8 1 2 1 2 3 4 4 5 3 4 1 2 3 4 1 2 Answer 2 p.s. Greedy Algorithm leads to AC |
Test #7 why? | AlexRad | 1203. Scientific Conference | 6 Apr 2015 14:29 | 1 |
Why my programm does not pass test #7 ? Give me please that test! using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Globalization; using System.Threading; namespace _1203.Научная_конференция { class Program { static void Main(string[] args) { Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture; var n = int.Parse(Console.ReadLine().Trim()); var reports = new List<Tuple<int, int>>(n); for(var i = 0; i < n; i++) { var tokens = Console.ReadLine().Trim(). Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries); reports.Add(Tuple.Create(int.Parse(tokens[0]), int.Parse(tokens[1]))); } reports.Sort(); var weights = new int[n]; var weight = -1; var reportStartComparer = new ReportStartComparer(); for (var i = 0; i < n; i++) { if (weights[i] > weight) weight = weights[i]; var nextReport = Tuple.Create(reports[i].Item2 + 1, 0); var idx = reports.BinarySearch(nextReport, reportStartComparer); if (idx < 0) idx = ~idx; if (idx < n && weights[idx] < weight + 1) weights[idx] = weight + 1; } Console.WriteLine(weight + 1); } } class ReportStartComparer: IComparer<Tuple<int, int>> { public int Compare(Tuple<int, int> x, Tuple<int, int> y) { return x.Item1 - y.Item1; } } } |
Add test please | Fyodor Menshikov | 1203. Scientific Conference | 29 Mar 2015 00:19 | 4 |
I know AC solution that answers 0 to the following test: 1 29999 30000 New tests were added. Read Site news. thank you . you inspired me! |
Who has WA2 | Carbon | 1203. Scientific Conference | 18 Mar 2015 19:57 | 5 |
Try this: 5 2 3 4 5 6 7 2 8 9 10 The answer is 4. This is Test 2: 7 1 90 91 125 129 200 3 130 140 150 160 162 201 202 The answer is 5. try this: 4 1 5 6 7 2 3 4 5 resault is 3. Thanks for this examples :) Edited by author 18.03.2015 19:57 Edited by author 18.03.2015 19:57 |