Hosen_ba's blog

[Gym] Tishreen Collegiate Programming Contest 2024
By Hosen_ba, 2 years ago, In English

We are happy to invite you to participate in 2024 Tishreen Collegiate Programming Contest that was held on the 25th of June in latakia, Syria.

The problems are authored and prepared by ahmad_alghadban, Ahmad7_7, Zaher, Go8, EyadBT, JaberSH1, Khaled_Mardini, SaeedSabbagh, Neodoomer, Yaman_Alwaza, OmarAlzakout, and me.

Thanks to The_Hallak, AmmarDab3an, Bisher_Sahloul, SUL, THE_THUNDERSTORM_BEGINS, Grizoo,skahl15, Khaled_Al_Awad, AhmadSelo, abd-alrzaq, and kareem_Bizreh for testing the contest.

We would love to hear your feedback on the problems in the comments section. Hope you enjoy solving the problems!

  • Vote: I like it
  • +71
  • Vote: I do not like it

Comments Comments (46)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

As a LordOfTheWrongs ... good job for this magnificent contest

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

ah yes , new gym as a tester = more contributions

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

When will the contest start ??? How do I participate?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

As a first time tester, I really enjoy writing "as a tester...".

Just kidding, the problems were really awesome.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

As Tester i really enjoyed the contest.

thanks for the problem setters for the awesome problems :)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

as tester , I Enjoy very much as testing this gym Finally , new ideas !!!!!!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

as a non tester

all the authors are my uncles

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

as wtf ammar

The contest is uncly for sure

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

For me, I can feel it's another LIT gym.I can't wait to participate!!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

As a sea problem setter, I hope you find the problems interesting <3

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

will you post the solutions ?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Is G's answers just 2 or 4.

Anyway, how to solve J :(

→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +9 Vote: I do not like it
    Hints
    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Got it, you healed my broken heart :(((((((((. So stress because I don't know why a lot of people can solve J :(((((

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

      For problem C

      you only care about the diameter

      you take the length of the diameter

      and here i did simple dp to know who would win

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

How to solve H . Divide And Multiply ..i try to solve this using freq array but got WA on 2

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    You can see that the value you want to get is a number in an array a

    Let's that value is d

    If you want to make all elements equal to d, you can see that: . If d = a[i], you don't need to use operation . If d is divisor of a[i], you need 1 transform to make a[i] equal to d . If d is multiplier of a[i], you need 1 transform to make a[i] equal to d . Otherwise, you need to make 2 transforms to make a[i] equal to d

    So the problem can convert to for any d, let's cntDiv[d] is number of elements in a with d is divisor, and cntMul[d] is number of elements in a with d is multiplier

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

      how to calculate divisors and multiples for every a[i]?

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it
        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I did not get it.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            code

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              I am doing same here but Time limit exceeded.

              import sys
input = sys.stdin.readline
from collections import Counter

MAX = 10 ** 6 + 1
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    c = Counter(arr)
    mini = n - c[1]
    # print(mini)
    temp_maxi = max(arr) + 50
    for num in arr:
        if num != 1:
            maxi = c[num]
            sumi = c[num]
            for x in range(num + num, temp_maxi, num):
                maxi = max(maxi, c[x])
                sumi += c[x]
            # print(sumi,num, maxi)
            mini = min(mini, sumi - maxi + c[1] + (n - sumi - c[1]) * 2)
    print(mini)
for t in range(int(input())):
    solve()

              Dont know why.

              → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Use method like Erathones sieve

        Fact: For all integers from 1 -> 1000000, the integer which has most divisors is just about 250 divisors

        So for all a[i], iterate all divisors d of a[i], then increase cntMul[d] and increase cntDiv[a[i]]. Because for each a[i], there would be d and for each d, there would be a[i] with a[i] is a multiplier of d

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Erathones Sieve method give us divisors in logn. Actually I am also using same approach in my solution but still getting time limit exceed. Can you get a look at my solution above?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            For each test case, you use erathones ?? So it would be time limit.

            I just use Erathones only 1 time before reading test case, to find out list of divisors for each number from 1 -> 1000000

            → Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

How to solve C ? any hint?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Find diameter of tree and then use grundy

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Sorry, I still don't understand how to use the greedy to solve this. Could you please explain it to me?

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

        In this game, we can identify winning and losing states based on the diameter of the tree.

        Winning State: If the diameter of the tree has 1 or 2 nodes, you can remove both, making 1 and 2 winning states. Now, let's consider a diameter of 3 nodes:

        Losing State: If there are 3 nodes in the diameter, you can remove one or two nodes on your move. However, by doing so, you always leave your opponent in a winning state, with no way to force them into a losing state. Thus, a diameter of 3 is a losing state.

        For diameters of 4 and 5:

        Winning State: With 4 nodes in the diameter, you can remove 1 node, leaving your opponent with a diameter of 3 nodes, which is a losing state. Similarly, with 5 nodes, you can remove 2 nodes, again reducing the diameter to 3, thus giving your opponent a losing state.

        For a diameter of 6:

        Losing State: You cannot force your opponent into a losing state because any move you make will leave them with a diameter of 4 or 5, both of which are winning states. Therefore, a diameter of 6 is also a losing state.

        From this analysis, we can conclude that if the diameter of the tree has 3*k nodes, it's a losing state. Otherwise, you can always win the game.

        → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Not greedy, it's grundy in game theory. You can search it on Google :D

        → Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

as a tester , this was an amaizing contest

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

How to prove F? my solution is just

$$$ 2 \times \left\lfloor \frac{n}{2} \right\rfloor \times \left( \left\lfloor \frac{n}{2} \right\rfloor + 1 \right) + \left( n \bmod 2 \times \left\lceil \frac{n}{2} \right\rceil \right) $$$
→ Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

As a problem setter, wtf ammar?!

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

Is there any editorial available?

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

Testcases for H seem not strong enough. Were $$$\mathcal{O}(n \sqrt{n})$$$ solutions intended to pass?

Solution spoiler
→ Reply
»
2 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

As a problem-setter <3

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

for D is the intended solution O(n)? can O(nlogn) pass ?

→ Reply
»
23 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve problem G?

→ Reply