justHusam's blog

By justHusam, history, 4 months ago, In English,

Hello Codeforces,

I would like to invite you all to participate in the 2017 JUST Programming Contest 2.0 of Jordan University of Science and Technology. The contest was originally held on 1st of April, and it will launch in Codeforces Gym tomorrow; Friday 7 April 2017 13:00 UTC.

The problems were prepared by Alaa_AbuHantash (Αlαα Abu Hantash) and justHusam (Husam Musleh).

Thanks to Vendetta. (Ibraheem Tuffaha) for testing the problem set.

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  
  • +42
  • Vote: I do not like it  

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Is there gonna be editorial for the problems?

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

How to solve A?

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

      Hi there,

      I tried approaching the problem with DP ... and I didn't see the O(1) formula ! Great work... I understood how to computer the probability. But, I'm struggling with getting the answer into the output format the question is asking.

      I know how to compute the answer in terms of getting probability as a floating point number.

      Can you explain ... given a floating point number f, how to get a fraction p/q, and from there get a y such that y*q = p (mod 1e9 + 7) ?

      Thanks.

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

        You can get the floating number x using string. The multi x 1000. So p/q = x*1000/1000.

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

          I didn't understand. Can you elaborate ?

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

            I think your question's answer is calculating the probability in inverse element. My poor English.

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

              No Problem ! Can you just write the piece of code that does what you say ? Then, i can understand. Or maybe some Wikipedia links ... I appreciate your help. By inverse, do you mean inverse in the modulo group 1e9 + 7 ?

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

                Yes.Maybe my words is this p / q can be changed to p * inverse of q.

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

              If p is the inverse of q, does it mean that

              pq = 1 (mod 1e9 + 7) ?

              This is what I understood.

              How do I convert the floating point number to this p/q form ? Please help.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J?

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

    Hi! Quite late, but hopefully it will help someone. Perhaps my solution is too complicated, I would love some feedback.

    1. Remove all such arrays which are wholly contained within another array.

    2. Model the problem as a graph. Each array is connected to every other array. The edge weight is the "saving" you do when you connect them, i.e., the number of elements in common from one end. We can assume A->B means overlap A's right end with B's left end. Hence, dist[A][B]!=dist[B][A]. I took the edge weights as negative.

    3. Create a dummy vertex connected to every other vertex with edge weight 0.

    4. TSP (it should run as you have at most 16 vertices).

    5. In my case, as edge weights were negative, I simply output the sum of lengths of all arrays + total saving.

    Hope this helps :) Please let me know if some part of my explanation is not clear...

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B by DP ?

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

    Make dp, dp[i] — count of ways we can divide prefix of length i into beautiful substrings. We want to calc dp[i]. Iterate j from i to 1 and break when not all numbers in [j, i] are unique otherwise add dp[j — 1] to dp[i] (making split before position j). Initial values: dp[0] = 1 (if you have indexes from 1). Solution O(n * a), where a = 10. There is also solution O(n) using two pointers.