Kaitokid's blog

[GYM] The 2024 Damascus University Collegiate Programming Contest
By Kaitokid, 9 days ago, In English

We would like to invite you to participate in The 2024 Damascus University Collegiate Programming Contest (DCPC 2024) that was held on [contest_time:528202] 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.

  • Vote: I like it
  • +213
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it +47 Vote: I do not like it

it was amazing! thank you for your work <3

→ Reply
»
9 days ago, # |
  Vote: I like it +50 Vote: I do not like it

As a participant, it was an uncly contest.

→ Reply
»
9 days ago, # |
  Vote: I like it +37 Vote: I do not like it

As a tester , Kaitokid is the GOAT

→ Reply
»
9 days ago, # |
  Vote: I like it +46 Vote: I do not like it

as a tester i had fun!

→ Reply
»
9 days ago, # |
  Vote: I like it +36 Vote: I do not like it

As a participant, It was an INCREDIBLE contest, so thanks for your hard work :)

→ Reply
»
8 days ago, # |
← Rev. 3   Vote: I like it +33 Vote: I do not like it

As a tester, I see this as one of the coolest contests I have ever practiced. Don't hesitate to participate and have fun!

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

    The problem set is Amazing. Is there any editorial of this set?

    → Reply
»
8 days ago, # |
  Vote: I like it +46 Vote: I do not like it

As a participant ,it was a great contest as YOU <3

→ Reply
»
8 days ago, # |
  Vote: I like it +33 Vote: I do not like it

As a tester, the problemset is my uncle.

→ Reply
»
8 days ago, # |
  Vote: I like it +24 Vote: I do not like it

As a tester,it's one of the best contests I have ever participated in. Thanks to all the authors

→ Reply
»
7 days ago, # |
  Vote: I like it +24 Vote: I do not like it

As a participant, I really enjoyed this contest. Thanks to everyone who contributed in this contest

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do B?

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

    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

    → Reply
    • »
      »
      »
      5 days ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Really thanks for the soln. I respect your efforts, but I already solved it (o_o). Still, thanks bro.

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

        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.

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

        You're more than welcome :) as for the solution, it may help someone to solve it so no problem.

        → Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

will you post the editorials?

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

How to solve G?

→ Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 4   Vote: I like it +28 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        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

        → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F and A?

→ Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

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

    To get the smallest range that exists between [L R`]
    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

    → Reply
»
4 days ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it
solution for K
→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

in problem B first test case is there a typo and r should be excluded ?? 

5
ababa
2
1 2
1 3

first query we can swap a&b and we get 8 instead of 4

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

    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]

    → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I solve C?

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    9 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    hint 1
    hint 2
    solution

    husseainshalaby6 you can read this if you stay want to solve c

    → Reply