sshwyR's blog

By sshwyR, history, 4 years ago, In English

Thank you for participating, and I hope you enjoyed the problems!

1395A - Boboniu Likes to Color Balls

Idea: dqa2021

Tutorial
Solution

1395B - Boboniu Plays Chess

Idea: Xiejiadong

Tutorial
Solution

1395C - Boboniu and Bit Operations

Idea: Retired_xryjr233

Tutorial
Solution

1394A - Boboniu Chats with Du

Idea: sshwyR

Tutorial
Solution

1394B - Boboniu Walks on Graph

Idea: sshwyR

Tutorial
Solution

1394C - Boboniu and String

Idea: sshwyR

Tutorial
Solution

1394D - Boboniu and Jianghu

Idea: Z18

Tutorial
Solution

1394E - Boboniu and Banknote Collection

Idea: sshwyR

Tutorial
Solution
  • Vote: I like it
  • +204
  • Vote: I do not like it

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

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

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

I have a doubt in $$$E$$$. The question is asking us to count the number of $$$k$$$ tuples, but I noticed the example had provided a set of $$$4$$$ edges instead of $$$3$$$. Can you please clarify why $$$4$$$ edges were considered ?

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

    K is the maximum outdegree of a node. It has nothing to do with the number of edges.

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

      They have asked to count the number of $$$k$$$ tuples $$$(c_1, c_2, \dots, c_k)$$$

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

        I don't understand your doubt.

        In Example 1, the 4 blue edges are just a path that you can follow to start from 1 and end at 1.

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

In 1395A, "It is meaningless to do operation more than once because we only care about the party of $$$r, b, g, w.$$$"

I think it should be parity of $$$r, b, g, w$$$.

In 1394A, it should be "Thus they take $$$(x - 1)(d + 1) + 1$$$" days.

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

    thanks!

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

      I think this statement is not clear: " Pick a red ball, a green ball, and a blue ball and then change their color to white ". I thought that the 3 white balls are added in one operation!! But that might just be me!! Anyways, Good problems :)

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

        it doesn't matter you consider it 3 or 1 as both the numbers are odd and both of them will change the parity of the white ball

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

    In the same question, I am not able to understand why we did this fill(b + l + 1, b + n + 1, b[l]); Please help me to understand the reason behind it.

    Thanks in advance!!

»
4 years ago, # |
  Vote: I like it +170 Vote: I do not like it

Problems are really good! But pretests... rrrrrrr

»
4 years ago, # |
  Vote: I like it +130 Vote: I do not like it

Great contest ruined by bad pretests.

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

Can someone plz explain his approach for div2D/div1A. I am not able to get the editorial :(

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

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

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

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

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

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

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

A lot of people FST on Div. 1A (test case 16, 24, ..). Were these test cases intentionally made or just random?

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

    I think all the test case of D1A is random

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

      How is it possible to think that not having multitest and having only random test cases is a good idea?

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

        For me, I can not know most of your thoughts about this problem before contest, so I have no idea about strengthening test cases. It's my first time to prepare Codeforces Round and there will be some shortcomings.

        Really sorry for that.

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

          If you don't know how to make good test cases against WA then just use multitest.

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

            I do not know why people complain. Random test cases make it a bit more wild :-)

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

              There is nothing wild about it. It is just frustrating.

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

    test24 is a hack test

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The Problems are wonderful! But I think some problems should have stronger pretests (like D1A&B).

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

I m not sure about my solutin for Div. 2/C 89732880 can anyone counter or prove it?

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

Problem Div2 (D) / Div1 (A): Why is this code failing on the last test case (test case 30)? Please help!! sshwyR

»
4 years ago, # |
Rev. 4   Vote: I like it -12 Vote: I do not like it

Can someone please tell why my code for div2 C gives wrong output for sample test 3 itself, I have done brute force O(n*m).

My idea: for the minimum answer to be obtained, every 'c' should be as minimum as possible i.e (a&b) for corresponding 'c' should be minimum, that's why i have brute forced every 'b' with 'a' to get corresponding (a&b) as minimum.

int main(){
    int n,m;
    cin>>n>>m;

    int a[n];
    for(int i=0;i<n;++i)cin>>a[i];

    int b[m];
    for(int i=0;i<m;++i)cin>>b[i];

    vector<int> c;
    for(int i=0;i<n;++i){           
        int minn = INT_MAX;
        for(int j=0;j<m;++j){       
            minn = min(minn,(a[i]&b[j]));
        }
        c.push_back(minn);
    }

    int ans = 0;
    for(int i=0;i<c.size();++i){
        ans = (ans|c[i]);
    }

    cout<<ans;
}

`

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

    UPD: Yes, I didn't get him and everything below is irrelevant.

    for the minimum answer to be obtained, every 'c' should be as minimum as possible

    What can I say, but that's just the wrong way to solve it.

    For example (in binary for easier understanding), a1 = 10001, a2 = 01110 and b = 00110, you can see that a1 > a2, but (a1 & b) < (a2 & b)

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

    Try this small test case:
    $$$2$$$ $$$2$$$
    $$$15$$$ $$$6$$$
    $$$4$$$ $$$10$$$
    Your answer is $$$6$$$, but correct answer is $$$4$$$.

»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Div1B can also be solved without hashing.

The idea is that a permutation is good iff no two chosen edges point to the same vertex. If two edges point to the same vertex, then one of their origins won't loop to itself. The backwards direction is also true: if no two edges point to the same vertex, then the function that maps a vertex to its following vertex is 1-to-1, and is therefore a bijection (since the function is from a finite set to itself).

So, to test a permutation, we need to know that for all i and j, the choices i->c_i and j->c_j don't cause two edges to point to the same vertex. In this case we call the pairs {i,c_i} and {j,c_j} "conflicting".

We can find all conflicting pairs by looking at each vertex in the graph, then seeing for each incoming edge what pair would cause that edge to appear. This can be done in N* ((K*(K+1))/2)^2 time which is good enough.

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

    Actually the complexity itself is not good enough. It requires certain test case based optimisations and imo it can be hacked but I am not sure. It took me quite some time to optimise the solution to work so I'm not sure if it would work for every test case as the TL is pretty strict.

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

      My code's runtime has quite a bit of leeway and no testcase based optimizations despite being O(n * k^4), so I doubt it's hackable. I think the key is just to have simple code with good constant factor by making sure you never iterate in areas that the pair doesn't exist and don't iterate over same pair of combinations twice, and if you math it out constant factor should be p good. Feel free to prove me wrong and hack though!

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

      Hmm, maybe that's true — the true worst case is on the order of 5e8 which might pose some problems.

      However, I think the real bound is probably less than N K^4 — since the outdegrees are bounded by 9, that means the sum of the indegrees must not be too big (on average, it's also less than 9). That means at worst, we have N/5 vertices with indegree 45, so it's already 5 times faster than the original calculation.

      Similarly, the recursive step can bail out early a lot of the time, and not check every permutation.

      It would be interesting to see if there can be really bad test cases that will make it fail though.

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

        The recursive step requires only k! if done correctly using bitmasking. I have inspected SuperJ6 code and have come to the conclusion that even if the complexity seems to be NK^4, but it is not the case. The complexity comes out to be N*KC4 if coded correctly which easily fits in the TL. The complexity and worst case of my code however is still in question as I have applied slightly random method to improve upon the worst case.

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

          Uh O(n * kC4) is equivalent to O(n * k^4), though referring to it as that does show why it fits in time limit more clearly. This is what I mean by if you never check same combination twice constant factor is good when you math it out (which I see you did orz).

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

    Actually, there is an implementation which won't need $$$ N * K ^ 4 $$$ time. We find the reverse graph and for each edge that comes into a node find the pair $$$(i, c_i)$$$ it corresponds to. There can only be $$$O(K^2)$$$ edges at max for a particular node. Calculating the invalid pairs for this node will obviously take $$$O(K^4)$$$. But the fun fact is, $$$ \sum_{i=1}^N E_i = M$$$ , where $$$E_i$$$ is the count of edges coming into node $$$i$$$. So, the amortized time will actually be $$$O(M*K^2)$$$.

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

    why K^4 ? it can be done in O(N*K^2), my code

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

      Or, more precisely, it's O(N*K^2/64) since the extra K^2 factor comes from the bitmask optimization :D

      Interestingly, our solution performance times are not that far off, so there weren't any stressful test cases (or maybe the bottleneck was always the permutation bruteforce).

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

      Can you briefly explain your idea? Sorry I wasn't able to clearly understand your code.

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

        it's basically the same as Svlad_Cjelli's solution (see his original comment) but I use bitmasks to reduce the complexity, the number of choices of $$$c_d$$$ is $$$d$$$ so in worst case we have $$$\frac{K*(K+1)}{2} = 45$$$ choices when $$$K = 9$$$, so instead of using hashes or sets, I use bits stored in long longs, I maintain for each $$$(d, c_d)$$$ a mask of bad choices (choices that can't happen if I choose $$$(d, c_d)$$$) called hate, in the backtracking step I maintain a mask called forbidden and to update it I or it with the value of hate[the current choice] and never use a choice that is in the forbidden mask or that invalidates itself

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

          Thanks a lot! I am relatively new to bitmasks so I had difficulties of understanding, thank you for the clear explanation.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I did reverse of approach given for Div2D. First I calculated sum for all small items and found how many remaining days we have for big items. Then everytime we take minimum of small item we check if we can add big item with given number of days left. Print maximum for all those cases.

Submission

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

    Why are you adding negative of small items to mn pq and subtracting from the sum?

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

      For smaller items, we need to take minimum at each step but CPP priority_queue is max heap by default. So we add negative values to use it as min heap.

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

I have a better approach for Div 2 C.For each a[i],find the minimum value of c[i].Then find the maximum among all the c[i].Now brute force this maxi with all possible a[i]*b[j] to get the ans. Time complexity(O(n*m)). Link to my submission:- https://codeforces.net/contest/1395/submission/89722222. Think a little bit and you will get why it works.

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

    hi could you please explain why you ORed maxi with x in your last loop? thanks!

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

      By now,I know that one among c[i..n] is maxi.So I checked that for a particular i, for which value of a[i]&b[j],the OR with maxi comes out to be minimum.That's it.

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

    Your solution is flawed and only works because of weak test cases. A hack was submitted against it. Try submitting the same code again.

    Or try case:

    54 12

    435 115 422 469 19 176 292 395 273 217 160 343 277 500 124 360 315 59 2 477 465 138 175 392 146 438 4 96 231 182 257 183 51 117 430 125 167 107 238 66 236 96 319 62 365 186 83 414 166 198 224 129 60 195 327 62 310 278 300 228 295 113 502 320 463 223

    You will get 63, while the correct answer is 62

    (Case created by GlobalElite)

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

      can u explain why his method is wrong? why the solution is incorrect?

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

        I don't know. I just tried the same logic and it failed. So I thought I would tell him too.

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

      Yah I got it bro.Thanks for the test case.It also fails for the this test case also:- 3 2 3 10 128 130 137.

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

        Nice test case, but in both hack test cases, the expected answer and the participant's answer differs by 1 :/. Is it just a coincidence or there's some logic behind it? UPD: i got it, it was a mere coincidence

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

        Any idea why it fails bro?

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

          Yes. Take the test case

          2 2 10 7 13 6

          Here if you take the bitwise and between ai & bj with a bruteforce you get the following matrix(candidates for c1 and c2) {8,2} {5,6} this code chooses {2,5}, so my code here chooses 5 as it maximum and in first case compares 5|8 which is greater than 5|2 so 5|2(7) is printed. But, if u look carefully u can choose c1 as 2 and c2 as 6 and get 6 as the answer. So, this greedy solution is completely flawed.

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

sshwyR For Div 1 E, where are key points 2 and 3 proven?

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

    The formal proof will be too verbose so I'm trying to explain it intuitively using pictures and examples

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

    For key point 2, basically, we can use "change blue to red" skill (picture in S 1.2) to prove that, for two different folding methods A and B resulting in the same sequence, we can do "change blue to red" several times to make A equal to B.

    key point 3 is obvious, beacuse the method it discribed leads to alternate mountain and valley folds. So each fold contains exactly one layer of paper.

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

      For key point 2, aren't we trying to show that "all folding methods result in the same sequence," not "given two folding methods that result in the same sequence, we can convert one to the other"?

      Also, I don't see why it is obvious that the method produces alternating mountain and valley folds.

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

        Specifically,we trying to show that "all folding methods, which don't have any more available folds, result in the same sequence".

        And yes, we can convert one to the other.

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

        For example, in this picture, the first method is physically not correct because you may damage the paper to make it.

        But the second one is physically correct, and also the result of both are the same. Thus we don't care about how you fold -- even it is physically not correct. Because you can always trasform it to be physically correct. And alternating mountain and valley folds is always physically correct. Thus we say the method produces alternating mountain and valley folds, it actually means we don't need to care about whether it's mountain or valley.

        We just care about the position of fold marks

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

          Yes, I see why you can convert one to the other. But I still don't see how this relates to "all folding methods, which don't have any more available folds, result in the same sequence."

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

            Maybe we can use proof by contradiction. Suppose method A results in a[l1,r1] and method B results in a[l2,r2] and we can prove that one (or both) of them has more available folds

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

              I still don't know why "all folding methods, which don't have any more available folds, result in the same sequence."

              By the way, I think you were just proving key point 1 in the previous messages. Isn't "We just care about the position of fold marks" key point 1?

              The sentence "For key point 2, basically, we can use "change blue to red" skill (picture in S 1.2) to prove that, for two different folding methods A and B resulting in the same sequence, we can do "change blue to red" several times to make A equal to B." is also to prove key point 1, although you start it with "For key point 2,".

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

Can anyone tell why my code of Div-2 D is giving RE on testcase 3

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

A should have less than or equal to, not just less than

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

Can anyone explain why we check that A[i] & B[j] | A == A for problem C?

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

    None of c1,c2,c3...cn can have any bit set that's not set in the result, because of the OR operation. Hence if we can find a ci = Ai&Bj whose set bits are a subset of the result's set bits then we are good with the ith value in the size n array. Hence, this line.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Div2. C can be solved in $$$9 * n^2$$$ by greedily eliminating possible values for every i. https://codeforces.net/contest/1395/submission/89696347

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

    you can also solve with sort of minimum for each a[i] https://codeforces.net/contest/1395/submission/89690151

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

      This solution is wrong UPD: Hacked

      test case
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

look at this solution for c https://codeforces.net/contest/1395/submission/89690151 why is it works?

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

Can Anyone Share A dp solution for Div-2 D ?

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

    i have only prev solutoin((

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

      No I'm looking for some other approach :p

      My Idea was to store the number of items of $$$type1$$$ and $$$type2$$$ ( Where $$$type1$$$ are the types for items which are greater then m and $$$type2$$$ for less.) and transitons based on their corresponding values using prefix-sums.

      However I'm get WA5 and would be nice to hear some similar (or other?) $$$DP$$$ approach.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can Someone please elaborate the 1394C problem. Plz explain what this part is doing Check(ans^(1<<i))?ans^=(1<<i):0;

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Can someone explain the logic behind to find the point $$$(x_{t}, y_{t})$$$ when the radius $$$r$$$ is fixed, in the problem 1394C?

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I enjoyed the problems :)

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

In Div2C, we can have $$$O(9nm)$$$ time with $$$O(nm)$$$ additional memory.

  1. First, let $$$s_i$$$ be a copy of $$$b$$$ for each $$$i$$$ -- that's the values in $$$b$$$ that we can still use for this $$$i$$$.
  2. Now let's iterate bits $$$b$$$ from 8 down to 0:
  • for every $$$i$$$ try to choose such an item from $$$x \in s_i$$$ that $$$a_i \land x$$$ does not have bit $$$b$$$ set;
  • if we can do this for every $$$i$$$, then we remove from all $$$s_i$$$ all values that have bit $$$b$$$ set;
  • otherwise, we set bit $$$b$$$ in the answer.

Submission

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

    I did the same (although couldn't submit during contest). And Rank 1 fellow also did the same way. I liked how he/she used ok[][] matrix instead of set to take care of adding and removing number :D

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

Can someone explain the solution of Div 1-B with hashing?

I solved it (although after the contest), but without hashing and I have no idea what hashing has to do with it.

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

    If you assign a random integer to every element in a set, then for any subset you can compute the sum (or other associative operation — for example xor), Then if two subsets are different, they are highly unlikely to have the same hash value. That is much faster than comparing the sets directly.

    In this problem for each assignment i -> c[i], you can figure out the set of vertices pointed to under that assignment. An array c is good if all those sets cover {1,...,N}.

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

      Ok, thanks.
      So with hashing solution we check with a hash that each vertex has exactly one incoming edge.
      While with normal solution we check that each vertex has no more than one incoming (from which it follows that there is exactly one) edge, by computing rule (i->c[i]) incompatibility matrix.

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

Can someone help me solve div2C with DP? By the way, let's see what's wrong with me. https://codeforces.ml/contest/1395/submission/89746733

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

    Here's my code using DP approach, I commented it a little bit but if you have any doubt, just ask me :)

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

      can you tell your approach? UPD: I figured it out. But you may write if you want.

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

      can u tell me what's wrong with my transition function ??89813834

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

        I'm sorry but i don't get what are you saving in dp[i][j] and ae[i][j], can you explain it a little bit?

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

For 1394A, how is the starting value of i in the code ( (k + d)/(d + 1) ) determined? I don't understand what it does.

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

Could someone help me please with Div2-D? Can't understand why my submission fails on test 6 https://codeforces.net/contest/1395/submission/89750243

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

Can someone show me how to do the condition test in Div1/C Div2/F. I mean, how can we do binary search on two coordinates x and y?

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

Tutorial for Div2 C is great , but is there any other non brute force approach ?

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

Banging my head because solution of Div2/C turned out to be way simpler than I thought

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

Why DFS does not work for problem B??

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

Problem B: Can any one tell me whats wrong in my code?

My code

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

    Initial position is wrong in your solution. I mean that first move should always be at square sx,sy as it is given in question that initially it is at square sx,sy.

    So initially you are at (sx,sy). So first square will be this,then cover squares in that column or row. Then move to (1,1) and cover rest rows/columns in a sequential manner.

    Hope you got the point.

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

I didn't got editorial solution for div2 C.

can anyone explain in some clear way with some example??

Please!!

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

Can someone please explain why I am getting wrong answer on test 5 of Div 2D. Here is the link to my code:- My submission

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

    The big ones are placed on first day, then after d days, and one as last element.

    For this last element we need to check if we used small elements at all, and if one big element is available. I think these checks are not correct in your code.

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

      Can you provide some test case as well. I still didn't get what's wrong with my logic.

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

      Now I get what you are saying. Thanks for your help. I found my mistake now.

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

Hi sshwyR, in the problem div1-C how to prove that the function in xOy is unimodal?

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

    The sum of unimodal function is still unimodal. This is the key to prove it :)

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

      The sum of two sharp peaks that are far away from each other is a function with two sharp peaks, which isn't unimodal.

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

        please consider the function in this problem instead of any unimodal function

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

          Okay, but the question was how to prove that this function is unimodal. We can't use a statement that isn't always correct to prove it and we can't use the fact itself to prove itself either.

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

            The first thing is to prove $$$dist$$$ is unimodal on a line. Take x axis for example, any other line can be rotated and shifted to be it.

            Let's say $$$f(x) = dist((x,0),(X,Y))$$$ where $$$(X,Y)$$$ is fixed. Thus it is obvious that $$$f(x)$$$ is unimodal.

            Well, let's say $$$f_2(x) = dist((x,0),(X_1,Y_1)) + dist((x,0),(X_2,Y_2))$$$ where $$$(X_1,Y_1)$$$ and $$$(X_2,Y_2)$$$ are both fixed. Thus we can prove that $$$f_2(x)$$$ is still unimodal.

            Thus for $$$g(x) = \sum dist((x,0),s_i)$$$, we can also prove that $$$g(x)$$$ is unimodal.

            Notices that this proof can apply to any line.

            Thus for any line, $$$g$$$ is unimodal.

            So we get the final part: the function in xOy is unimodal. you can use reduction to absurdity.

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

    Were you or anyone else was able to prove that the function in xOy is unimodal? I'm still struggling to prove it.

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

      u can read my reply to Xellos :)

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

Can someone please tell me what I'm doing wrong in my Div2D submission? The idea is to enumerate all the possible combinations of numbers which are bigger than m and calculate the result with prefix sum. Code: https://codeforces.net/contest/1395/submission/89766414.

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

    If I understood correctly from your code that you are only considering the case of, if you take k big values then you have to cover k*d days. Which is not always true. You can also take k big values but with (k-1)*d days and placing the remaining one big value in the nth position, which will not cover d days. For better understanding you can see my code. Hope that helps. code

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

      In the code I'm trying to cover that case with if(space >= d) space -= d; (i.e. whenever we can put one big value in last position, we put it).

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

Can someone please explain the second problem 1395B — Boboniu Plays Chess I am unable to understand the editorial as to how the formula for f(i,j) is getting derived?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If you know rook move its so easy.. 
    1.from your 1st position 1st go all of position of that row..
    2 then check all row from up to down..if you in the left then start from left and next you must be in right and start from right.next again left next right.continue the process until all row complete...
    
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

How to check if there is a hexagon cover all points on a fixed radius?

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

Can C be solved without explicitly checking all the possible values?

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

Can someone suggest some good blog or video to understand the execution of hashing used in div 2 e/ div 1 b 1394B — Boboniu Walks on Graph.....I understand the idea I just need to understand the implementation.....

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

For Div-1 C if the function is unimodal can we use ternary search over x's that is number of B's in the final answer to solve it?

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

    I think simple ternary search over the number of Bs and Ns is not an intended solution. I upsolved it with simple ternary search with some optimizations, but it was barely within the time limit. It might just be because my code is badly written though. If you're interested anyway, here's my submission.

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

      Should ternary search work for this problem?

      let f(x,y) be the distance if answer string has x B's and y N's.

      let g(x) = min(f(x,y))

      If we consider a string s = "BBN".

      for x = 1. g(1) = 1, as we can add BN to the end of the string B

      for x = 2, g(2) = 1, as we can add N to the end of the string BB

      In this case g(x) = g(x+1), doesn't ternary search fail if there are equal values.

      I was trying to write a soln based on ternary search but got WA 90523331

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

        You might be getting WA because you're comparing values right next to each other. I can't think of any other explanation. For example in classic ternary search you investigate the points $$$mid1 = (2 * lo + hi) / 3$$$ and $$$mid2 = (lo + 2 * hi) / 3$$$. These points are far away enough to work well (in this problem at least). In your case the values have a high probability of being the same, since you are investigating points that are very close to each other, and if they are equal you always move $$$lo$$$ to $$$mid$$$, although the optimal point may be to the left of $$$lo$$$. Do correct me if I'm wrong about anything I said though, I'm not exactly an expert on ternary search or unimodal functions.

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

          Yeah, this might be the issue with my solution. You are right, my ternary search won't work in this case.

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

can anyone please explain DIV2B?? I am unable to understand the tutorial.

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

    You could give some hint on which part you did understand, and which not.

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

I have a question about Div. 1-A.

Does anybody know why in the tutorial they are filling the array of the smaller elements with the last value as if there were more small elements?

I have made two submissions 89774711 and 89774745. The only difference between them is that in the second one I have commented out line 96 which is equivalent to the fill call in the tutorial. And the way I see it by adding those values to the end of the prefix sum we would be considering cases that are not valid because they have too many small elements.

Can anybody please explain this to me?

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

    It an array of prefix sums. Ie setting the elements all same is like adding zero elements to the end of the set of smaller elements.

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

      Thanks!!

      I was trying to argue back but thinking of it as adding zeroes made me understand why it works.Just in case anybody has the same doubt I'll elaborate on why I got confused with this:

      5 2 10
      11 11 8 8 8
      

      For this testcase, the best I had been able to find was 11 8 8 8 11. But it turns out 8 8 8 11 11 is better.

      However if you don't add the zeroes you won't find the second one since the code (at least mine) expects two days of being muzzled after each big number but that is not always the case.

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

        I also had a similar problem, which resulted in the out of bounds of the smallSum elements. I think the reason why we fill the array with some elements (I think they are zeros) is not to reach out of bounds --> avoid this case wisely by the addition of the elements. However, I found an alternate solution rather than filling the array which is taking minof (smallSum.size(), n — 1LL * (i — 1) * (d + 1) — 1). It handles the case efficiently without any operations.

        WA submission : 90204055 AC submission : 90206949

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

          Thanks ,got it why they fill with last elements with same number

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

How to solve Div. 2B (Bononiu Plays Chess) if a rook when travelling from (X1 Y1) to (X2 Y2) also travels all squares between the two points? (that is unlike the problem, you cannot "lift" the rook.

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

    I think then we should go in spiral but there will be some cases when we can not fill it in any combination

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

      yes I was thinking it involves Euler Trials, wanted a rigorous solution or atleast ideas for one..

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Were the test cases hard to prepare for div1B? How did you go about it? Also, is there any test case where both (a). for any out degree from 1 to k, there is at least one vertex having that out degree; and (b). the answer is big (i.e. > 1000, say); hold? I can't think of any test case like this, but I find it a relevant question: If there are only a few solutions, some more permissive heuristics + brut-force check would also solve the problem.

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

How to solve Div2C using dp?

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

I know it is apparent but still, Div2 E doesn't mention clearly that array c should be a permutation of 1,2...k so someone could mistake it by using repeated values in c.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can somebody explain div2 C? The editorial is confusing.

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

    The editorial is confusing

    It is

    All numbers are up to 511 so there are only 512 (from 0 to 511) possible answers. You can just check all of them from 0 to 511 (because we need the minimum we check from lowest to biggest). Check each guess directly, without any optimizations (~ n*m operations) — I believe you'll figure out this part.

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

I just finished Div 1-C and after reading the editorial, I may say that the proposed solutions are strange: hashing for 'B', Hill Climbing Algorithm for 'C'...

»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

for C , when distance is fixed (say d), we have to check whether every region has a common point. Each hexagon can be described as (lx<=x<=rc) and (ly<=y<=ry) and (lxy <= x-y <= rxy). So for each dimension we can easily get a common interval, and the common area is also of that form. Then we can check in O(1) time.

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

I know that editorial for Div1C mentioned the randomized solution because it was considered to be simpler than binary searching + checking one. But here I want to discuss the later solution with brute force instead of binary search, which is actually simple to implement.

The core idea of this solution that we need to find $$$x_t, y_t$$$ and $$$r$$$ such that the hexagon covered all the points. To make this simpler, let's project all the points onto 3 axes: $$$Ox, Oy$$$ and the line $$$y = -x$$$. I do claim that hexagon can cover all the points iff we project the hexagon onto these 3 axes, the ranges made by the hexagon also cover the projections of the points. I don't have formal proof yet, but this is intuitively true. Feel free to share it if you guys have one.

Now we can fix either $$$x_t$$$ or $$$y_t$$$ and find the other one. But I like to fix $$$y_t - x_t = diff$$$, i.e the projection (or 2 times the projection) of $$$(x_t, y_t)$$$ onto $$$y = -x$$$, and find the coordinates. Firstly, we can find minimum $$$r$$$ for covering the points on the axis $$$y = -x$$$. Secondly, since we have known $$$diff$$$, we can actually combine projection on $$$Ox$$$ and $$$Oy$$$ into one: we keep all projections on $$$Oy$$$ the same, and add $$$diff$$$ to every projections on $$$Ox$$$. Sound like $$$O(n)$$$, but we don't care about the points, only the endpoints of the range made by projection, so this is instead $$$O(1)$$$. After that, we got a big range of projections, and the middle points is the optimal one. The optimal $$$r$$$ is the minimum of $$$r$$$ for $$$y = -x$$$ and $$$r$$$ for the combined axis.

Finally we brute force $$$diff$$$. Since $$$0 \le x, y \le 5\times 10^5$$$, the range for $$$diff$$$ is not that big. Hence complexity is $$$O(\max |S|)$$$.

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

    I do claim that hexagon can cover all the points iff we project the hexagon onto these 3 axes, the ranges made by the hexagon also cover the projections of the points

    That is indeed true,
    because hexagon = intersection of square with "infinite diagonal slice".
    And in general:
    if C = intersection of A and B
    then P is in C <=> P is in A and P is in B
    (by definition of intersection)

    Although I didn't understand your solution. Can you link to your submission?

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

    Hi, I was unable to understand how you combined projection on Ox and Oy, why adding diff to every projection on Ox and keeping Oy same will combine the two range of projections. Can you help? Thanks!

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

      As I said before we can either fix $$$x$$$ and find $$$y$$$, or fix $$$y$$$ and find $$$x$$$. But I don't like that so I fix $$$diff = y - x$$$. And because of that, we also have $$$y = diff + x$$$. So yeah, we can project all the points from $$$Ox$$$ onto $$$Oy$$$ simply by adding $$$diff$$$.

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

    Thanks, I found your solution much easier to follow and understand. I felt like the editorial one was missing a lot of details that are not necessarily trivial.

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I found A somewhat tricky for A and found B harder than C or D. In C and D, I knew approximately what to do — what exactly and how to do it were mostly details. Also, all my solutions were deterministic and those hashing solutions are way too risky, especially in C compared to binsearch + checking 6 nice types of inequalities.

My solution to div1B is based on rewriting the rule for "at most 1 incoming edge to each vertex" to forbidden equalities and pairs of equalities "$$$c_x=y$$$" and then the rule for "at least 1 incoming edge to each vertex" into "if we choose $$$c_x=y$$$, how many edges do we add?", where we want exactly $$$N$$$ edges in total. There are $$$O(K^4)$$$ pairs of equalities, which gives $$$O((K+4)!)$$$ time complexity, but the constant in it is nice and the checks are simple enough that it's very fast. Still, miss one idea and you can be stuck with what ends up as just $$$O(NK!)$$$ heuristic.

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

What! Div2 C was that easy. I wasted 1 hour over complicating such an easy problem!!

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

Div2 problem C Can anyone explain, why if answer is A, then for all i (1<=i<=n) ci | A is A?

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

    Let a|b = k and consider a = 100110 and b = 111001 now a|b = 111111, if you check the condition then it hold up. This is occurring because k will be greater than both a and b and there is no possibility remain that a bit in k is 0 while it is 1 in either of a and b. Hope it helps

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

Please anyone help me understand the div2D/div1A solution

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

Problem div2D/div1A is one of the Prettiest Greedy Problems I've seen so far!

Honestly, I gave up on it 30 minutes before the contest, but just Love the Problem.

My Attempt to Problem D

My Submission

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

    But instead of muzzling the remaining big numbers shouldn't we muzzle the small numbers instead?

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

      Not Always.

      Assume a case where n=12, d=4, m=20

      big [ 23 22 21]

      small [19 19 19 19 19 19 19 19 19 ]

      Here we take the first big number 23 and keep it at the end of Permutation. No Problem.

      Now if you take the number 22, you have to muzzle 4 small numbers, resulting in losing 19+19+19+19=76 for 22. Not a good option.

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

For anyone interested, I implemented it based on satashun comment in $$$log(maxDist)$$$, where $$$maxDist$$$ is the maximum distance between any two strings ($$$+ O(n)$$$ for reading the data).

https://codeforces.net/contest/1394/submission/89813839

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

Hey, Isn't the solution given for Div2/C of complexity $$$O(9nm)$$$?

The for loop in main() runs only 9 times.

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

    When using the big-oh notation, O(c ⋅ f(x)) (where c is a constant) is the same as O(f(x)).

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Do you guys call "tutorial" of B a tutorial? I would see the same information about this problem in others code.

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

Here are my video solutions for all div. 2 problems (A-F, A-C for div. 1). Sorry that they're a bit late, I was mostly grappling with trying to upsolve 1C (unsuccessfully).

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

I guess there might be a solution of Div2 C with the a complexity of $$$\mathcal O(n^2 \log a)$$$ instead of $$$\mathcal(n^2 a)$$$ in tutorial.
enumerate bits from the highiest bit to see whether each $$$a_i$$$ has a $$$b_j$$$ satisfies $$$a_i \verb'&' b_j$$$ is $$$0$$$ in the current bit. If so, mark every $$$b_j$$$ of $$$a_i$$$ where $$$b_j \verb'&' a_i$$$ is $$$1$$$ in the current bit in a two-dimensional array to show that that $$$b_j$$$ is not good for $$$a_i$$$. And we wouldn't consider that $$$b_j$$$ in the following bits of $$$a_i$$$. If not, add $$$1$$$ to the current bit of the ans.
https://codeforces.net/contest/1395/submission/89796424

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

Errata: Example 2 in 1E should be [1,1,−1,1,−1,−1,1,1,-1], the last element is wrong.

I think?

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

Can anyone explain why the red case in 1E 4.3 Key point 4 is neccessary true? I can se it for the other two cases but not that one.

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

During the system test, I got WA41 in task B. When I submitted the same code, but after the final results, I received an OK verdict, while I checked my code on test 41 using my checker and the answer turned out to be correct. Can someone explain the reason for UB in my code?

Wrong answer: 89685485
Accepted: 89846084

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

For div1B , can anyone please discuss about the probability of collisions?

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

Editorial to the problem D1A/D2D is not clear. Can someone please explain the approach clearly?

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

Bobonui Chats with Du: I feel like instead of writing (x-1)(d+1) + 1 for big items, if we write (x-1)d+x then it will make more sense and intuitive.1394A - Boboniu Chats with Du

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

I have a submit for Div1E and it may O(nlog^2n). I write a Chinese explain for it.

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

sshwyR SecondThread Monogon — Since this post is ~ 2 months old, hence tagging few members. Please don't mind.

Can someone please explain the hashing part in Div2E? I understand that we want to compare the union of sets to {1, 2, 3, ..., n} using hashing e.g. union of {1, 2, 4} and {3, 5, 6} is equal to {1, 2, 3, 4, 5, 6}

I tried hash as product modulo prime but I got an error on 8th test case and I realized that this is not a good way to hash because it can generate same hash for distinct sets

Is there any blog/tutorial that I can follow to understand this? Any help will be appreciated

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

    you may use multihash with random value, like val[i] in the solution :)

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

Nice solution. In Div1B, as you mentioned, we can use many functions h(T) for an integer set T, like \pi or \sigma mod(-ed), or even XOR; but I tested AND and OR operator, they were not strong enough. Also, the idea of creating val[x] randomly is smart, without it, none of the function is strong enough to pass the tests.