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.

wlak 3aaash

Waiting for this!

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

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

Big up!!

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

as usual , coach yaman is the best

Agreed

Great problems from great people <3

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!

Interesting problems with a lot of new ideas!

Waiting for the editorial :D

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

What a contest!!

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.

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

I have the same problem how did you solve it ?

i just added this line to my code and it passed

line## pragma GCC optimize("Ofast")

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?

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)

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

Thank you all for a great problemset.

Great contest!

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

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 :)

Thanks Hosen, great approach .

time for B too tight: https://ideone.com/6J3igi this passes in 2,9 sec (tle at 3) how can I improve 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?

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

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.

Hint 1Think of each consecutive zeroes or ones as just a big zero or one. It should be easier now to count the number of ways to arrange these zeroes and ones.

Hint 2If the number of big zeros is $$$k$$$ you want $$$x_1 + x_2 + ... + x_k = n_0$$$. where $$$l_0 \leq x_i \leq r_0$$$. It's the same for the ones. Now you need to count the number of valid distribution of $$$n_0$$$ among these $$$k$$$ variables.

Hint 3To solve the previous hint, check this out and the article that it leads to.

I hope this helps you.

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

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

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

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.

binary search is unnecessary. It only saves the first and last occurrence of each letter.

Hello bro, thank you so much! I solved 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.

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

Still giving me TLE :/

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.

BTW you sorted the array in ascending not descending

even after descending still TLE :D

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

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

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

First you have 1-D for

. Then you have 10 values — The Frequency of each digit of the numbers chosen so far.idThe 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).

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

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

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.

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

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

What is the reason of this being correct?

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

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

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.

Done, Thank you for reminding us.

Any hints to problem L? thank you.

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 :)

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.

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

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

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

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.

Auto comment: topic has been updated by ahmad_alghadban (previous revision, new revision, compare).really wow lovely contest Thanks all for your efforts.

What a great problemset!! I REALLY ENJOYED IT !

Could anyone give hints about problem C ? Thanks in advance

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

Hint 1 : How can we simplify this expression ?for each pair $$$(i , j)$$$ such that $$$ 1 \le i , j \le n$$$ , how many times can this pair appear over all permutations $$$p$$$ where $$$i$$$ and $$$j$$$ are consecutive elements ?

we can so multiply this number by $$$dist(i , j)$$$

Hint 2 : How many times can this pair appear over all permutations p ?it is equivalent to count the number of ways to fix $$$i$$$ in the first $$$n - 1$$$ positions which is $$$(n - 1)!$$$

Hint 3 : What is the final value of e ?$$$e = \frac{\sum p_i}{n!} = \frac{\sum\sum (n - 1)! \cdot dist(i , j)}{n!} = \frac{(n - 1)! \cdot \sum\sum dist(i , j)}{n!} = \frac{\sum\sum dist(i , j)}{n}$$$

It is easy to compute $$$\sum\sum dist(i , j)$$$ with dp on trees , you can refer to the following problem : problem

Thank you, this is an amazing idea.

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

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)!

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.

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.

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.

I'll try, thanks for the type.

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

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.

where is the solution of these problems ? plz

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

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