Hosen_ba's blog

[Gym] Tishreen Collegiate Programming Contest 2024
By Hosen_ba, 21 month(s) 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 (47)
| Write comment?
»
21 month(s) ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

ah yes , new gym as a tester = more contributions

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

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

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

as a non tester

all the authors are my uncles

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

as wtf ammar

The contest is uncly for sure

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

will you post the solutions ?

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +9 Vote: I do not like it
    Hints
    → Reply
    • »
      »
      »
      21 month(s) 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
  • »
    »
    21 month(s) ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +3 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it
        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I did not get it.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            code

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
        • »
          »
          »
          »
          »
          21 month(s) 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
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
»
21 month(s) ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

How to solve C ? any hint?

→ Reply
  • »
    »
    21 month(s) ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Find diameter of tree and then use grundy

    → Reply
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
»
21 month(s) ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

as a tester , this was an amaizing contest

→ Reply
»
21 month(s) 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
»
21 month(s) ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

As a problem setter, wtf ammar?!

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is there any editorial available?

→ Reply
»
21 month(s) 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
»
21 month(s) ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

As a problem-setter <3

→ Reply
»
21 month(s) 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
»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve problem G?

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

any hint for K ??

→ Reply