### justHusam's blog

By justHusam, 3 years ago, ,

Hello Codeforces,

I would like to invite you all to participate in the 2017 ACM Amman Collegiate Programming Contest (AmmanCPC 2017). The contest was originally held on 19th of August, and it will launch in Codeforces Gym on Friday 25 August 2017 14:00 UTC.

The problems were prepared by Hasan0540 (Hasan Alhamsh), justHusam (Husam Musleh), AliOsm (Ali Fadel), Alaa_AbuHantash (Αlαα Abu Hantash), and yosef_darwish (Yosef Darwish).

The duration of the contest is 4 hours, and the registration will be open 6 hours before the start of the contest.

Good luck for everyone, and I wish you all Accepted solutions.

UPD: Registration is currently open.

UPD: The contest will start in 30 minutes.

• +93

 » 3 years ago, # | ← Rev. 2 →   0 how to solve task J?
•  » » 3 years ago, # ^ |   0 string must be divided on prime number, is that right ? noticed but time over before coding
•  » » 3 years ago, # ^ |   +3 You only need to check the values i, len / i for i * i <= len.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 TY. Seems that I misunderstood the problem: I thought that we can rearrange words.
•  » » » 3 years ago, # ^ |   0 Can you explain, or provide the sample code.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Suppose, n = count of words Then, len = n + Now you should split this len into some lines with equal sizes. For that you should find all divisors of len Suppose, you choose some k such that len % k == 0, len / k > 1. To check whether you can split the whole text into lines of length k, just iterate over the words and calculate value sum of lengths + count of words (i.e. spaces) until you reach k. If your sum is not equal to k, then you can't split the words using chosen length, otherwise check next words. If you found that you checked all the words, then you found the answer.
•  » » » » » 3 years ago, # ^ |   0 Got it, thanks
 » 3 years ago, # |   +8 Hints for M? We could determine the last point(greatest element in distance array) and then placing elements either from start point or end point but this couldn't pass.
•  » » 3 years ago, # ^ |   +8 I had a similar solution. When I was generating possible indices for all 2^(n-2) bitmasks repeatedly, I was getting TLE on test 2. Then I changed it to dfs-like solution so as to save same computations in different bitmasks and it passed the tests.Code: link
 » 3 years ago, # |   0 How to solve task F and G?
•  » » 3 years ago, # ^ |   +1 F : greedy, just remove the ingredient with greatest next_pos. G : Interval is good if it's sum % lcm = 0.
•  » » » 3 years ago, # ^ |   0 Im getting TLE on testcase 2 on problem G..my solution is O(n^2)...can you provide me a faster one??thanks in advance
•  » » » » 3 years ago, # ^ |   0 Because your LCM calculation overflows.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I always get TLE on problem F even I already use set
•  » » » 3 years ago, # ^ |   0 why i got wa when i'm using the method you said?
•  » » » » 3 years ago, # ^ |   0 For which problem?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 AC
•  » » 3 years ago, # ^ |   0 any tricky test cases for problem F ?
•  » » » 3 years ago, # ^ |   0 maybe something like this 20 22 1 3 1 3 1 3 1 3 1 2 2 2 2 2 2 2 2 2 2
•  » » » » 3 years ago, # ^ |   0 expected output plz ?
•  » » » » » 3 years ago, # ^ |   0 answer is 4
 » 3 years ago, # | ← Rev. 2 →   0 why after this contest I can't see test cases in other problems in problemset, for example in other people submissions (not in GYM, obviously not for this contest)???P.S. there is nothing in FAQ, so question is reasonable
 » 3 years ago, # |   0 How to solve task L and M? Help please :D
•  » » 3 years ago, # ^ |   +3 L: use bellman ford to check for a negative cycle then dfs with dp from each node to get it's minimum shortest path (ignore cycles since they are all positive). This solution passed in 2324 ms.Here is my code.
•  » » » 3 years ago, # ^ |   0 thanks
•  » » » 3 years ago, # ^ |   0 Thanks a lot.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Why are you running bellman-ford with a source vertex of 1? What if the negative weight cycle is not visible from this vertex?
•  » » » » 3 years ago, # ^ |   0 It doesn't matter, if the negative cycle wasn't in the component of vertex 1 it will still be detected by bellman ford, that's because relaxation will occur in the negative cycle due to the negative edge weights.
•  » » » » » 3 years ago, # ^ |   0 Got it, thanks.
 » 3 years ago, # |   0 How to solve problem I ?
•  » » 3 years ago, # ^ |   0 Since we can remove at most 1 stone from each pile, it gives us a hint to think in terms of parity.Let (p1,p2) represent stones in pile1 and pile2 respectively. (0,0) is a losing state since no step is possible.Notice that if the state of piles is (even,odd) , (odd,even) or (odd,odd), the current player can always push the state to (even,even). In return the 2nd player must bring the state of piles to one of the 3 initial states. This continues till the first player forces the second player to (0,0). Hence the second player wins iff both piles have even number of stones in the beginning otherwise the first player wins.
•  » » » 3 years ago, # ^ |   0 Understood , thanks !
 » 3 years ago, # |   0 How to solve F with greedy QAQ.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +4 It's a standard greedy problem known as optimal scheduling algorithm. I knew this from an OS course :P. You can find a similar problem here with editorial and access to many codes http://codeforces.com/problemset/problem/802/B
•  » » » 3 years ago, # ^ |   0 thanks ！
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 TAT
 » 3 years ago, # |   +3 How to solve problem K ?
•  » » 3 years ago, # ^ |   0 http://paste.ubuntu.com/25415416/Solve the problem by DP
•  » » » 3 years ago, # ^ |   0 Thanks :)
 » 3 years ago, # |   +3 Can anyone provide tutorial?
 » 3 years ago, # |   +7 Can anyone give me a hint on how to solve G. I precomputed the LCM for all [i..j] segment and then check if the sum of each segment is divisible by its LCM but it keeps getting TLE.
•  » » 3 years ago, # ^ |   +4 your solution is correct but need simple modificationwe assume that we have 2000 prime number then the LCM become very huge number ..from constraints the sum of all 2000 number doesn't exist ( 2000 * 10^9 ) .. so when LCM become bigger than this limit we don't need to continue ,because ( sum % LCM == sum ) because ( LCM > sum )
•  » » » 3 years ago, # ^ |   +4 Thank you I didn't think of that.
•  » » » » 3 years ago, # ^ |   +1 you’re welcome :)
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 IGNORE
 » 3 years ago, # |   +1 Can someone explain how to solve D?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 this is combination problem, and u have to know modular multiplicative inverse to compute large combination
•  » » » 3 years ago, # ^ |   0 my solution doesn't pass the second test. can I see your solution ?
•  » » » » 3 years ago, # ^ |   0 your nCr formula is wrong
•  » » » » 3 years ago, # ^ |   0 that quora thread need some modification