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, justHusam, alfadel, Lvitsa, and flerynn.
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.
how to solve task J?
You only need to check the values i, len / i for i * i <= len.
TY. Seems that I misunderstood the problem: I thought that we can rearrange words.
Can you explain, or provide the sample code.
Suppose, n = count of words
Then, len = n +
Now you should split this
leninto some lines with equal sizes. For that you should find all divisors oflenSuppose, you choose some
ksuch thatlen % 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 valuesum 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.Got it, thanks
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.
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
How to solve task F and G?
F : greedy, just remove the ingredient with greatest next_pos.
G : Interval is good if it's sum % lcm = 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
I always get TLE on problem F even I already use set
why i got wa when i'm using the method you said?
For which problem?
AC
any tricky test cases for problem F ?
maybe something like this
20 2
2 1 3 1 3 1 3 1 3 1 2 2 2 2 2 2 2 2 2 2
expected output plz ?
answer is 4
How to solve task L and M? Help please :D
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.
thanks
Thanks a lot.
Why are you running bellman-ford with a source vertex of 1? What if the negative weight cycle is not visible from this vertex?
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.
Got it, thanks.
How to solve problem I ?
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.
Understood , thanks !
How to solve F with greedy QAQ.
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.me/problemset/problem/802/B
thanks ！
TAT
How to solve problem K ?
http://paste.ubuntu.com/25415416/
Solve the problem by DP
Thanks :)
Can anyone provide tutorial?
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.
your solution is correct but need simple modification
we 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 )
Thank you I didn't think of that.
you’re welcome :)
IGNORE
Can someone explain how to solve D?
this is combination problem, and u have to know modular multiplicative inverse to compute large combination
my solution doesn't pass the second test. can I see your solution ?
your nCr formula is wrong
that quora thread need some modification