Mehrdad_Sohrabi's blog

By Mehrdad_Sohrabi, history, 9 days ago, In English

We want to mention BamiTorabi and amoo_safar who we thank for helping us with translating the problems and writing the tutorials.and we want to apologize for div1 A2 and B hopefully you will forgive us :( .

Tutorial is loading...

Prepared by Mohammad.H915

official solution
Tutorial is loading...

Prepared by Mohammad.H915

official solution
Tutorial is loading...

Prepared by Mohammad.H915

official solution
Tutorial is loading...

Prepared by Alishahali1382

official solution
Tutorial is loading...

prepared by Mehrdad_sohrabi

official solution
Tutorial is loading...

prepared by Mehrdad_sohrabi

official solution
O(n2) solution
Tutorial is loading...

will be ready soon.

Prepared by Alishahali1382

official solution
 
 
 
 
  • Vote: I like it
  • +100
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Auto comment: topic has been updated by Mehrdad_Sohrabi (previous revision, new revision, compare).

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

    Codes of Problems

    1440A
    1440B
    1440C, 1439A
    1440D, 1439B
    1440E, 1439C
    1439D
    1439E
»
9 days ago, # |
  Vote: I like it +5 Vote: I do not like it

can you please provide the codes?? :)

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

    Now is 2 am In Tehran, We will done it tomorrow as soon as possible.

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

    I've honestly never found much value in problem setter's code. I always just try to implement the ideas described in the editorial.

    Anyways why not look at contestant's code?

  • »
    »
    8 days ago, # ^ |
    Rev. 19   Vote: I like it -26 Vote: I do not like it

    Here are some implementations, I will update these more

    Problem A - O(n * k) solution - Bruteforces
    Problem A - O(n) solution - Math
    Problem B - O(n*k) Offline solution
    Problem B - O(n*k) Online Solution
    Problem C1 - O(nm) solution - operations <= 3nm - Simple Greedy
    Problem C2 - O(nm) solution - operations <= nm - Greedy
    Problem C2 - O(nm) solution - operations <= nm - Greedy
    Problem C2 analizer for above AC code
    Problem C2 analizer report for all cases with (n = 5, m = 4)
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +46 Vote: I do not like it

      I may get downvotes, but O(3nm) and O(3nm/4) are the same. If you want to compare constants don't use big O notation.

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        Ok then, but actually the result is also ≈ $$$O(f(x))$$$, what should I write then

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

          try this
          Problem C2 <= (3nm/4) operations solution

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I updated and also add an extra solution

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

            this is an overkill but we can in fact solve each row in $$$\frac{m+1}{2}$$$ steps,

            idea is to consider in each row as many columns of size 2 and solve each block of size 2 as follows

            11 : chose block with left most point at i,j and dont flip i+1,j

            01 : chose block with left most point at i,j and dont flip i,j

            10 : chose block with left most point at i,j and dont flip i,j+1

            00 : chill

            code

            So over all number of operations will be atmost $$$ \frac{m+1}{2}*(n-2) + (m-2)+4 $$$

            • »
              »
              »
              »
              »
              »
              »
              8 days ago, # ^ |
              Rev. 3   Vote: I like it +3 Vote: I do not like it

              I used your code and make this checker, it seems my code is overkill too

              Checker of your solution
              Checker of my solution
              Checker of your code report for (5, 4)
              My checker report for (5, 4)
              • »
                »
                »
                »
                »
                »
                »
                »
                8 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Now that's what I call stress testing XD.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      SPyofgame can you please explain use of x,y,z, and t in the 2*2 block code ... are you checking for the number of moves through them?

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        In C1, we know that we can turn off only one cell by $$$3$$$ operations

        Then in $$$2x2$$$ cells, we have to use $$$3x4$$$ operations

        However, by using xor operator, you will reduce the number of calls upto 4 times ! Since the same cells are called will be ignored

        For simpler thinking (ignore the complex math part), here is an example, you need to flip {$$$o2, o3, o4$$$} to turn off {$$$p1$$$} and flip {$$$o1, o2, o4$$$} to turn off {$$$p2$$$}, then you actually need to flip {$$$o1, o3$$$} in order to turn off both {$$$p1, p2$$$}

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          cool... thank you ... now I understood ... nice explaination

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

    check out anyone's code in submission.

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

Does this work for C2 Hard version , let's go to each element of our matrix except the last row and last column and try to fix them by flipping , Requies only one move so we have exhausted nm-n-m moves till now lets try to fix our bottom most row and rightmost column by the brute force way we used for C1 easy Version,It works? If anyone has a counter example?

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

Lodu contest

»
9 days ago, # |
  Vote: I like it +17 Vote: I do not like it

I'd like to see an official Java solution for Div1B.

There was one, right?

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

[deleted]

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't worry about downvotes, random shit from noobs and pupils like me........i didn't check your video, but you can share these things until and unless they are not related to programming.

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

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

Please somebody help.I dont know why this solution 98723050 for 1440A - Buy the String is showing Time limit exceeded on pretest 3. Thank you!!!

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

    I'm not sure whether this's the problem but the size of the string might be 1000 which is greater than ur dp's size

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

    The size of your DP if just 100, but the size of string can be up to 1000, so it might be undefined behavior.

»
9 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Codeforces Round #50000000 Div2 C — So just enumerate all $$$2^{256}$$$ cases and handle them individually...

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

    But wait you have a overflow here.

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

      Can't even make a joke without getting Memory Limit Exceeded error! XD

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

can pls someone explain sum of medians

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

    For each of the $$$k$$$ partitions, greedily fill up the part from the end to the median first, using the largest available numbers. Then calculate the sum of the medians.

    See this submission here — 98706701

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

      my solution can you please check my solution

      what i did is that i have created a k x n matrix

      and for each row I have stored the first element as the first element of the matrix. I mean first element of each k row is first k element of the array

      and the rest n-1 element I have taken from the back of the array

      and to get the ans I have added all the elements of n/2 column of the matrix

      is the concept even correct?

      for n=2 I have handeled it separately

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

I couldn't understand how to solve for the last nth row in binary table question. Can someone plssss help me out....

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

Problem with the Div.2 taskE, my approach with the editorial: When the man wants to eat:

First the man only eats for log(maxY) consecutive things so the time complexity for this is O(log(maxY))

Second we binary search for the place he starts to eat which takes at most O(log(n))

Third we find how much he will eat and this also takes O(log(n))

And to implement the above things I used a segment tree to maintain range_max, range_min, range_sum, so each range-query takes O(log(n))

So for each query of the second type will take O( log(maxY) * ( log(n) + log(n) ) * log(n) ) So it leads to TLE

Can someone please tell me how to boost my algorithm, thanks in advance.

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

    You can binary search on a segment tree for O(log n). Start at the root, if the left subtree is not good, go to the right subtree, else go to the left subtree.

    More specifically, in this problem, you have 2 different binary searches, one for starting place and one for ending place.

    The first binary search is for min i so that a[i] <= x. This is simple.

    The second binary search is for max i so that sum(a[l], a[i]) <= x. This is the same as finding max i so that sum(a[0], a[i]) <= x + sum(a[0], a[l-1]). This binary search is also simple.

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

    You can get rid of binary search in both operations. For example you want to find leftmost position p, such that a[p]<=y. You can store minimum on segments in your segment tree. Imagine that you are standing in the root. You know that minimum in left subtree is larger or equal than maximum in right subtree. So if minimum from left subtree is smaller or equal to y you can go left, otherwise go right. You can do similar thing to remove second binary search.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I also want my p to be greater than the current begin point, so going left might not be able to take a usable minimum.

      So I'll have to iterate almost every vertex of my seg tree which again makes me TLE.

      Thanks for ur time and patience BTW.

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        What’s the problem of taking p=max(p,x)? Because our array is non-increasing. If p is good, then every index after p is good too.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh wow I misunderstood the statement. I thought the modification was for only one position. Again, thanks for ur help and patiences.

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

Can anybody please explain B? Why we are taking the biggest n/2 numbers from the end and smallest n/2 numbers from the beginning? I was not able to understand the proof.

»
9 days ago, # |
  Vote: I like it -42 Vote: I do not like it

Div2 C1/C2 was the most complex implementation problem. Upvote if you agree!

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

In the contest dashboard, there isn't the option of "Tutorials(en)" in the contest material section. please look into it.

Thank you :)

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

Where is the editorial for div2 C1 (easy version of binary table)?

»
8 days ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Nice problemset.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A we can also count zeros and ones in the string and then take the minimum from zeros*h + c1*n, ones*h + c0*n, ones*c1 + zeros*c0. So the total complexity will be O(n/w) (because we use bitset.count() method)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, i think i have made a little mistake here. I haven't calculate the compexitiy of string to bitset operation. I guess, compexity of it is O(n) so the to total compexity is O(n + n/w) = O(n)

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Mohammad.H915 In div1B How do we check if it is a clique or not in O(k^2). I know one way which takes O(k^2*log(n)) but I am not able to understand editorial's approach. can you please elaborate a bit more. Thanks

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can store neighbours of each vertice in an unordered_set.

  • »
    »
    8 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Check it ofline for each vertex that have more than or equal to k-1 we see thier Neighbors, now if you want to know v and u is adjacen just set a new vector for v or u then when you want see neighbors of v just check it adjance with u or not,

    My code
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what does "— 1" part do (tried googling it but all i get is HTML blah ..)?

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      I've never seen an if statement like this if(nxt != k &mdash; 1), can you tell me what it does exactly? Thanks in advance.

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

        Forgive me when such a bug probably occurred while copying

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

B formulars: Consider using \cdot multiplication sign instead of a simple dot.

$$$n\cdot{k}$$$ vs $$$n.k$$$

see http://www.malinc.se/math/latex/basiccodeen.php

»
8 days ago, # |
  Vote: I like it +19 Vote: I do not like it

Could you please take a look at hack 678765? I'm getting "Unexpected Verdict".

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

    Usually it means that the model solution is giving TLE or something.

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

for Div2D/Div1B in the editorial they have put random full stop in sentences and I an not able to understand for checking clique part. How they are assigning 0 and 1 to vertices?

Can anyone please tell how to check for the clique after checking the other one(non empty subset) does not exist?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can just store neighbours of each vertice in an unordered_set. If you have a vertice with $$$k-1$$$ edges, you iterate over all of it's neighbours to check if they form a clique.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but what guarantees that once we have checked a vertex with $$$k-1$$$ edge and it's neighbours then we don't have to repeat the same for it's neighbours too? because if we have to repeat then time complexity will be $$$O(nk^2)$$$ which is not feasible. so can you tell the reason behind the previous claim.

»
8 days ago, # |
  Vote: I like it +26 Vote: I do not like it

For Div1 B, I don't understand this part:

for checking clique candidates fast, iterate over vertices and name current vertex $$$v$$$. then for neighbors of $$$v$$$ set $$$nei_v$$$ to 1 and 0 otherwise. for each clique candidate that contains $$$v$$$ like $$$C$$$, we check edge between $$$v$$$ and $$$u \in C$$$ in $$$O(1)$$$ using array $$$nei$$$.

Especially, what does "name current vertex" mean, and what does $$$nei$$$ do?

I tried implementing similar solution but I got TLE.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it -17 Vote: I do not like it

    We want to check cliques offline so we fix a vertex and check all the edges for that vertex

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

      Does "check cliques offline" means that we check for cliques after removing vertices as much as possible, while recording the vertices with $$$k-1$$$ outgoing edges, and check for cliques after reaching to the end (when we could not find any $$$k$$$-neighbor graph)?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So do you gather all candidates for cliques? Then it's $$$O(n^{1.5})$$$ space complexity, seems very dangerous. Can I see your code?

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        Wrong
      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oops, I mean, the number of vertices added to the list is at most twice as large as the number of edges, so the spacial complexity is $$$O(m)$$$, perhaps?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In Binary Table (hard version) editorial, I am not able to understand how you are performing operations. Like you have written we can use one operation on it, its left neighbour and the two cells above to fix this cell , can someone please explain this. I am also not able to comprehend solution posted by SPyofgame

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you might find this useful(for c1 and c2): https://www.youtube.com/watch?v=qHVt2ulsVxY

    resharing prev comment

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks much for this. Have you implemented this by any chance? I find it tricky to implement the n x 2 section.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    At which part you feel hard to understand ? I will add some other approachs later and extra comments & proves

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I appreciate your solution, but I am finding difficulty in understanding the logic like why you are eliminating the last row, last column. And also how using bitwise XOR solves 2*2 boxes, being a tyro I am not able to grasp the logic, if you can add some explanations it would be very useful for everyone

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        :( If not using XOR to implement, you will have to check 4 if-else

»
8 days ago, # |
  Vote: I like it +106 Vote: I do not like it

I forgot to sort the adjacency list to perform binary search after i switched from set to vector (because the amazing tle) and it somewhat passed even the system test, amazing tests too ;)

https://codeforces.com/contest/1439/hacks/678778

To be honest seems more hard to create tests where my solution is correct than where it's wrong, but you guys did it, unbelievable.

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

    well ive change my vector to unordered_set and i got Ac, thats weird!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In div1 C if we binary search on the segment tree and there are logY segments then the complexity becomes O(n*logY*logn*logn) , I came up with this solution but it should give TLE. Is there a faster way to binary search on the segment tree?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just checked, the same has already been answered in the comments!

»
8 days ago, # |
  Vote: I like it -21 Vote: I do not like it
»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Maybe the Div1 D tutorial has any problem? dp1_i=(n+1)\sum_{j=0}^i dp1_{j-1}dp1_{i-j}\binom{n-1,i-1} thx.

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

An intuitive way and short clean code to solve Div2 C2 Hard version solution hope you understand 98807026 Thank you.

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

Anyone help me find whats wrong in my submission 98818397 for problem E (div 2).Thanks in advance!!

»
8 days ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

There are some mistakes in the second paragraph of tutorial of 1439D.

$$$dp2_j\times dp1_{i-j-1}+dp2_{i-j-1}\times dp1_j$$$ should be $$$dp2_{j-1}\times dp1_{i-j}+dp2_{i-j}\times dp1_{j-1}$$$.

$$$(\binom j2+\binom{i-j}2)dp1_j\times dp1_{i-j-1}$$$ should be $$$(\binom j2+\binom{i-j+1}2)dp1_{j-1}\times dp1_{i-j}$$$.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve div2 E if the array was unsorted?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why does my code run so slow in test 4? and it even gets WA in test5! here is the code.98820613

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div1 B i dont understand how to implement the nei array . i used map and i got TLE which makes sence . however doesnt array nei have size of N * N ? doesnt it get MLE ? or if you only consider the candidates how can can you find out that there is an edge between to vertices that both are not candidates in O(1) ?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For div1A editorial

We can do this for the first n−2 cells in the row

It should be m-2 cells.

»
8 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

In the analysis of problem 1439B is it is written that

If d(u) > k, remaining vertices will form a subset that every vertex have at least k neighbors in the subset, so we'll print this subset as answer.

If d(u) = k − 1, we consider u and all neighbors of u as candidate for clique of size k. then we erase u and all edges attached to it.

So, what we do when d(u) = k? Maybe there is typo here and first condition should be d(u) ≥ k?

»
8 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Could someone explain $$$O(N\log N)$$$ solution for 1D? I came up with $$$O(N^2)$$$ solution myself (98827591), and it seems to be similar to the code in this comment, but I still don't see the way to reduce it to FFT. (the $$$(n-i)^j$$$ term is troublesome)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think shayan.p and alishahali1382 know about it

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

    I dont know the O(n.log(n)) solution but I had a O(n.log(n)^2) with FFT and divide and conquer. here dp1 and dp2 have same definitions as the editorial.

    Spoiler
»
8 days ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

My solution to

$$$C$$$

was slightly different. I divided the matrix into

$$$2 \times 2$$$

matrices. And solved it independently for each

$$$2 \times 2$$$

matrix.

  • If the matrix has 4 ones, do a flip and make it have 1 one.
  • If the matrix has 1 one, do a flip and make it have 2 ones.
  • If the matrix has 2 ones, do a flip and make it have 3 ones
  • If the matrix has 3 ones, do a flip and make it have 0 ones

Here is my code and explanation

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Div1E editorial when

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Mehrdad_Sohrabi Please provide the implementations also.

»
8 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Auto comment: topic has been updated by AliShahali1382 (previous revision, new revision, compare).

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand B's solution Sum of Medians.

Let A = [0 24 34 58 62 64 69 78]. n = 2, k = 4. Length = n * k = 8.

If you take ceil(n / 2) numbers from the end and floor(n / 2) numbers from the beginning for each group, you get this:

n = 2. ceil( 2 / 2) = ceil(1) = 1.

Pick 1 number from the end and 1 number from beginning.

Group G = [[78 , 0] , [69, 24], [64, 34], [62, 58]].

Now take median of each one and sum them up, Median = ceil( n / 2). sum = 0 + 24 + 34 + 58 = 116. This is not equal to the answer of 165.

Let's assume you sorted each group though, G = [[0, 78], [24, 69], [34, 64], [58, 62]] Sum = 78 + 69 + 64 + 62 = 273. This is still not equal to answer of 165.

How does the solution work?

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This 98841172 my solution for problem "Binary Table", I think it's easier to understand it.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

for(int msk = 0; msk < (1 << 4); msk++) { for(int j = 0; j < 4; j++) if(msk & (1 << j)) upd(n — 1, m — 1, j, 0); if(!cnt[n — 1][m — 1] && !cnt[n — 1][m] && !cnt[n][m — 1] && !cnt[n][m]) { for(int j = 0; j < 4; j++) if(msk & (1 << j)) upd(n — 1, m — 1, j, 1); break; } for(int j = 0; j < 4; j++) if(msk & (1 << j)) upd(n — 1, m — 1, j, 0); }

can anybody explain this line of code what is logic behind this code in binary table solution

»
4 days ago, # |
  Vote: I like it +20 Vote: I do not like it

Some of the problem were quite nice theoretically, but no fun at all to code. Or maybe it's just that I don't enjoy the coding as much now that I'm retired.

On problem B I got TLE despite having the intended big-O, but the unordered_map constant factor was too high. Problem C I had to spend a lot of time integrating the binary search into the segment tree structure (because just putting it on top of the segment tree adds a log factor that made it too tight). And on problem E I really enjoyed working out the maths (I didn't think I would, but it turns out to be a very nice result), but trying to compute the union of the paths that get painted black was fiddly and my solution is still suffering from time and memory limit errors.

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it
Solution for D1E