Hiasat's blog

By Hiasat, history, 7 years ago, In English

Hello Everyone.

I would like to invite you to participate in ACM Arabella 2017 which will be launched in GYM Friday 14/04/2017 14:00 UTC

You will be given 13 problem to solve in 5 hours, The contest difficulty is similar to Div2 Contests.

The problem-set were prepared by Hasan0540 , Hiasat , Motarack Reem , Kilani abed.jaradat , Lvitsa and Ahmad Alkhaldi.

Good luck for everyone.

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

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

How do I register for this? I have never used the "Gym" function before.

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

    It is very similar to regular Contests. Yet the registration button appears a little bit later (typically a few hours before the contest starts).

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

Any hint about problem E :\

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

    If you are the first player then you can have this winning strategy:

    You need to split the the squares into 2 groups each of the same size and whatever the other player does into a group, you are going to make a similar move into the other group till you win (similar to a nim game with 2 piles).

    So if the game starts with an odd number, you can remove 3 squares in the middle to split the squares into 2 equal groups, and if the game starts with an even number you can remove 2 squares from the middle.

    You will be able to use numbers 2, 3 only if the given number is greater than or equal to 4.

    So the first player wins if the given number is 1 or is greater than or equal to 4, otherwise the second player will win.

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

Can someone explain the approach for problem A.

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

      We also need to satisfy j-i>=2.Also we need to eliminate subarrays with exactly 1 one and which are beginning or ending with 1.

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

        @shubhamgoyal__ What about the case "111"? There is clearly one subarray that works, "111", which begins AND ends with a "1".

        EDIT: Oh, I see, it must have both those conditions satisfied for deletion from the total count...

»
7 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

How to solve problem L?

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

    The amount of water could be stored between all walls is .

    Where MaxR[i] is the maximum number of blocks in a wall comes from the right side and MaxL[i] is the maximum number of blocks in a wall comes from the left side.

    So now we will have 2 arrays :

    a which stores the number of blocks in each wall.

    b which stores the number of blocks of each wall + the amount of water on top of each wall.

    If we added the amount of water could be stored on each wall we can see that the numbers we got are sorted in an ascending order until we reach the maximum value then they become sorted in a descending order.

    Queries :

    if the query was of the first type then we should print .

    if the query was of the second type, we will have on these conditions :

    1- : after increasing a[x] it is still smaller than or equal to b[x], in this case we will just update a[x].

    2- : increasing the maximum value, in this case we should update b[index of the maximum value] and a[index of the maximum value].

    3- : after increasing a[x] it becomes larger than the maximum value, in this case we should update all the values between x and the index of the maximum value in array b and make it equal to the maximum value, after updating we should change the maximum value into a[x] then update b[x] and make it equal to a[x].

    4- :after increasing a[x] it becomes larger than b[x] but still smaller than the maximum value, in this case we should update all values smaller than a[x] in array b in the range [x,index of the maximum value] to a[x] and because we know that values between x and index of the maximum value are sorted we can find the first value larger than a[x] (starting from x) and change all the values between x and the first value larger than a[x] in array b into a[x].

    To update sum and get sum value in array b we can use segment tree with lazy propagation and we can use binary search to find the first value larger than a[x] in array b

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

Can someone give some hint on problem G?

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

    used principle

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

      Thanks!

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

      @Hiasat I tried using TSP Complexity (K*2^K) in my submission here (29608212), but I get TLE on the first case. Did I misunderstand your method, or do I need some kind of optimization?

      UPD 1: I made another optimization (in addition to precomputing multiplications), where I precompute the bits turned on in a mask. The code here still TLEs on the first case.

      UPD 2: Changing all of my variables to global ones gave me AC in about 3 seconds...

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

        I know solution with complexity like O(K * (N + KlogK)). First, how to solve this problem: given matrix N*M with 0/1 cells, we need to count number of rectangles without 1-cells. It can be solved using stack in O(N * M).

        So this task is similar but we have not more than 20 1-cells. In that task we visited every column for every row, but in this task we need to visit not more than K columns for every row. When we are iterating row we need to keep sorted by y array of 1-cells with x <= row. I think it is better than exponential solution.

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

          Can you explain how this algorithm does the counting?

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

            Let f[i][j] — count of such (x, y) x <= i, y <= j, there is no 1-cells in subrectangle (x, y, i, j). For example we know f[i][g] (let's call it x), next 1-cell is in column j.

            How to count f[i][j] and add to answer sum of all f[i][s], g < s <= j? It is obvious that f[i][s] = f[i][s — 1] + h, so sum of them is sum_of(x + h * (s — g)) = x * d + h * sum_of(s — g) = x * d + h * (d * (d + 1)) / 2, f[i][j] = x + h * d.

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

Any hints about F? :/

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    [Spoiler Alert]
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Yesss, finally someone is asking about the only problem I wrote :P

    This problem can be solved after realizing the following observation:

    Observation
    Cases
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give me some hints on problem M. I've tried unordered_map and binary search but both failed for me :( This is my binary search code: https://ideone.com/vrkOpV.

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

    The verdict you're getting is Time Limit Exceeded, that means your program was too slow (it could still be correct!).

    Looking at your code, the thing making your program slow is probably the usage of cin and cout, it's common knowledge that they're not the fastest when reading and printing input/output.

    Instead, try using scanf and printf to read and print the variables.

    If you're not already familiar with them, you can read about them here:

    http://www.cplusplus.com/reference/cstdio/scanf/

    http://www.cplusplus.com/reference/cstdio/printf/

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

      Yeah but we can't use scanf with string in C++

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

        Yes we can't.

        Instead we can use a character array (for the problem I think the strings are at most 10 characters), so we can do it like char s[11];.

        Reading a character array using scanf and then converting it into a string (if needed) is still much faster than reading a string using cin.