justHusam's blog

[Gym] 2017 ACM Amman Collegiate Programming Contest
By justHusam, 7 years ago, In English

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), alfadel (Ali Fadel), Lvitsa (Αlαα Abu Hantash), and flerynn (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.

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

Comments Comments (47)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve task J?

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

    You only need to check the values i, len / i for i * i <= len.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      TY. Seems that I misunderstood the problem: I thought that we can rearrange words.

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

      Can you explain, or provide the sample code.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

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

    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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve task F and G?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    F : greedy, just remove the ingredient with greatest next_pos.
    G : Interval is good if it's sum % lcm = 0.

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

      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

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I always get TLE on problem F even I already use set

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

      why i got wa when i'm using the method you said?

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

    any tricky test cases for problem F ?

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve task L and M? Help please :D

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

    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.

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

      thanks

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

      Thanks a lot.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why are you running bellman-ford with a source vertex of 1? What if the negative weight cycle is not visible from this vertex?

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

        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.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem I ?

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

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F with greedy QAQ.

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

How to solve problem K ?

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

Can anyone provide tutorial?

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 )

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain how to solve D?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    this is combination problem, and u have to know modular multiplicative inverse to compute large combination

    → Reply