Hello, Codeforces!
I am happy to invite you to participate in Al-Baath Collegiate Programming Contest 2023 that was held at the Al-Baath University 22.06.2023 11:00 (Московское время).
The problems were authored and prepared by Mahmoud_Haddad, Blade-Master, nooooob_KiFaH_HeLaL, Geo_Ghaffar, Basharo, molhaam1, somar_mh, Tinky-Winky, and me.
I would like to give our sincere thanks to:
Nihad_Nabelsi, aminsh for yellow testing.
MaherSefo, ApraCadabra for purple testing.
Abito, NeroZein, edogawa_something, Experto_Besherunom, FzArK, kaislash., Ayham_Dabah for blue testing.
Mohammad_soleman for cyan testing.
Rama_i_am, dina_saba, little-fermat for green testing.
And a special thanks to EleCursity, who helped us coordinate the contest onsite and made sure that everything ran smoothly.
We would love to hear your feedback on the problems in the comments section. We hope you have a blast participating in this contest and wish you the best of luck!
Happy coding!
As a tester, Geo_Ghaffar orz
Thank you, I appreciate it. Hope the best for you!
Without being a tester , Geo_Ghaffar orz
orz
It is a pleasure to work with you. Looking for positive feedbacks ^_^
As a tester, the problems were really interesting and I would definitely recommend them.
Oh and also, Geo_Ghaffar orz.
How to solve K???
Take a look at the other problems, some of them are easier. We will soon publish brief solutions or editorials.
.
Actually there is something missing or something that is misunderstood.
because after coloring the card with number 1 -in fact- all the other cards still be reachable.
the statement says: He can paint a black card (i) with red if and only if there is another black card (j) ......(not) there is another red card (j).
we know that for each card (j) there are always two cards ,let us call them (a) and (b), and there is a way to get from (a) -or (b)- to (j) passing through exactly two cards differ than (a) -or (b)- and (j).
It could be proven that coloring a card(j) "j!=1" that the two previous mentioned cards (a) and (b) are still uncolored will make it impossible to color n-1 cards at the end. ( the prove of this fact will be in the tutorial when published).
And the previous fact is what makes the code above works, and the reachable indices -in the solution section- should be called valid indices not reachable.
.
yes you're right, but the problem has been changed and I just wanted to clarify the tutorial of the actual problem.
.
I am glad that I have been part of the testing process.
And as a tester, I had a great time joining this gym ^_^
how to solve I ?
Take a look at the other problems, some of them are easier. We will soon publish brief solutions or editorials.
It is always difficult to deal with $$$gcd = 1$$$. Think about the same problem with $$$gcd(c_u,c_v)>1$$$.
To solve the original problem, just count the total number of paths contain the $$$i^{th}$$$ edge, and subtract the result from Hint1.
Still hard to deal with $$$gcd(c_u,c_v)>1$$$, try to solve it for $$$gcd(c_u,c_v)=x$$$ $$$(x > 1)$$$
You can solve Hint3 through Inclusion-Exclusion Principle or Mobius Function. With the help of some tree techniques like Centroid, Sack or Auxiliary Tree.
Full tutorial will be published soon.
Any hints for problem D ?
"Brute force all possible subarrays, considering the largest number as 1023. Therefore, the worst-case scenario would involve iterating through 1024*1024*10 (number of bits) https://pastebin.com/Q9DPh3RJ
Try to solve the problem in a brute force approach.
Instead of inserting an integer $$$x$$$ $$$(|x| = k)$$$ in any position $$$p$$$ $$$(1 \le p \le n)$$$ and finding the maximum xor. (which has a complexity $$$O(n^3 \times C(10,k)$$$ where $$$C(10,k)$$$ is the number of way to choose $$$k$$$ bits from $$$10$$$ bits.)
You can think of a better way, find the xor of a subarray $$$a[l;r]$$$ and try all possible values $$$x$$$, then take the maximum among them (which has a complexity $$$O(n^2 \times C(10,k)$$$)
Let $$$pref_0 = 0$$$ , $$$pref_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$$$ $$$(1 \le \ i \le n)$$$.
To calculate $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_r$$$ we can use the previous precalculated array. $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_r = pref_r \oplus pref_{l-1}$$$ .
We only interest about the distinct values among $$$pref_r \oplus pref_{l-1}$$$ where $$$(1 \le l \le r \le n)$$$
Let $$$pref_0 = 0$$$ , $$$pref_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$$$ $$$(1 \le \ i \le n)$$$.
Number of distinct values among $$$pref_r \oplus pref_{l-1}$$$ where $$$(1 \le l \le r \le n)$$$ is less than or equal $$$2^{10}$$$. (You can find these values with complexity $$$O(2^{2\times 10})$$$).
After finding these values, try all possible integers $$$x$$$ $$$(|x| = k)$$$.
Time complexity will be $$$O(2^{20})$$$ per each test.
Any hints for problem I plz ?
Read this previous comment.
how to solve F? i can't detect the error in my code nor the logic
let's consider for each string the minimum changes to make it palindrome as for example : the first test case = [1,2,2,2,1,1]
Try thinking of prefix sums furthermore sparse Table
It will be little bit hard to get the idea in this way but if you concern about prefix sums with the first array we made from the strings -- pre[0,1,3,5,7,8,9] (_return to hint1_) , we will only concern about sub-arrays [l:r] which has value which has value (pre[r]-pre[l]) <=k , then for each index we will find the index makes sub-array satisfying the above condition ,to make it clear let's consider subarray starting from index 2, it can take strings up to the 5th index (8-1<=7),and this can be easly get by binary search.
moving in to the second part we want to know the maximum value we can get ,in other words the index which I have to stop on it to get the maximum answer for this sub-array ,so we will also make prefix sum for the array of scores to get from it the maximum answer but how??!
let us also consider the first test case the the array will be scores[0,3,15,14,12,21,23] so the beginning from index 2 it will be optimal to stop at index 5 as it has the maximum value in the range , and this max range query can be done using sparse table ,so final answer will be (scores[max value index] — scores[i-1]).
solution by
algohary
ahmedtawfik
https://mirror.codeforces.com/gym/104447/submission/212087023
sorry for bothering you but if you have time can you look at my submission?
it does the same but using sliding window
it gives me wa 2
Any Hints to solve problem J?
Thanks for the amazing problem any idea how to solve problem E
Any hints for $$$J $$$ $$$?$$$
When & where editorial will be published?
I think there is a mistake in testcase 4 (and probably some other testcases after that too!) for problem H, the polygon given on that testcase is probably on counterclockwise order (which in problem description the polygon given should be on clockwise order), thanks to this I wasted 2 whole hours to find a counter testcase to my solution which is can only works on clockwise order. But there is none, since when I reverse the order of polygon when it was given on counterclockwise order then I got AC.
I want to know how to solve H. I use sweep line and segement tree to maintain the number of intervals that cover the points, but i can't solve those points at the endpoint of interval. I'm hopeful that someone can provide hint of this problem. Your response would be highly appreciated. Thank you.
I solved it after 62 tries. oh yeah
Please, Can you give the solution?