justHusam's blog

[Gym] 2018 JUST Programming Contest 1.0
By justHusam, history, 7 years ago, In English

Hello Codeforces,

I would like to invite you all to participate in the 2018 JUST Programming Contest 1.0 of Jordan University of Science and Technology. The contest was originally held on 17th of March, and it will launch in Codeforces Gym tomorrow Friday 13 April 2018 13:00 UTC.

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

Thanks to MahmoudHamdyY (Mahmoud Hamdy) for sharing the idea of one problem.

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: During the contest today, and after 2 hours and 51 minutes, we received a notification from a team that the author's solution to problem B. Ran and the Lock Code is wrong. Immediately, we checked our solution with respect to their test case to figure out what is the error. It turns out that the solution's idea is totally wrong. So, we have updated the solution and rejudged all the submissions. Since we rejudged all the submissions 15 minutes before the end of the contest, we increased the contest's duration by 30 minutes. We are really sorry for this error. Finally, I would like to thank team Ruhan Habib Fan Club and its members: Rezwan.Arefin01, Alpha_Q, and Bruteforceman for reporting the error.

UPD: Tutorial

Tags gym
  • Vote: I like it
  • +28
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Great, will there be tutorials after the contest shortly?

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

This contest is intended to do individually or in team?

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

What is test 2 in D problem? My solutions uses bitmask+dp.

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

    Some large random(I guess) test, you can view it using coach mode. My solution is bitmask dp too.

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

      Can you share your code?

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

        click

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

          Thanks, btw what is tricky case for B problem? I did min(n, a * 2 - 1), but i failed.

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

            We reported that. Actually their initial solution was wrong too.

            Consider n = 10, a = 2, then answer is 5 — [1, 2, 3, 4, 5, 1, 1, 1, 1, 1], but that formula gives 3. Actually any optimal solution is in this format [1, 2, 3, ..., 1, 1, ...]. You can do binary search on the solution.

            Btw, I wonder, did they use same dataset in onsite contest too :3

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

              "We are really for this mistake :(" — didnt see that coming. xD

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

Isn't problem D just edge weighted Steiner Tree? Is there a better solution than O(Tn3k)?

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

    I was very unclear on what a subgraph meant in terms of this problem. Got AC with by trying every subset of nodes and finding the minimum spanning tree of those nodes. Throw out subsets that don't include all important vertices.

    What are T, n, and k in your runtime?

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

      T, n, k from statement. T = Number of testcases, n = number of nodes, k = number of nodes we need to cover.

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

Can someone give hint for G problem?

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

    You need to notice that triangles OAD and OBC are similar. After that you need some easy calculatons and using formula P = a·b·sin(x)

    Formula actualy is not so important, but easier for solving (at least to me).

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

any hint about problem F?

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

    2d prefix sums.

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

    What we need to find is the number which have (n + 1) / 2 numbers less than it in that range where n is the size of submatrix. This can be done using 2D frequency sums of each number(<= 500) and then using another 3D matrix, dp[k][i][j] which denotes no of numbers less than equal to k in the range [1,1] to [i,j]. This matrix along with binary search produce the required answer. https://ideone.com/EnCunm

    → Reply