saliii's blog

By saliii, 3 years ago, In English,

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.

Link

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

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

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
3 years ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it
hint1
hint2
hint3
code
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Seems There is another approach coding it.

    code
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Confusion 1: if A[0] 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[1]. But 1 can never be constructed using the numbers given {2,5,7}.

      Please help here.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        look this part of the code:

        if(dist[x%A[0]] <= x)
        	printf("TAK\n");
        else
        	printf("NIE\n");
        

        for x = 1 we have (dist[1] = 5) > (x = 1) so the answer is NO("NIE").

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +5 Vote: I do not like it

      spoiler in edits

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh! HEY, PLEASE DON'T SPOIL THE SOLUTION! thanks :) But the idea seems cool :) I'll think and I'll post about it.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Is there any other approach to solve this problem? As I don't find square root decomposition to be that intuitive.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ChamrAn (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ChamrAn (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can i find solutions of main problems?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      looksery cup book

      You mean looking for a challenge? How is that related to looksery cup? O_o

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
16 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 case

N=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.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      16 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 ?

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to submit solution? When I tried to submit it shows: We are moving to szkopul.edu.pl! MAIN will no longer be supported.