### AN_out_of_date's blog

By AN_out_of_date, 15 months ago, ,

I appreciate if anyone can help me share his good problems of POIs, just list them in the comments and I'll check them all.

We are given a set of positive integers A. Consider a set of non-negative integers B, such that a number x belongs to B if and only if x is a sum of some elements from A(the elements may be repeated).

Given A and an integer q. Then q integers Bi, determine whether it belongs to B or not. (YES=>"TAK", NO=>"NIE")

n ≤ 5000,  Ai ≤ 50000,  q ≤ 10000,  Bi ≤ 1000000000

Ai < Ai + 1

___________________
3
2 5 7
6
0 1 4 12 3 2
___________________
TAK
NIE
TAK
TAK
NIE
TAK
___________________

hint1
hint2
hint3
code

Seems There is another approach coding it.

code
Problems like this:

You can see next great problem here Maybe these problems helps someone!!!

•
• -3
•

 » 15 months ago, # | ← Rev. 3 →   +18 hint1Let's consider a0, minimum of them. hint2The point is when you can make x, you also can make x + a0. hint3So, try finding some of the minimum numbers you can construct in a way that you can construct all of the numbers from them. code// <................ be name khoda .................> #include using namespace std; int iin(){int x;scanf("%d",&x);return x;} int n, k; const int N = 10001; const int maxA = 100001; const int inf = 1e9 + 1; int ans[ maxA + 1]; int mn = 0; main() { fill( ans, ans + maxA + 1, inf); n = iin(); ans[ 0 ] = 0; mn = iin(); n--; while(n--){ int cc = iin(); int gcd = __gcd(mn, cc); int t = mn / gcd; for(int j = 0;j < gcd; j++){ int c = inf; for(int k = 0; k < t * 2; k++){ int I = ( j + ((cc%mn) * k )) % mn; if( ans[ I ] < c ) c = ans[ I ]; else ans[ I ] = c; c += cc; } } } k = iin(); while( k-- ){ int c = iin(); if( ans[ c % mn ] > c ) printf("NIE\n"); else printf("TAK\n"); } }  Problems like this:
•  » » 15 months ago, # ^ |   +10 Seems There is another approach coding it. codeActually, it uses dijkstra to implement what I said in hint 3. #include using namespace std; int INF = 2000000000,A[5005],dist[50005]; set < pair > dijk; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &A[i]); } for (int i = 0; i < A[0]; ++i) { dist[i] = INF; } dist[0] = 0; dijk.insert(make_pair(dist[0],0)); while(!dijk.empty()) { pair top = *dijk.begin(); dijk.erase(top); int v = top.second; int d = top.first; for (int i = 1; i < n; ++i) { int d2 = d+A[i]; int v2 = (v+A[i])%A[0]; if(d2 < dist[v2]) { if(dist[v2] < INF) dijk.erase(make_pair(dist[v2],v2)); dist[v2] = d2; dijk.insert(make_pair(dist[v2],v2)); } } } int k; scanf("%d", &k); while(k--) { int x; scanf("%d", &x); if(dist[x%A[0]] <= x) printf("TAK\n"); else printf("NIE\n"); } return 0; } 
 » 15 months ago, # |   0
•  » » 15 months ago, # ^ |   +5 Thanks. Added.
 » 15 months ago, # |   +5 This one is cool: http://main.edu.pl/en/archive/ontak/2010/ogr
•  » » 15 months ago, # ^ |   0 Yes, I thought about it and I remember I came up with a solution that uses checking some different situation and nothing else. Is there a cool solution?! Really?
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +5 spoiler in edits
•  » » » » 15 months ago, # ^ |   0 Oh! HEY, PLEASE DON'T SPOIL THE SOLUTION! thanks :) But the idea seems cool :) I'll think and I'll post about it.
•  » » » » 15 months ago, # ^ |   +5 Is there any other approach to solve this problem? As I don't find square root decomposition to be that intuitive.
•  » » » » » 15 months ago, # ^ |   +5 Not that I know of
 » 15 months ago, # |   0 Auto comment: topic has been updated by ChamrAn (previous revision, new revision, compare).
 » 15 months ago, # |   0 Auto comment: topic has been updated by ChamrAn (previous revision, new revision, compare).
 » 15 months ago, # |   +5 Where can i find solutions of main problems?
•  » » 15 months ago, # ^ | ← Rev. 2 →   +5 Some of them in looking for a challenge book.Every year, POI site publish polish solutions! you can use google translation to translate them and use.
•  » » » 15 months ago, # ^ |   0 looksery cup book You mean looking for a challenge? How is that related to looksery cup? O_o
•  » » » » 15 months ago, # ^ | ← Rev. 3 →   0 Oh, thanks :), I made a big mistake!
 » 8 months ago, # |   0 Can you explain the reason why you used gcd? I understood the solution with Dijkstra's algorithm. But your solution seems a bit non-trivial to me. Can you help me?
 » 10 days ago, # | ← Rev. 2 →   0 Just wondering !! Why the Dijkstra's approach is not giving a TLE for this question? As the complexity is O(N*Max(Ai)*log(maxAi) , and in the worst caseN=5000 MaxAi=50000 log(MaxAi)=15.6 Total number of operations = 3.9*(10^9) And the max time limit on a subtask is 0.4s.Please let me know If I'm missing on anything.
•  » » 10 days ago, # ^ |   +1 You can code it in O(N*max(Ai)), without a heap by finding the shortest current distance with brute force. Since the graph is dense, it's better to do it this way
•  » » » 9 days ago, # ^ | ← Rev. 2 →   0 Thanks for replying. Actually, I was asking why the code with the heap is not giving TLE? Isn't the expected number of operations of the order of 10^9 in the worst case scenario ?
 » 8 days ago, # |   0 How to submit solution? When I tried to submit it shows: We are moving to szkopul.edu.pl! MAIN will no longer be supported.
•  » » 8 days ago, # ^ |   0