saliii's blog

1.Sums(POI: 10, solved: 210)

By saliii, 8 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
Problems like this:

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

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

Comments Comments (23)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it
hint1
hint2
hint3
code
Problems like this:
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Seems There is another approach coding it.

    code
    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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").

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Link to the problem

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This one is cool: http://main.edu.pl/en/archive/ontak/2010/ogr

→ Reply
  • »
    »
    8 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?

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

      spoiler in edits

      → Reply
      • »
        »
        »
        »
        8 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.

        → Reply
      • »
        »
        »
        »
        8 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.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can i find solutions of main problems?

→ Reply
  • »
    »
    8 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.

    → Reply
    • »
      »
      »
      8 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

      → Reply
»
7 years 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.

→ Reply
  • »
    »
    7 years 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

    → Reply
    • »
      »
      »
      7 years 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 ?

      → Reply
»
7 years 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.

→ Reply