We would like to invite you to participate in The 2024 Damascus University Collegiate Programming Contest (DCPC 2024) that was held on Jun/23/2024 12:00 (Moscow time) in Damascus, Syria.
The problems were authored and prepared by BERNARD , Guess.Who , Richtofen , KactusJack , roctes7 , BallzCrasher , Harraaak , Modar_Ali , Wael_Mchantaf , Obada_Saleh , ETheHedgehog , ZoTH and me.
Thanks to the testers : RaiseFromDeath , Drakkon , Gamal74 , antonis.white , Mr.Pie , yahia , Rania , FzArK , CaMOUFlage , stefdasca , purp4ever , The_Hallak, Al27700 , ApraCadabra , Majedh , A.D. , Arturo , HeMoo , Helal_Salloum , KingOfHababeesh , AboAbdoMC , HazemDalati , Magician_Mathematician1 , Farsh_LE , King_of_the_city , SUL , THE_THUNDERSTORM_BEGINS , Abo_alzeek , zain_salloum , AlI_sAiRo , megaminion , Your_Hands_Clean , Cp_Commado , AMR_23 , Nawar-Georges and MR.Michea1st .
Any feedback will be appreciated in the comments.
Hope you have fun participating in this contest.
it was amazing! thank you for your work <3
As a participant, it was an uncly contest.
As a tester , Kaitokid is the GOAT
Sorry, I think EyadBT is the GOAT for this season
Hello. Unfortunately, I don't think one can be the GOAT for a single season, as that contradicts the definition of the acronym.
as a tester i had fun!
As a participant, It was an INCREDIBLE contest, so thanks for your hard work :)
As a tester, I see this as one of the coolest contests I have ever practiced. Don't hesitate to participate and have fun!
The problem set is Amazing. Is there any editorial of this set?
As a participant ,it was a great contest as YOU <3
As a tester, the problemset is my uncle.
As a tester,it's one of the best contests I have ever participated in. Thanks to all the authors
As a participant, I really enjoyed this contest. Thanks to everyone who contributed in this contest
How to do B?
In the given segment from L to R, we can increase the value of F(a[l] .. a[r]) if there is character C1 has fewer occurrences than C2, and there is at least one occurrence of C2 before C1 in the given range.
for example, adac, L=1 and R=4 (one index)
cnt[c] = 1 and cnt[a] = 2
Because c appears after a, we can swap them.
my solution was just to find for each query, the number of occurrences of each character in the given range, this can be done using upper and lower by storing for each character the positions it appears in, and find the first and last occurrence for each character
then just brute force, try to compare all the characters, if cnt[i] > cnt[j] and the first occurrence of i is before the last one of j, then you can increase the answer
here i and j represent two different characters in the segment L→R
Really thanks for the soln. I respect your efforts, but I already solved it (o_o). Still, thanks bro.
You're more than welcome :) as for the solution, it may help someone to solve it so no problem, because usually they don't post an editorial.
You're more than welcome :) as for the solution, it may help someone to solve it so no problem.
will you post the editorials?
How to solve G?
I will try to find the largest possible character for each i .
So for each i I will apply several operations,
I will take all characters in the string with smallest possible range
For example, the number of distinct characters between i, n is x and the number of characters between i and r is also x and r is smallest possible.
1 — If the new character is smaller than the old character I can skip the change stage and move to the next place.
2 — If the new character is larger than the old character here the change is clearer (all letters in the range i r are converted).
Here are for each character from r+1 to n I can choose to change them or not if I changed all the characters before it ,then I can change the characters until I reach a character larger than the new character and here I can stop changing the characters .
3 — If the new character is equal to the new character then here I will look at the first j that is s[i]!=s[j] and j > i and return to the first two cases.
finally , if i change characters from i to r , then new i is r + 1 in order not to change the same index twice
Is your solution about taking the whole range from i to n, except for some suffix like from i to n-1 or n-2, and finding the largest possible value?
yes If the range contains all characters *except for some suffix like from n-1 or n-2 to n
all characters in the suffix u won't take exist in the range from i to r so that the answer stay valid
Yeah I got the same solution but it was too late, thanks for responding <3
you are welcome :)
How to solve F and A?
To solve the problem F
For every number of c characters, store for every index L the size of smallest range that contains a distinct c characters and begins in L
in each query you have [L R] so that you want to print shortest range in it, But will the range that you will search remain between [L R]?
No, because for example, if you search between [L R] for a range that contains 3 characters and the shortest range in the index R — 2 is equal to 4, then the index R — 2 is incorrect because it exceeds R
So you will try to find a new right that the shortest range in new Right not exceeds R and only then find the smallest range that exists between [L R`]
you can make sparse table or segment tree for each c characters on array that contains the shortest range for c characters in each L.
in each query get c in range [L R] and then just get min in Range L to new Right with c characters
How to solve E?
Since the maximum element in the array can be up to 1e9 Therefore maximum number of factors of the element can be up to 30 So the GCD will change maximum of 30 times throughout the array you can calculate it whenever it changes, and keep the answe whenever it is same
kd tree
edit the tree to search for maximum distance instead of minimum distance by checking the maximum of the squared distances from the current point to the four points that form the rectangle that represents a node in a tree
see Operations on k-d trees in the previous article
Guys, I need some advice. Please read my comment.
Today, I did L after almost 6 hours of brainstorming.
In the first half-hour, I fixed the median and calculated three variables: median_count, bigger_than_median_count, and smaller_than_median_count.
I got stuck with these three variables for almost 5 hours, trying to figure out how to check if these numbers met the required condition. My first algorithm didn't work as I was focusing on both arrays.
Then, I changed my approach to focus on one array and moved what I didn't want to the other one.
My question now is: what should I do to solve similar problems faster next time? Also, what is the perfect solution? I think with the three variables mentioned above, the condition might be checked in one line, but it took me 15 lines to check.
in problem B first test case is there a typo and r should be excluded ??
first query we can swap a&b and we get 8 instead of 4
no because there is 1 charecter a and 1 charecter b so that no difference if you put a first or b
I think you calc in each query the number of occurrences of the charecter in the whole string not for s[l...r]
How do I solve C?
How to solve C?
If there is a node that has more than three edges, is there a solution?
If there is set of nodes that has three edges, When is there a solution and when is there not?
if there is at least one node has more than three edges then the answer NO.
now i have set of nodes that has three edges (it may be empty) , the answer YES if all nodes in the set can be in one simple path proof : because each node can repeat at most two times ,for a node with three edge i will call it S. first appear of S when i enter S form first edge and second appear when you scan all nodes in second edge and back to S then the third edge will be the exit edge and you can't back to S.
you can try to solve this problem 1702G1 - Passable Paths (easy version) if you want to make sure if your check of set of nodes in one simple path is true or not.
husseainshalaby6 you can read this if you stay want to solve c
https://ideone.com/umWaZV
I think this is what I do but is not work
your check is not correct for second idea
try to implement new way
Any hints for problem E?
i need answer of M number please;
Thank you authors! beautiful contest
How to solve A?
i want code M please?