Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

AN_out_of_date's blog

By AN_out_of_date, 21 month(s) 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  

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

    Seems There is another approach coding it.

    code
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    21 month(s) 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?

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      spoiler in edits

      • »
        »
        »
        »
        21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) 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.

»
21 month(s) 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).

»
21 month(s) 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).

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can i find solutions of main problems?

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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

»
14 months 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?

»
6 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.

  • »
    »
    6 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

    • »
      »
      »
      6 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 ?

»
6 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.