Kaitokid's blog

[GYM] The 2024 Damascus University Collegiate Programming Contest
By Kaitokid, 5 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 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.

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

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

it was amazing! thank you for your work <3

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

As a participant, it was an uncly contest.

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

As a tester , Kaitokid is the GOAT

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

as a tester i had fun!

→ Reply
»
4 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
»
4 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
  • »
    »
    2 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
»
4 days ago, # |
  Vote: I like it +38 Vote: I do not like it

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

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

As a tester, the problemset is my uncle.

→ Reply
»
4 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
»
3 days ago, # |
  Vote: I like it +16 Vote: I do not like it

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

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

How to do B?

→ Reply
  • »
    »
    29 hours 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
    • »
      »
      »
      29 hours 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
      • »
        »
        »
        »
        29 hours 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
      • »
        »
        »
        »
        29 hours 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
»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

will you post the editorials?

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

How to solve G?

→ Reply
  • »
    »
    7 hours ago, # ^ |
    ← Rev. 4   Vote: I like it +17 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
    • »
      »
      »
      7 hours 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
      • »
        »
        »
        »
        6 hours 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
»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F and A?

→ Reply
  • »
    »
    4 hours ago, # ^ |
    ← Rev. 3   Vote: I like it 0 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