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
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