Блог пользователя justHusam

Автор justHusam, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +60
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

How to solve A and L?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Check this test case:

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

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Check this test case:

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

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C — Large GCD?

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Any editorial for this contest?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve K?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any tips for problem k?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Any tips for H and I?