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!
As a LordOfTheWrongs ... good job for this magnificent contest
ah yes , new gym as a tester = more contributions
agree
When will the contest start ??? How do I participate?
2024 Tishreen Collegiate Programming Contest tomorrow 10:00, you can find the contest in gym section, it's on top.
We want a lesson
enough! <3
Accepted
As a first time tester, I really enjoy writing "as a tester...".
Just kidding, the problems were really awesome.
cuz problem setters are uncles
As Tester i really enjoyed the contest.
thanks for the problem setters for the awesome problems :)
as tester , I Enjoy very much as testing this gym Finally , new ideas !!!!!!
as a non tester
all the authors are my uncles
as wtf ammar
The contest is uncly for sure
For me, I can feel it's another LIT gym.I can't wait to participate!!
As a sea problem setter, I hope you find the problems interesting <3
We were tricked that Latakia has a sea and a lot of water :(
will you post the solutions ?
Is G's answers just 2 or 4.
Anyway, how to solve J :(
J : For array B, if you include an index i for any range l to r, then g(l, r) can be atmost 20 distinct value.
Got it, you healed my broken heart :(((((((((. So stress because I don't know why a lot of people can solve J :(((((
let's note $$$p$$$ the prefix sum of $$$a_i^2$$$
$$$b_i , b_{i + 1} , ... , b_n$$$ can have at most $$$log(MAX)$$$ distinct values (since each time either the OR remains the same or gets increased by $$$2^j$$$)
so for each $$$i$$$ from $$$1$$$ to $$$n$$$ divide the sequence $$$b_i , b_{i + 1} , ... , b_n$$$ into blocks of the form $$$[l , r , x]$$$ meaning for each $$$j \in [l,r] \ b_i | b_{i + 1} | ... | b_j = x $$$
Than for each block you have to count # $$$j \in [l ,r]$$$ having $$$p_j - p_{i-1} \lt x^2$$$ which can be done with binary search.
to find the blocks :
you need for each bit $$$b$$$ and each $$$i$$$ find $$$f[b][i]$$$ the first $$$j \gt i$$$ such that $$$b$$$ is on in $$$b_i | b_{i + 1} | ... | b_j$$$ which can be done with a frequency array on each bit and binary search again.
now given some $$$i , j$$$ let $$$x = b_i | b_{i+1} | ... | b_j$$$ , the first $$$k \gt j$$$ where $$$x \neq b_i | b_{i+1} | ... | b_k $$$ is :
$$$ \ k = $$$ the minimum over $$$f[b][i]$$$ for all bits $$$b$$$ that are off in $$$x$$$
$$$O(n \cdot log^2(MAX))$$$
code
How to solve C ?
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
How to solve H . Divide And Multiply ..i try to solve this using freq array but got WA on 2
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
how to calculate divisors and multiples for every a[i]?
start with $$$i = 1$$$ till $$$n$$$ and update the answer for each multiple of $$$i$$$
I did not get it.
code
I am doing same here but Time limit exceeded.
Dont know why.
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
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?
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
How to solve C ? any hint?
Find diameter of tree and then use grundy
Sorry, I still don't understand how to use the greedy to solve this. Could you please explain it to me?
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.
Not greedy, it's grundy in game theory. You can search it on Google :D
as a tester , this was an amaizing contest
How to prove F? my solution is just
As a problem setter, wtf ammar?!
Is there any editorial available?
Testcases for H seem not strong enough. Were $$$\mathcal{O}(n \sqrt{n})$$$ solutions intended to pass?
Our team's solution tested every possible pivot $$$i$$$ in range $$$[1, n]$$$, and for each, counting the number of divisors and multipliers of $$$i$$$ existing in the array.
As a problem-setter <3
for D is the intended solution O(n)? can O(nlogn) pass ?
How to solve problem G?