KhaledFarhat's blog

[GYM] The 2023 Damascus University Collegiate Programming Contest
By KhaledFarhat, 16 months ago, In English

We would like to invite you to participate in The 2023 Damascus University Collegiate Programming Contest that was held on 25th June in Damascus, Syria.

The problems were authored and prepared by Kaitokid, Obada_Saleh, Guess.Who, Eliaster, HeMoo, Borgov, EleCursity, Wael_Mchantaf, Salahiano, Tareq_Ali, Helal_Salloum, Edrisov, ETheHedgehog, and me.

Thanks to our testers: A.D., AboAbdoMC, LastDance_NotLastOfMe, Zaher, Naseem17, Mahmoud_Haddad, Space-Time-, Arturo, Magician_Mathematician1, roctes7, Mohammad.Nour, HazemDalati, BallzCrasher, Richtofen, KactusJack, Harraaak, Malek_, Hadi_Alhamed, 57rek, and A.L.S.A.

Special thanks to EleCursity who helped us coordinating the contest.

We would love to hear your feedback about the contest. Hope you enjoy solving the problems!

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

Comments Comments (29)
| Write comment?
»
16 months ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

I am the author of problem G, and this comment is a motivation for you to read it to downvote me if you don't like it (or upvote if you like it?)

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Your first upvote!!

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Thank you for the interesting problem :)

    → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Excuse Me, where are problems? Would You send link? before thanks)

    Sorry
    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can I get a hints about how to calculate the Wael-uty of two unordered integers (X, Y) fast? Thank you for the interesting problem?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      hint_1
      hint_2
      hint_3
      → Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

Thanks for the efforts of all the coordinators of this contest.

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

Any idea on how to solve H???

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

Painful day it was

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

How to solve I?

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

    Let's Reverse the permutation we note that the first $$$j$$$ such that all elements between $$$[1;j]$$$ exists in this prefix form a connected component this is easy to prove and you can find it out from doing some trials as well.

    So you just need to count the number of such $$$j$$$. This can be translated to the following problem: Count the number of prefixes such that $$$\sum_{i=1}^{j} i-p_i == 0$$$, Note that this sum will always be non-negative which translate it to this

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

Problems are very interesting kudos guys.

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

    Thnx.

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

    Can you post your solutions on pastebin for all problems please? I am curios about some of them.

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

      Too much work tbh :" Try to ask here thou :"

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

        Any hints for problem L?

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          You need to think of the problems as at each step you add a maximum layer of nodes where no node is ancestor of the other, which means you need to add the first layer as answer to K=1 , the first 2 layers as answer for K=2 and so on. To build the layers you need to use small to big merge where you have for example layers from all childs and now you need to merge them for example layers of u are { 6,2,1} and layers of v are { 9,5} when you merge you will have {6+9 = 15, 2+5 = 7, 1} which means you merge the big from u with the big from v , after merging all childs, you add layer for the current node , here is my code if you want to take a look : link

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

nice problems. are editorials available?

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

any explanation on the first example of problem $$$M$$$ .

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    for the first test case the possible permutations are: all permutations

    for the second test case the possible permutations are: all permutations

    for the third test case the possible permutations are: [1,3,2],[2,3,1], [1,2,3]

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

      Can you give me some hints for problem M?

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        You can reformulate to think about the given indices in the set doesn't really matter if p[i]>p[i+1] or p[i]<p[i+1] , becaus if p[i]>p[i+1] then it is in the set otherwise it doesn't matter, so our problem is how many permutations such that if i isn't in the set than p[i]<p[i+1], I hope this helps!

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

          tks a lot!!! this really helps me

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

How to solve B?

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

    You build a union find data structure with time , where you save the update time for every node and the corrosponding id and answer for that time. you have for example for node 2 has been updated at times 3, 6 , 7 you will have the following update_time[2]={0,3,6,7}, id[2]={2,2,2,5}, now to get the id for u and time t , you search for the biggest update time for u <= t and see , if it's equal to u then it's the id of the component otherwise recursively search on it's id like a simple DSU. , for the merge operation you keep set for every component , and save current ans for every component, you merge the small one into the big one, lets consider big is the big set and small is the small set, now we iterate over the items of the small set , let's say u is the current value we want to insert, if u is already in big continue, if u+1 and u-1 are in big the we decrease the ans by 1 (we merged them together) , if u+1 and u-1 not in big we increase the answer by 1 (a new component) and then we insert u into big and we continue iterating. Here is my code : link

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

How to solve problem A?

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

    First you need to notice that every value should exist at most 2 times . If a value exist only 1 time it doesn't matter where it should be A or B, If a value exists 2 times then you there are 3 cases : if the 2 poisitions of that values are the same it means there is i such that a[i]=b[i]=value then it doesn't matter we swap those or not so we skip. if we have now 2 positions i,j such that ai=V, bi=x and aj=V,bj=y then we need one of them to be swapped and the other no , se we will construct a graph with nodes are indices and edge weight =1 between i and j in this case.

    if we have now 2 positions i,j such that ai=V, bi=x and aj=y ,bj=V then we need if one is swapped then the other one should be swapped too. then we add to the graph an edges between i and j with weight 0.

    So we will build a graph with edges with weights 1 or 0 and see if we can color the graph with 2 colors such that edge with weight 0 means both end should have same solor and edge with weight 1 means both ends should have different colors. => bipartite graph

    And for the answer just get the minimum size of color_0, color_1 for each connected compoenent and sum them .

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

Hi, overall, nice problemset but problem A is basically this: G. Columns Swaps.
The only difference is that in Problem A the values are up to 2*n instead of n.
The code of problem "G. Columns Swaps" in the editorial can be slightly modified to get A accepted.

→ Reply