Блог пользователя saliii

Автор saliii, 8 лет назад, По-английски

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!!!

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится
hint1
hint2
hint3
code
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Seems There is another approach coding it.

    code
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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").

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 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?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Where can i find solutions of main problems?

  • »
    »
    8 лет назад, # ^ |
    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.

»
6 лет назад, # |
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 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 лет назад, # ^ |
      Проголосовать: нравится +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

    • »
      »
      »
      6 лет назад, # ^ |
      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 ?

»
6 лет назад, # |
  Проголосовать: нравится 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.