### saliii's blog

By saliii, 3 years 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!!! Tutorial of Upsolving poi, pois, Comments (24)
 » 3 years ago, # | ← Rev. 3 →   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:
•  » » 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,dist; 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; ++i) { dist[i] = INF; } dist = 0; dijk.insert(make_pair(dist,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; 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] <= x) printf("TAK\n"); else printf("NIE\n"); } return 0; } 
•  » » » Confusion 1: if A is equal to 2, then v2 can only get values 0 or 1.Confusion 2: Suppose A={2,5,7}then in first iteration, v=0, d=0. After that we iterate from i=1 to N-1, so in this case v2=(0+5)%2=1 and then we are assigning d2=0+5=5 to d. But 1 can never be constructed using the numbers given {2,5,7}.Please help here.
•  » » » » look this part of the code: if(dist[x%A] <= x) printf("TAK\n"); else printf("NIE\n"); for x = 1 we have (dist = 5) > (x = 1) so the answer is NO("NIE").
 »
 » This one is cool: http://main.edu.pl/en/archive/ontak/2010/ogr
•  » » 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?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   spoiler in edits
•  » » » » Oh! HEY, PLEASE DON'T SPOIL THE SOLUTION! thanks :) But the idea seems cool :) I'll think and I'll post about it.
•  » » » » Is there any other approach to solve this problem? As I don't find square root decomposition to be that intuitive.
•  » » » » » Not that I know of
 » Auto comment: topic has been updated by ChamrAn (previous revision, new revision, compare).
 » Auto comment: topic has been updated by ChamrAn (previous revision, new revision, compare).
 » Where can i find solutions of main problems?
•  » » 3 years ago, # ^ | ← Rev. 2 →   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.
•  » » » looksery cup book You mean looking for a challenge? How is that related to looksery cup? O_o
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   Oh, thanks :), I made a big mistake!
 » 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?
 » 20 months ago, # | ← Rev. 2 →   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.
•  » » 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
•  » » » 20 months ago, # ^ | ← Rev. 2 →   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 ?
 » How to submit solution? When I tried to submit it shows: We are moving to szkopul.edu.pl! MAIN will no longer be supported.
•  » »