Hosen_ba's blog

[Gym] Tishreen Collegiate Programming Contest 2024
By Hosen_ba, 4 months 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, King_of_the_city, SUL, THE_THUNDERSTORM_BEGINS, better.call.grizo,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

»
4 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it +28 Vote: I do not like it

ah yes , new gym as a tester = more contributions

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

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

→ Reply
»
4 months ago, # |
  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
»
4 months ago, # |
  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
»
4 months ago, # |
  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
»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

as a non tester

all the authors are my uncles

→ Reply
»
4 months ago, # |
  Vote: I like it +27 Vote: I do not like it

as wtf ammar

The contest is uncly for sure

→ Reply
»
4 months ago, # |
  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
»
4 months ago, # |
  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
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    We were tricked that Latakia has a sea and a lot of water :(

    → Reply
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

will you post the solutions ?

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

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

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I did not get it.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            code

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                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
      • »
        »
        »
        »
        4 months ago, # ^ |
          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
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            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
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              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
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve C ? any hint?

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Find diameter of tree and then use grundy

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        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
      • »
        »
        »
        »
        4 months ago, # ^ |
        ← 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
      • »
        »
        »
        »
        4 months ago, # ^ |
          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
»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

as a tester , this was an amaizing contest

→ Reply
»
4 months ago, # |
  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
»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

As a problem setter, wtf ammar?!

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

Is there any editorial available?

→ Reply
»
4 months ago, # |
  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
»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

As a problem-setter <3

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

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

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

Is the XOR in Lazy Jaber a red herring?

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

Will there be an editorial? These problems are awesome but beyond my level I'd love to learn.

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

How to solve problem G?

→ Reply