Hosen_ba's blog

[Gym] Tishreen Collegiate Programming Contest 2024
By Hosen_ba, 3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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

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

ah yes , new gym as a tester = more contributions

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

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

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

as a non tester

all the authors are my uncles

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

as wtf ammar

The contest is uncly for sure

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

will you post the solutions ?

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

          I did not get it.

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

            code

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

How to solve C ? any hint?

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

    Find diameter of tree and then use grundy

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

as a tester , this was an amaizing contest

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

As a problem setter, wtf ammar?!

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any editorial available?

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

As a problem-setter <3

→ Reply
»
2 weeks 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
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the XOR in Lazy Jaber a red herring?

→ Reply
»
2 weeks 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