Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Страница 2 | WA3 | shamim | 1303. Минимальное покрытие | 26 сен 2022 20:45 | 1 | WA3 shamim 26 сен 2022 20:45 Could anybody help me? I have WA at 3th test .I tried many test and answers were correct .I also tried this test and answer was correct: 5 -5 0 0 1 1 2 2 3 4 5 3 4 10 49000 0 0 | WA#16 | Alexandr | 1303. Минимальное покрытие | 29 мар 2022 23:37 | 1 | WA#16 Alexandr 29 мар 2022 23:37 Hey, this is the test 16 - it was a long path to get there. What can possibly go wrong? | WA 13 | hotguy6pack | 1303. Минимальное покрытие | 25 мар 2022 08:19 | 3 | WA 13 hotguy6pack 24 мар 2022 01:41 i have tried all cases and it seems correct but cant pass test 13. Can someone help me what is test 13??? Английский я знаю плохо, поэтому sorry:) У меня тоже был WA 12. Попробуй тест: 1 49999 50000 0 0 TY so much <3 :(( Английский я знаю плохо, поэтому sorry:) У меня тоже был WA 12. Попробуй тест: 1 49999 50000 0 0 Edited by author 25.03.2022 08:26 | greedy works! | khdz | 1303. Минимальное покрытие | 14 янв 2022 10:28 | 2 | I have solved this problem by using an easy greedy algorithm. MAIN: you need to use an idea of 2 pointers(of course you need to sort array) and take the rightest segment. Left part of segment need to be <= x(another pointer) The solution below: void solve() { int m; cin >> m; vector< pair<int, int> > pi; int a, b; cin >> a >> b; while (a || b) { pi.pb({a, b}); cin >> a >> b; } sort(all(pi)); int cnt = 0, j = 0; vector< pair<int, int> > ans; j = 0; int x = 0; for (; j < sz(pi) && x < m; j++) { int k = j; int mx = x; pair<int, int> par = {-INF, -INF}; while (k < sz(pi) && pi[k].ff <= x) { if (mx < pi[k].ss) { mx = pi[k].ss; par = pi[k]; } k++; } if (par.ff == -INF) { cout << "No solution\n"; return; } x = mx; ans.pb(par); if (k > j) j = k - 1; } if (x < m) { cout << "No solution\n"; return; } cout << sz(ans) << '\n'; for (auto &i : ans) { cout << i.ff << ' ' << i.ss << '\n'; } } always choose segments with rightest right points | dp - O(m^2) | >>> | 1303. Минимальное покрытие | 21 ноя 2021 19:10 | 1 | dp[i] - минимальное количество отрезков, если последний отрезок заканчивался в позиции i. ответ dp[m]. | If you are having trouble | urmat | 1303. Минимальное покрытие | 9 фев 2020 01:50 | 1 | There is full solution!!! Try thinking yourself or using hints before watching it and use visual c++ 2017 . . . . . . . . . . . . . . . . . . . //#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #define int long long #define pb push_back using namespace std; const int N = 50000; pair<int, int> dp[N], right_end[N]; vector<pair<int, int> > v; vector<int> ans; unsigned main() { for(int i = 0; i < N; i++) { right_end[i].first = -50001; right_end[i].second = -50001; } int m; cin >> m; int l, r; int k = 0; while(true) { cin >> l >> r; if(l > m || r < 0) continue; if(l == 0 && r == 0) break;
v.pb({l, r});
if(r > right_end[l].first) { right_end[l].first = r; right_end[l].second = k; } k++; }
int i = 0; for(auto it: v) { if(it.first <= 0 && it.second > 0) { if(it.second > dp[0].first) { dp[0].first = it.second; dp[0].second = i; } } i++; } for(int i = 1; i <= m; i++) { if(dp[i - 1].first >= right_end[i].first) { dp[i].first = dp[i - 1].first; dp[i].second = dp[i - 1].second; } else { dp[i].first = right_end[i].first; dp[i].second = right_end[i].second; } } for(int i = 0; i <= m; i++) { if(dp[i].first < i) { cout << "No solution" << endl; return 0; } } int pos = 0; while(pos < m) { ans.pb(dp[pos].second); if(dp[pos].first == pos) { cout << "No solution" << endl; return 0; } pos = dp[pos].first; } cout << ans.size() << endl; for(auto it: ans) { cout << v[(int)it].first << " " << v[(int)it].second << endl; } } Edited by author 09.02.2020 01:50 | solution hints | imaginary friend | 1303. Минимальное покрытие | 17 фев 2018 04:30 | 1 | 1) greedy works here, although it's not that much obvious how *correct* greedy should look like 2) 5th test case, that didn't pass for me: 12 -3 10 -2 8 -1 16 0 0 Edited by author 17.02.2018 04:30 | If you want a solution | Mahilewets | 1303. Минимальное покрытие | 1 июн 2017 11:37 | 1 | The problem is quite evil. The problem is actually very easy. It is hard to understand that the problem is that easy. Possible solution. First , eliminate all such segments I=[l;r], that l>M or r<0, because of such I's can't appear in the answer. Second, build your dp[]. Your dp[x] contains rightmost right end of all such segments [l;r], that l<=x. Finally, just start from segment whose right end is dp[0], jump to a segment whose right end is dp[dp[0]] and so on. How to build dp[x]? I have used an additional array right_end[y]. Where right_end[y] is the right end of a segment with maximal length from all segments whose left end is y. dp[x] =max(dp[x-1], right_end[x]). | All tests in forum didn't help me :( WA5 | Rocky.B | 1303. Минимальное покрытие | 14 мар 2017 15:26 | 2 | #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define ppb pop_back #define mp make_pair #define pii pair <int, int> #define pll pair <ll, ll> #define ld long double #define ll long long #define ull unsigned ll #define bit(x) __builtin_popcountll(x) #define all(x) x.begin(), x.end() #define sqr(x) ((x) * 1ll * (x)) #define sz(x) (int)x.size() #define purple ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define rep(_i, _from, _to) for (int _i = _from; _i <= _to; _i++) #define per(_i, _from, _to) for (int _i = _from; _i >= _to; _i--) #define nl '\n' #define ioi exit(0); #define _225day "" using namespace std; const int N = 1e6 + 7, mod = 1e9 + 9, inf = 1e9 + 7; const ll linf = (ll)1e18 + 7; const ld eps = 1e-15, pi = 3.141592; const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; int n, m, base = 50000; int s[N]; pii a[N]; struct Tree{ int ans, add; } t[N << 2]; inline bool cmp(pii x, pii y){ if (x.f != y.f) return x.f < y.f; } inline bool Check(int pref){ memset(s, 0, sizeof(s)); rep(i, 1, pref) s[a[i].f]++, s[a[i].s + 1]--; rep(i, 0, m + base){ s[i] += s[i - 1]; if (i > base && !s[i]) return 0; } return 1; } inline void Push(int v, int tl, int tr){ if (t[v].add && tl != tr){ t[v + v].add += t[v].add, t[v + v + 1].add += t[v].add; t[v + v].ans += t[v].add, t[v + v + 1].ans += t[v].add; t[v].add = 0; } } inline void Update(int l, int r, int add, int v = 1, int tl = 0, int tr = N){ Push(v, tl, tr); if (l <= tl && tr <= r){ t[v].ans += add; t[v].add += add; return; } if (tl > r || tr < l) return; int tm = tl + tr >> 1; Update(l, r, add, v + v, tl, tm); Update(l, r, add, v + v + 1, tm + 1, tr); t[v].ans = min(t[v + v].ans, t[v + v + 1].ans); } inline int Get(int l, int r, int v = 1, int tl = 0, int tr = N){ Push(v, tl, tr); if (l <= tl && tr <= r) return t[v].ans; if (tl > r || tr < l) return inf; int tm = tl + tr >> 1; return min(Get(l, r, v + v, tl, tm), Get(l, r, v + v + 1, tm + 1, tr)); } int main(){ #ifndef _225day freopen (_225day".in", "r", stdin); freopen (_225day".out", "w", stdout); #endif cin >> m; while (1){ int x, y; cin >> x >> y; if (x == 0 && y == 0) break; a[++n] = {x + base + 1, y + base}; } sort (a + 1, a + 1 + n, cmp); int l = 1, r = n, ans = -1, mid; while (l <= r){ mid = l + r >> 1; if (Check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } if (ans == -1) cout << "No solution", ioi ans = n; rep(i, 1, ans) Update(a[i].f, a[i].s, 1); vector <pii> res; rep(i, 1, ans){ Update(a[i].f, a[i].s, -1); if (!Get(base + 1, m + base)) Update(a[i].f, a[i].s, 1), res.pb({a[i].f, a[i].s}); } sort (all(res), cmp); cout << sz(res) << nl; for (auto i : res) cout << i.f - base - 1 << ' ' << i.s - base << nl; ioi } Same problem :( WA5, WA5, WA5... What causes that? | If you WA#14 | Accelarator | 1303. Минимальное покрытие | 30 ноя 2015 11:43 | 1 | When my sort compare function is: bool cmp(pair<int, int> p1, pair<int, int> p2) { if(p1.first != p2.first) return p1.first < p2.first; else return p1.second >= p2.second; } I get WA#14. And then delete the "=" like : bool cmp(pair<int, int> p1, pair<int, int> p2) { if(p1.first != p2.first) return p1.first < p2.first; else return p1.second > p2.second; } I get AC; | If you WA#4 | Accelarator | 1303. Минимальное покрытие | 30 ноя 2015 11:38 | 1 | Try this test: 5 0 3 3 5 5 7 0 0 AC answer is: 2 0 3 3 5 not: 3 0 3 3 5 5 7 | WA 10 | aslan7470 | 1303. Минимальное покрытие | 18 мар 2015 20:34 | 1 | WA 10 aslan7470 18 мар 2015 20:34 | To Admins | † SiriuS † [TWYT Union] | 1303. Минимальное покрытие | 16 май 2014 11:28 | 2 | To Admins † SiriuS † [TWYT Union] 15 май 2014 23:52 Исправьте слово "соледует" в последнем предложении Результата: "соледует вывести единственную фразу «No solution»". | I use greedy algorithm and get WA 1 | Ekaterina Chumbarova | 1303. Минимальное покрытие | 29 май 2017 02:50 | 2 | Hi! I use greedy algorithms and can't get past first test. Could someone please provide me with some tests? I tried these tests with following results: 1 -1 0 -5 -3 2 5 0 0 ----------- No solution 1 -1 0 0 1 0 0 ----------- 0 1 10 -5 1 1 14 -5 2 2 3 3 19 0 0 --------- -5 2 1 14 5 -5 0 0 1 1 2 2 3 4 5 3 4 10 49000 0 0 --------- 0 1 1 2 2 3 3 4 4 5 4 0 4 -5 0 3 4 -4 4 0 0 ------- -4 4 6 0 5 7 8 0 0 ------- No solution 10 0 9 0 0 ------- No solution you don't print segment's count first line | To admins : two possible answers | sylap | 1303. Минимальное покрытие | 21 июн 2013 00:56 | 1 | For Input : 10 -5 1 1 14 -5 2 2 3 3 19 0 0 Output1 : 2 -5 1 1 14 Output2 : 2 -5 2 1 14 Are both output1 and output2 considered as correct ? EDIT At least output2 is considered as CORRECT. (Finally solved :D) Edited by author 21.08.2013 18:18 | To admins: weak tests | Alexey Dergunov [Samara SAU] | 1303. Минимальное покрытие | 15 июн 2013 15:54 | 2 | Add this test: // test begin 42 0 0 // test end Edited by author 13.06.2013 15:45 Input format is updated. The following conditions were added: 1) L_i < R_i 2) Numbers in the pair are separated with exactly one space 3) The set contains at least one segment. All tests satisfy these conditions. But your test is considered to be incorrect now. | WA14 Access violation | Havard | 1303. Минимальное покрытие | 15 апр 2014 04:18 | 4 | #include <cstdio> #include <climits> #include <cstdlib> #include <algorithm> #include <list> #include <vector> using namespace std; #define PB push_back #define BEG begin() #define MP make_pair #define F first #define S second bool compare(const pair<int,int> &left, const pair<int,int> &right){ return left.F <= right.F; } int main(){ int M; int readInt1, readInt2; vector<pair<int,int> > segments; vector<int> solutionInd; scanf("%d", &M); while(scanf("%d %d", &readInt1, &readInt2) && !(readInt1 == 0 && readInt2 == 0)){ segments.PB(MP(readInt1, readInt2)); } sort(segments.begin(), segments.end(), compare); if(segments.empty() || segments[0].F > 0){ printf("No solution\n"); return 0; }
int currEnd = 0; int segInd = 0; int ansInd = -1; int maxEnd = 0;
while(segInd < segments.size()){ while(segInd < segments.size() && segments[segInd].F <= currEnd){ if(segments[segInd].S > maxEnd){ maxEnd = segments[segInd].S; ansInd = segInd; }
segInd++; } solutionInd.PB(ansInd); currEnd = maxEnd;
if(currEnd >= M || segments[segInd].F > currEnd) break; } if(solutionInd.empty() || currEnd < M){ printf("No solution\n"); } else{ printf("%d \n", solutionInd.size()); for(int i = 0; i<solutionInd.size(); i++){ printf("%d %d\n", segments[solutionInd[i]].F, segments[solutionInd[i]].S); } }
}
Keep getting runtime error(Access violation) even though I can't find anywhere it is possible to go outside the vectors memory space.
Update: The problem was accepted when using visual studio compiler instead of g++. Same thing happened to me. But why is that? Hi, I get WA6 with g++ but get runtime error access violation on test case 14 with Visual Studio 2010 C++. Code : /* * File: main.cpp * Author: Parnami * Created on April 14, 2014, 10:18 PM * Description : TIMUS Online Judge Problem ID : 1303 (DP) */ #include <stdio.h> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <string> #include <queue> #include <cmath> #include <utility> #include <limits.h> using namespace std; inline int fastRead() { int input; char c=0; while (c<33) c=getchar(); input=0; while (c>33) { input=input*10+c-'0'; c=getchar(); } return input; } vector < pair <int,int> > myVec,answer; bool inRange(pair <int,int> cur, int starter) { if(starter>=cur.first && starter<cur.second) return true; return false; } int main(int argc, char** argv) { int m,starter,ender,iter,i,flag; pair <int,int> maxxer,current; m = fastRead(); while(1) { cin>>starter>>ender; if(starter==0&&ender==0) break; if(ender<=0||(starter>=m&&ender>m)) { //Do Nothing } else { //cout<<"Pushing "<<starter<<"-"<<ender<<endl; myVec.push_back(make_pair(starter,ender)); } } if(!myVec.empty()) { sort(myVec.begin(),myVec.end()); iter = 0; starter=0; while(starter<m) { //cout<<starter<<endl; current = myVec[iter]; //cout<<"Yahaan Phuncha"<<endl; flag = 0; while(!inRange(current,starter) && iter!=myVec.size()) { //cout<<"Not in range : "<<current.first<<"-"<<current.second<<endl; iter++; current = myVec[iter]; } if(iter==myVec.size()) { //cout<<"End of vector nowhere to search"<<endl; flag = 1; break; } maxxer = current; iter++; if(iter==myVec.size()) {
} else { while(1) { if(myVec[iter].first>starter) { break; } else { if(myVec[iter].second>maxxer.second) { maxxer = myVec[iter]; } iter++; } } } //cout<<"Pushing into answer "<<maxxer.first<<"-"<<maxxer.second<<endl; answer.push_back(maxxer); starter = maxxer.second; } } else flag=1; if(flag) { cout<<"No solution"<<endl; } else { cout<<answer.size()<<endl; for(i=0;i<answer.size();i++) { cout<<answer[i].first<<" "<<answer[i].second<<endl; } } return 0; } Edited by author 15.04.2014 04:19 | How to save the path to solution if using DP. | hliu20 | 1303. Минимальное покрытие | 21 окт 2013 20:28 | 2 | If using DP, it seems that saving the path to minimum value exceeds the MEMORY threshold. How to solve it? How do you solve using DP? I used greedy algorithm and cuz of this I only saved only the optimal path (So, O(N) memory). | Страница 1 | If you have RA#5 | shtek_KH-13 | 1303. Минимальное покрытие | 13 мар 2013 09:54 | 1 | Numbers in the pair are separated with space(!S!). Its mean read-error if you didnt handle it in some langs such as c#. | why I can not get ac ,who can give me some powerful datas or help me check it | 578141611 | 1303. Минимальное покрытие | 10 авг 2012 22:26 | 1 | #include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<queue> using namespace std; #define N 900000 struct seq { int l; int r; }; seq se[N]; int m; bool cmp(const seq &s1,const seq &s2) { if(s1.l==s2.l) return s1.r>s2.r; return s1.l<s2.l; } int main() { //while(scanf("%d",&m)!=EOF) //{ scanf("%d",&m); int left,right; queue<int>que; while(!que.empty())que.pop(); int i=0,j; while(scanf("%d%d",&left,&right)) { if(left==0&&right==0)break; se[i].l=left; se[i].r=right; i++; } sort(se,se+i,cmp); int rightf=0; int maxlen=0; int num=0; int p=-1; int ff=0; for(j=0;j<i;j++) {
if(se[j].l<=rightf&&se[j].r-rightf>maxlen) { maxlen=se[j].r-rightf; p=j; } else if(p!=-1&&maxlen>0) { que.push(p); rightf=rightf+maxlen; maxlen=0; num++; j=j-1; } if(rightf>=m) { ff=1; break; } } if(maxlen>0) {
rightf=rightf+maxlen; maxlen=0; num++; if(rightf>=m) { que.push(p); ff=1; } } if(ff) { printf("%d\n",num); while(!que.empty()) { int top=que.front(); printf("%d %d\n",se[top].l,se[top].r); que.pop(); } } else printf("No solution\n"); //} return 0; } |
|
|