Kaitokid's blog

[GYM] The 2024 Damascus University Collegiate Programming Contest
By Kaitokid, 3 months 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
  • +212
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +47 Vote: I do not like it

it was amazing! thank you for your work <3

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

As a participant, it was an uncly contest.

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

As a tester , Kaitokid is the GOAT

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

as a tester i had fun!

→ Reply
»
3 months 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
»
3 months 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
  • »
    »
    3 months 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
»
3 months ago, # |
  Vote: I like it +46 Vote: I do not like it

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

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

As a tester, the problemset is my uncle.

→ Reply
»
3 months 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 months 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
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do B?

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

will you post the editorials?

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

How to solve G?

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

How to solve F and A?

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

How to solve E?

→ Reply
  • »
    »
    3 months 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
»
3 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it
solution for K
→ Reply
»
3 months 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 months 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
  • »
    »
    3 months 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
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I solve C?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it
    hint 1
    hint 2
    solution

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

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

Any hints for problem E?

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

i need answer of M number please;

→ Reply
»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Thank you authors! beautiful contest

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

How to solve A?

→ Reply