justHusam's blog

[Gym] 2019 JUST Programming Contest
By justHusam, 6 years ago, In English

Hello Codeforces,

I would like to invite you all to participate in the 2019 JUST Programming Contest of Jordan University of Science and Technology. The contest was originally held on $$$23^{rd}$$$ of March, and it will launch in Codeforces Gym on Friday, 29 March 2019, 13:00 UTC.

The problems were prepared by justHusam (Husam Musleh), Aristos (Hamzeh Sahyoun), Lvitsa (Alaa Abu Hantash), H2A_TLE (Asem Al-Radaideh), and Thunder_r (Bara' Al-jawarnEh).

Thanks to Mockingjay (Sarah Abu Elayyan) 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 to everyone, and I wish you all accepted solutions!

Update: Registration is now open.

Update: The contest has ended. Congratulations to all participants!

You can check the scoreboard of the onsite contest on the following link.

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

Comments Comments (28)
| Write comment?
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

    JUST already did it. You should be Jordanian to understand how XD.

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

How to solve A and L?

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

    For L , the problem is very similar to IOI 2010 Quality of living , you can see here my solution to it and with explanation , don't forget to use scanf and printf because normal input and output will make TLE.

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

    A: you may have already noticed this is a graph problem, with the cards being edges, and the nodes containing a character.

    For every non-bridge edges in the graph, change their weight to 0 (since we can just wand them instead). Build a minimum spanning tree over these edges. Root this tree anywhere you like. Now for each A/H character in the tree you'd want to "lift" them up, moving them closer to the root, until they meet their counterpart character.

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

Can anyone tell why we need dp in D? Where greedy solution fails? I am not able to find case where it fails? Code

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

    Check this test case:

    $$$0001000010$$$
    $$$1111111011$$$
    $$$0101001000$$$

    Your code output is "1111111100", while the correct answer is "1111111111".

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

      Can you share the approach to solve D?? I tried solving Greedily but getting WA.

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

        Try every permutation of the first two strings, then you can greedily match the 3rd

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

          My intitial solution was the same as you mentioned. But after a rough calculation I thought it will not fit in time limit. As it's time complexity will be roughly O(T * 252 * 252 * 10); As maximum permutation of a string will be max 252 (i.e. five zero's and five one's).

          Example :

          T = 250

          for every T all the three strings be same

          1111100000.

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

            Not very surprising :)

            The 1e8/1s bound is a simple approximation. As long as you don't do anything too costly, it should pass smoothly. I used that approach and passed in 233ms. In one problem I did O(M*2^N) for N = 19, M = 5000 and it passed in 2.3s

            I suppose it comes down to optimization skill and confidence for one particular problem.

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

              Mine too got an AC in 265ms. But if we consider the test case i mentioned above i don't think that our solution will work on it within given TL.

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

                You have a point.

                My code runs on 1500ms for your case :) looks like I found an unintended solution.

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

            Actually you only need to try all permutations of the second string, first one can be fixed (or vice versa) and then greedily match from the third. The complexity is now around $$$O(T * 252 * 10)$$$ and my accepted code runs in 15ms.

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

Hi there, can anyone help me find a counter case for problem D code I tried a lot of cases but it seems to work, I cannot find a counter case

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

    Check this test case:

    $$$1111110000$$$
    $$$1001001110$$$
    $$$0100001001$$$

    Your code output is "1111111100", while the correct answer is "1111111111".

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

How to solve C — Large GCD?

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

Any editorial for this contest?

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

How to solve K?

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

    Lets fix the left barrier of the subarray. A key insight in this case is to note that we can't get more than log_a different results as we keep expanding to the right. Why? The OR result is always non-decreasing. Either it stays the same, or one or more bits get turned on. So, every different result turns on at least one new bit, but we only have log_a bits, so the possibilities are limited to this number.

    Having this insight, for every left barrier i ( from 1 to N ) we can do the following. Start with a range [i,i]. Insert the OR of the range to a set. Then, as long as we can keep expanding our right barrier, binary search the closest right barrier that increases the OR of the range. When we find it, insert the OR of the new range and repeat. Stop when we can't find a new OR.

    We will try N different left barriers, and in each one we will make at most log_a binary searches. To calculate the OR of a range quickly we can use a sparse table. This would give us a complexity of N*lgN*lgA that fits perfectly in time.

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

Any tips for problem k?

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

Any tips for H and I?

→ Reply