ahmad_alghadban's blog

By ahmad_alghadban, history, 12 months ago, In English

We would be happy to invite you to participate in 2023 ICPC HIAST Collegiate Programming Contest that was held on 17th July in Damascus, Syria.

The problems are authored and prepared by Zaher ,SaeedSabbagh, OmarAlzakout, Yaman_Alwaza, Abdulrahman27, Khaled_Mardini, Ahmad7_7, Ismail_Alrifai, yaser.harba, and me.

Thanks to Kaitokid and HeMoo for testing the contest.

And Special thanks to EleCursity for helping us to coordinate the contest onsite and his efforts to ensure that everything ran well.

We would love to hear your feedback on the problems in the comments section. Hope you enjoy solving the problems!

UPD: it seems that there were something wrong with time limit of problem A, We've updated the time limit and all accepted solutions were rejudged, We do really apology for that wrong but too many non accepted solution have passed tests which made the problem too silly compared to the intended solution, We advise to try to solve the problem with the intended solution since it has a nice idea.

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

»
12 months ago, # |
  Vote: I like it +21 Vote: I do not like it

wlak 3aaash

»
12 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Waiting for this!

»
12 months ago, # |
  Vote: I like it +31 Vote: I do not like it

The problems are so interesting that I wish I can forget the problems and participate as a contestant :(

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

    can you give me the solution hints or solution of problem c

»
12 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Big up!!

»
12 months ago, # |
  Vote: I like it +30 Vote: I do not like it

As a problem-setter, I can assure you that the problems are interesting and I encourage you to try solving them all.

»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Great problems from great people <3

»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

As a problem setter, I assure you that there are many good problems. I highly encourage participants to share their valuable feedback. Happy problem-solving to all participants!

»
12 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Interesting problems with a lot of new ideas!
Waiting for the editorial :D

»
12 months ago, # |
  Vote: I like it +11 Vote: I do not like it

To be honest, amazing problemset. I solved some with too much excitement. Thanks for this :)

»
12 months ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

What a contest!!

»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

As a participant, I truly enjoyed solving the problems. I can assure you that you will find the problem set very interesting. Thanks all for your efforts.

»
12 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

i'm using sparse table for answering queries in o(1) in problem B but still getting TLE on test 25 , any hints ? :((

update: AC folks , thanks for the great problemset

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I have the same problem how did you solve it ?

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      i just added this line to my code and it passed

      line
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sadly it didn't work for me

        But it's a great line thanks :)

        my complexity is n*log(n)^2 is there something less?

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          O(Nlog(N)) is enough , i took a look at your code and i think you should process the priority queue after taking the elements first (ignoring the ones for sure)

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

            thanks for taking a look on my code really appreciate it .

            but I didn't get it what do you mean by process the priority queue after taking the elements first the last thing I do before answering the query is that I iterate over the pq

»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Thank you all for a great problemset.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest!

Can anyone explain the solution of B as I get MLE/TLE when implementing NLog^2(N)?

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    you can use priority_queue to get the max and divide it by its largest prime factor but it will still n.log^2(n). to get rid of priority_queue or set, i use a frequency array. first store for each number from 1 to 2e6 the largest prime factor using sieve in an array p. then lets store for each number from 1 to 2e6 the indices where it appears in the array using a vector. then iterate over this array of vectors from 2e6 to 1. if the current i is prime then sort the vector and set ans[v[j]]=t (where t is the time),otherwise move all elements of the vector to the vector i/p[i] (and increment the time while moving them). each element will be moved at most log(a[i]) times ,and the sort complexity overall is O(n.log(n)) since each element has exactly one final state in some prime index.so the total time complexity is O(n.log(n)). i hope this helps you :)

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

      Thanks Hosen, great approach .

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

time for B too tight: https://ideone.com/6J3igi this passes in 2,9 sec (tle at 3) how can I improve it?

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

    Your solution is N*log(N)*log(max a[i]). There is an N*(log(N) + log(max a[i])) solution which pretty much fits the time limit. I mean it wouldve been too easy jf the solution was that straight forward right?

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

      That s actually true I really forgot about the log in the priority queue.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The best solution i could think about at problem I was O(2^min(n0/lo,n1,l1) by inclusion exclusion which clearly did not pass. Can anyone here provide a hint/solution? thanks.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3

    I hope this helps you.

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

      Your hints really helped me, thank you. Such a good problem for practicing combinatorics.

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

I can't find the solution. May I ask where the solution is?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem K is interesting. Please anyone tell me how to solve K? thank you.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Notice that the strings are sorted. Therefore, we can perform a binary search on them. Now, we have only 26 characters, so in each query, we can iterate over all characters. Let's denote the target character as 'C'. First, we perform a binary search on the strings 'a' and 'b' to find the first joint occurrence of 'C', which we will call "first". Next, we find the last joint occurrence of 'C' in 'a' and 'b', denoted as "last".

    To calculate the answer, we add (last — first + 1) for each character and continue this process for all characters. Finally, we print the answer for each query.

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could anyone kindly assist me in identifying the correct state for the DP solution in problem A? I attempted to solve it recursively using a map with a pair of int and a vector of size 10. The int for id, The vector is meant to keep track of the number of digits used.

My transition function involves two choices: either not taking the number or taking the number, adding its value, and updating its digits to my vector. However, if any digit becomes greater than or equal to 3, I avoid the recursive call since it leads to invalid recursion.

Unfortunately, this solution is inefficient and results in a Time Limit Exceeded (TLE) error on test case 11.

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

    The time limit is too tight. greedily sorting the array in descending order before DP worked for me.

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

      Still giving me TLE :/

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

        sadge :( i also included the id to the vector instead of using pair to reduce map time. i think better approach is to use 2 bit musk.

      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        BTW you sorted the array in ascending not descending

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

          even after descending still TLE :D

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

      I want to know why I keep getting wrong answer on test 11.

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

        My transition function is the same as his, so what's the problem?

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

    You can simply solve it using an array with 11-D array !!

    First you have 1-D for id . Then you have 10 values — The Frequency of each digit of the numbers chosen so far.

    The Transition is the same as above — but I should mention that you have to check if frequency is still valid before choosing (Don't choose then avoid the recursive call). Because array size in this solution equals to 100*3^10 and can't be any larger (You can't store frequency if digit occurs 5 times or more).

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      you can simply use the same idea of bitmasks but in base-3 it is much faster and easier to code

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

first , thx for the Interesting problem set

can any one help me in J

my idea is to assume that x is to the left,right or equal to MED then

1)find MED

2)calculate $$$x = (n+1)*MED — sum(before \space adding \space x)$$$

3) minimize ans

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

    Notice that after sorting the array, you are left with only two options: either make 'a[n / 2 — 1]' the median or make 'a[n / 2]' the median.

    In the first choice, you need to add 'X' before 'a[n / 2 — 1]' so that it remains smaller than 'a[n / 2 — 1]'. In the second choice, you need to add 'X' after'a[n / 2]' so that it remains bigger than 'a[n / 2]'. Now, let's calculate if this scenario is feasible. Let the sum target be '(n + 1) * a[n / 2 — 1]', denoting it as 't1'. You already have the current sum, which we'll call 's'. Therefore, it's evident that 'X' must be equal to 't1 — s'.

    If '(t1 — s) <= a[n / 2 — 1]', then the answer can be printed.

    However, if '(t1 — s)' turns out to be greater than 'a[n / 2 — 1]', it indicates that the first choice is not viable. In this case, since an answer always exists, the second choice is the correct one: making 'a[n / 2]' the median. Now, calculate the new target sum as '(n + 1) * a[n / 2]', denoting it as 't2'. Then, print 't2 — s' as the answer.

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

      thx. I think my solution fails when I assume it's the median.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      Then, print 't2 — s' as the answer.

      What is the reason of this being correct?

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      in problem j i think there is a mistake in testcases : assume this test

      1
      1
      1
      

      there is two numbers can be added before 1 which are 0 and 1 , the statement said that print minimum answer if there are many of them so answer should be 0 not 1

»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

There's a clarification that's been sent during the contest for problem M and the statement is not updated. Please note this ahmad_alghadban as the clarification was important to solve the problem.

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

Any hints to problem L? thank you.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    The edges not used in the m paths, add nothing to your discount so have their weight equal to zero. An edge included in some of the m paths will add a discount equal to the number of paths its included in times its weight, so replace its weight with this value instead. The K vertices will form a subtree, and no matter how this subtree is going to look like, you can cover it with at most K leaves of the original tree. let's say we choose two vertices among the K vertices we need, the best possible for them is to have the maximum path weight (diameter of the tree). Now for the K — 2 vertices left, you try figure it out :)

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

      Could you elaborate on how to choose the k vertices? I still have no idea what to do after choosing the 2 endpoints of the diameter.

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

      I tried to code this solution but get WA, someone can help me?

      My solution: https://pastebin.com/dNfCK0L8

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? Can anyone give me the solution or some hints, please.

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

    First notice that the order of the elements is not important as you will sort it anyway, so you can define the subsequence using the frequency of every digit in it.

    From that, you can use dp[i][j], the sum of all cost of strings consisting of the first i digits and the length of the string is j.

    To update that dp you will need another array ways[i][j], which will hold the number of different strings.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ahmad_alghadban (previous revision, new revision, compare).

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

really wow lovely contest Thanks all for your efforts.

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

What a great problemset!! I REALLY ENJOYED IT !

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone give hints about problem C ? Thanks in advance

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

    The expected Value $$$e = \frac{\sum p_i}{n!}$$$

    Hint 1 : How can we simplify this expression ?
    Hint 2 : How many times can this pair appear over all permutations p ?
    Hint 3 : What is the final value of e ?
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody give the answer of A or K thanks!!!

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

    Hints for 104493K - Sam-Oh, the funny coach: As the given string are sorted so, we can just store the starting and ending position of each 26(a to z) character for every string. Now for each query just go through the stored index of each 26 character add the length of intersection of both string and finally print it (note: Try to store index in light structure otherwise there will be MLE or TLE)!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone provide some hints on problem N? I thought about storing dfs order in treap so queries of type (2) and (3) would be easy. But how do I know where to insert another node? I think I should either maintain sizes of all the subtrees or "the most right" node in a subtree.

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

    You can build a treap that when you insert, put u and -u before the position of -father[u], for example in the test case the treap is something like "1 2 -2 3 4 -4 -3 -1", and if 3 has a new child, the array will be "1 2 -2 3 4 -4 5 -5 -3 -1". I don't now if this really works because I got MLE in the test 15, because I don't know treap so much, but I thing that's ok.

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

      I actually realized that you can avoid inserting new nodes. Since the queries are offline you can build the final tree first and do operations in reversed order (remove new nodes instead of inserting). My implementation uses two treaps and it got AC.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me some hints or solutions for problem L ?

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

    Remember that three points define an unique circle, and you can find easily some material to find this circle. Try to use a bit of combinatorial to solve the rest of problem.

    Hint: Remember that a O(N^3) solution get accepted in this problem.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

where is the solution of these problems ? plz

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

in problem j i think there is a mistake in testcases : assume this test

1
1
1

there is two numbers can be added before 1 which are 0 and 1 , the statement said that print minimum answer if there are many of them so answer should be 0 not 1