fcspartakm's blog

By fcspartakm, 9 years ago, translation, In English

525A — Vitaliy and Patty

To solve this problem we need to use array cnt[]. In this array we will store number of keys of every type, which we already found in rooms, but didn't use. Answer will store in variable ans.

Now, we iterate on string. If current element of string si is lowercase letter (key), we make cnt[si]++. Else if current element of string si uppercase letter (door) and cnt[tolower(si)] > 0, we make cnt[tolower(si)]--, else we make ans++. It remains only to print ans.

Asymptotic behavior of this solution — O(|s|), where |s| — length of string s.

525B — Pasha and String

At first we need to understand next fact — it doesn't matter in wich order make reverses, answer will be the same for all orders.

Let's numerate elements of string from one. To solve given problem we need to count how many reverses will begin in every position of string. Then we need to count array sum[]. In sum[i] we need to store count of reverses of substrings, which begin in positions which not exceeding i.

Now iterate for i from 1 to n / 2 and if sum[i] is odd swap si and sn - i + 1. After that it remains only to print string s.

Asymptotic behavior of this solution — O(n + m), where n — length of string s, m — count of reverses.

525C — Ilya and Sticks

This problem can be solved with help of greedy. At first count array cnt[]. In cnt[i] will store how many sticks with length i we have.

Now iterate for len from maximal length of sticks to minimal. If cnt[len] is odd and we have sticks with length len - 1 (that is cnt[len - 1] > 0), make cnt[len]-- and cnt[len - 1]++. If cnt[len] is odd and we have no sticks with length len - 1 (that is cnt[len - 1] = 0), make cnt[len]--.

In this way we properly done all sawing which we need and guaranteed that all cnt[len] is even. After that iterate similary on length of sticks and greedily merge pairs from 2 sticks with the same length in fours. It will be length of sides of sought-for rectangles, left only summarize their squares in answer. In the end can left 2 sticks without pair, we must not consider them in answer.

For example, if cnt[5] = 6, cnt[4] = 4, cnt[2] = 4, we need to merge this sticks in following way — (5, 5, 5, 5), (5, 5, 4, 4), (4, 4, 2, 2). Two sticks with length 2 are left, we must not count them.

Asymptotic behavior of this solution — O(n + maxlen - minlen), where n — count of sticks, maxlen — maximal length of stick, minlen — minimal length of stick.

525D — Arthur and Walls

To solve this problem we need to observe next fact. If in some square whith size 2 × 2 in given matrix there is exactly one asterisk, we must change it on dot. That is if in matrix from dots and asterisks is not square 2 × 2 in which exactly one asterisk and three dots, then all maximum size of the area from dots connected by sides represent rectangles.

Now solve the problem with help of bfs and this fact. Iterate on all asterisks in given matrix and if only this asterisk contains in some 2 × 2 square, change this asterisk on dot and put this position in queue. Than we need to write standart bfs, in which we will change asterisks on dots in all come out 2 × 2 squares with exactly one asterisk.

Asymptotic behavior of this solution — O(n * m), where n and m sizes of given matrix.

525E — Anya and Cubes

To solve this problem we need to use meet-in-the-middle. At first sort given array in increasing order and divide it in two parts. In first part must be first n / 2 elements, in second part — other.

Iterate all submasks of all masks of elements from first part. That is iterate which cubes from first part we take and on which from them we paste exclamation marks. In this way we iterated all possible sums, which we can get with cubes from first part. Let for current submask we get sum sum_lf and use tlf exclamation marks. To store all such sums we use associative arrays map < long long > cnt[k + 1], where k — count of exclamation marks which we have in the beginning.

After that similary iterate all submasks of all masks of elements from second part. Let for current submask sum is sumrg and number of used exclamation marks is trg. Then from first part we need to get sum (s - sumrg) and we can use only (k - trg) exclamation marks, where s — sum which we must get by condition of the problem. Then iterate how many exclamation marks we will use in first part (let it be variable cur) and increase answer on cnt[cur][s - sumrg]. To accelerate our programm we may increase answer only if cnt[cur].count(s - sumrg) = true.

For submasks in iterate we can cut off iteration on current sum for submask (it must be less or equal to given s) and on current count of exclamation marks (it must be less or equal to given k). Also we should not paste exclamation marks on cubecs with numbers larger than 18, because 19! more than 1016 — maximal value of s.

Asymptotic behavior of this solution — O(3((n + 1) / 2) * log(maxcnt) * k), where n — count of cubes, maxcnt — maximal size of associative array, k — count of exclamation marks.

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

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Fastest editorial so far! Thanks!

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

your rounds are awesome :D won't miss any of them :3

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

What was test case 4 for problem C??

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

    Now we can see it's 8 5 3 3 3 3 4 4 4. I got 3 WAs on test 4 because of misunderstanding the problem statement

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

      i too misunderstood the problem statement :(

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

        What's that? I don't see it... Where does the "25" come from?

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

          It was the sum of all possible rectangles that could be made. Not the max of those.

          I also got to know now ! :(

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

          We can choose {5-1, 4, 4, 4} to make a rectangle and choose {3, 3, 3, 3} to make another one, and we get the maximum total area which is 16 + 9

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

        me too!but I understand it finally

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

    we convert 5 to 4 so we have 4, 4, 4, 4 -> 4 * 4 = 16 and we have 3, 3 , 3 ,3 — > 3 * 3 = 9 so total maximum area is 9 + 16 = 25 not 16 !

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

    In problem C use long long Because the input and Output is large it can't covered by long

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

Thank you for nice problems:) BTW, for 530E, I think associative array cnt should be map < long long, int >

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

Im getting wrong answer on test 4 problem C....why? where 25 comes from?

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

    Make 5 equal to 4 by reducing it and then you have 4,4,4,4,3,3,3,3. So total area = 16+9;

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

      I got it man....i thought that they only need the maximum area not the sum..so i was getting 16

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can someone please explain why in Problem C the output for test 4

8
5 3 3 3 3 4 4 4

is 25 instead of 16? Thanks.

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

    You can use 5 (-1), 4, 4, 4 for one rectangle and 3, 3, 3, 3 for another.

    4*4+3*3=16+9=25

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

    5 becomes 4, and then the rectangles are: { 4, 4, 4, 4 }, { 3, 3, 3, 3 }. First's size is 16, second's is 9.

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

    man i did the same mistake....i thought they need the maximum possible area....but they needed the sum of all maximum possible area... I think this problem should be reviewed...

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

      I totally agree with you. A lot of people including myself misunderstood the problem statement. It should have been something like:

      "..maximum total area of ALL THE POSSIBLE rectangles that Ilya can make .."

      Aside from this the round was great. Many thanks to the problems setter =).

»
9 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I liked E a lot, and I had the idea in contest, but made some stupid mistakes...Anyway, now, after the contest ended, I tried to find the bugs, and, apparently, I found them, but I have TLE because of map(I checked, not at the point when we insert in map, is because of the point where we are "querying" the map).Here is my source: http://codeforces.com/contest/525/submission/10476721

I really don't know what's so wrong.It inserts me in map in 0.5 seconds and queries in 18 seconds...

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

    On lines 40,41 and 78,79 you make about 2^n iterations, wich is way larger than 3^(n/2), wich is the optimal complexity for finding all the submasks of a mask.

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

      It's not because that.I reimplemented it and it was the same thing.The idea is that I have 2^n and it enters in for just for 3^(n/2) :-P .Here is the new source: http://codeforces.com/contest/525/submission/10477139 I thought it was easier for someone to look at th first source ant that's why I posted that one.

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

        First, don't try this _j < (1<<n_bit);, it is slow. Second, you could implement 3^(n/2) in a faster way by just iterating the masks from 1 to 3^(n/2) and considering : 0->not taken 1->taken without factorial 2->taken with factorial

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

    Try unordered_map.

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

      I'll try it but I still can't believe that it take it so much to query, knowing that it inserts in 0.5 seconds with the same complexity

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

    As editorial said, "To accelerate our programm we may increase answer only if cnt[cur].count(s  -  sumrg)  =  true."

    The operator[] creates a new object if it wasn't there before, which will slow down subsequent queries by a bit.

    Accepted: 10478038

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

      WOW, it's a really big difference of times just because that...I'll never make the same mistake :))Thanks

»
9 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Pasha and string can be solved in O(n) time using BIT. :)

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

    No operation of BIT takes linear time it always involve logn factor

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

    Every operation on BIT takes O(logn) time. How is it O(n)?

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

Probably a silly mistake on my part, but This code outputs the right answer (8) for the first test case (4, 2 4 4 2) when i debug it on my machine but outputs 4 and fails on pretest 1 when tested on the website. I know the algorithm is greedy and might not be right but why does it have a different output? Thanks in advance!

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

    I figured it out. It seems that par[++i] is behaving different on the website's compiler. Weird.

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

Please help me with the logic used in the problem 525B especially the 'sum' part ? :

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

    So, let's start with an example word "abcdef".

    Our possible operations include:

    1 (reversing letters from [1,6]),

    2 (reversing letters from [2,5]),

    3 (reversing letters from [3,4]),

    4 (reversing letters from [3,4]),

    5 (reversing letters from [2,5]),

    6 (reversing letters from [1,6]),

    I will call operations rather by their intervals now, I think it's easier to understand that way.

    Now focus on the first letter "a" for a while. It can only change it's place after reverse operation [1,6]. Where it can go? Only at the end, swapping with "f". And after the second one of that type? "a" will go back to the first position again, swapping with "f". No other operation can change position of "a", all other operations will only change something inside the word, between "a" and "f". So how can we now where is "a" after all operations? Well, that's simple, let's count all of the type [1,6], if it's even then "a" stays on the position 1, if it's odd then "a" is swapped with "f". If you can't see it just do few operations [1,6] in your head or on piece of paper and look what happens. Let's store information about number of operations [1,6] in sum[1], you will see why in few seconds.

    Ok, moving onto "b". "b" can be swapped with "e" after operations [2,5], but also [1,6]. "Even-odd rule" works there two, as it's really the same thing — only changes "b"-"e" are possible and they come after [1,6] or [2,5]. Ok, so if we store number of operations [2,5] in sum[2] only thing we need to know is number of operations [1,6]. Now sum[1] comes into play :) Only thing we have to do for "b"-"e" is check if sum[1] + sum[2] is odd and, if it's the case, swap "b" with "e".

    One thing you may not see now, but it's also the small problem — for position 3 it's easy, just sum up sum[1] + sum[2] + sum[3]. But you would have to do that addition for every position from the first half of the string and for long ones it can be little bit painful. Don;t worry though, there is one Jedi trick :) Just iterate over all i's from 1 and do:

    for (int i = start_position; i < s.length() / 2; ++i) {

    if (i != 0) sum[i] += sum[i — 1];

    //computations here

    } In first iteration we have sum[1] in sum[1], in the second one sum[2] + sum[1] in sum[2], in the third one sum[3] + sum[2] + sum[1] in sum[3] and so on. Just what we needed :)

    EDIT: My code: http://codeforces.com/contest/525/submission/10479343

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

      Perfect explanation sir !! Thank u , thanks a lot :)

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

For E can't we just loop over all k-sets in a maximum of (25 choose 12)=5*10^6 ways and update the sum from one k-set to the next in O(1) by simply changing one factorial to a different factorial? (Of course we ignore factorials which are too big)

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

Can someone explain to me the solution for #4? I used BFS on a space, then got the width and height of the total room, and within the width and height set everything to a '.'. It gives me a wrong answer on case 20, but the case is too large.

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

    I don't understand solution well enough to explain it, but those are smaller counterexamples to your solution:

    the one showing something is wrong with your bfs

    3 3

    **.

    **.

    ...

    and the one showing "one-time" bfs is not enough

    3 3

    **.

    .**

    ...

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Thank you! Did you happen to solve the problem? Can you explain the solution?

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

In the editorial's solution for Pasha and String

Then we need to count array sum[]. In sum[i] we need to store count of reverses of substrings, which begin in positions which not exceeding i.

I don't get this statement. Could someone explain it in greater detail?

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

In problem E you don't need to sort the given array.

»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I tried to solve problem D in the following,

Find the connected components from the given maze. And also find the boundary of the connected component.( top,bottom, left,right). And make all the cells in the maze which lies in the boundary to ".".

Also kind of handled case like this with double run of algo.

.... .... ..*.. ...*. ....*

Is there anything wrong with this approach ? This approach was failing for test case 12.

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

    Consider this initial connected components:

    *********
    *1*******
    *1*******
    *1***3***
    *111*****
    *1*******
    *1*22222*
    *********
    

    When you only draw dots on the boundary you get:

    *********
    *1112222*
    *1*1***2*
    *1*1*3*2*
    *111***2*
    *1*1***2*
    *1122222*
    *********
    

    You don't discover that 3 is also part of the 1-2 room.

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

      After you find a boundary ( top, bottom, left, right), my idea is to convert every cell inside the boundary to "." .

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

        hello , your idea is correct, you have a lot of rectangles , but you have to merge rectangles that intersect, and then fill the rectangles with '.'

        the most difficult is solve the last part, how do you merge rectangles optimaly???

        my idea was make a sweep line on x , and then merge rectangles on y , keep a structure, the code is very difficult , therefore is better analize the problem and make it more easy!!

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

        I used the same method as yours, but I got TLE on test 12. I don't know why I got TLE, because I don't think it would cost such long time.

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

Could somebody help me come up with a case where my solution fails?

I chose to forgo the option of keeping track of how sticks of length L I had. Instead, I sorted the sticks in descending order according to their lengths. Then, I tried greedily choosing the four largest sides, assuming that the difference between the opposing was always less than or equal to 1 (otherwise, I would be unable to cut accordingly). Thanks for your help in advance.

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

For problem E, I din't pass the system test if I used map(10491477) but passed with unordered_map(10491490). But, interestingly, 10480213 (from which I got the idea because it was easy to understand) passed system test. What is going on?

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

I get wrong answer for problem c for test case 37. Can somebody provide a counter example for my approach. 10502423

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

Hello, I tried to solve problem D about 20 times but verdict is always "runtime error on test 92". Could you help me, please? Regards 10507530

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

    I also got a runtime error on test case 92.I just changed string to char array and took the input character by character.It got AC.10776197

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone discuss solution of D and proves of solution?

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

could someone explain where my solution goes wrong for 525C . I am having wrong answer in test case 37 . http://codeforces.com/contest/525/submission/10501081 . My output : 11234878867001938 jury's answer : 11234878866984153 . Thank you for help

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

    Try the following test case:

    6
    7 7 6 6 6 4
    

    Should output 42. But yours outputs 43. Third time through the loop i=1,area=1,count=2. So you add area to totalarea which you shouldn't.

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

How can one prove the solution to D? (I mean the property of 2x2 matrix)

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

Can someone explain the solution for D better? I honestly can't understand the editorial's solution, as the writer's English is not the best.

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

In problem D, my dfs solution is accepted but when the same logic is applied using bfs i am getting tle. Can anyone guide me why is it hapenning ??

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

can anyone explain why am i getting wa !!

TIA

here is maah code

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  1. In problem B : How I should approach if given problem is like given index l and r . You have to reverse the string the string from a[l] to a[r].
  2. What would be its approach ?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A ,I used unordered multiset to store the keys, but why its getting TLE in test 8?