sshwyR's blog

By sshwyR, history, 3 months ago, In English

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

1395A - Boboniu Likes to Color Balls

Idea: dqa2020

Tutorial
Solution

1395B - Boboniu Plays Chess

Idea: Xiejiadong

Tutorial
Solution

1395C - Boboniu and Bit Operations

Idea: 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: ZZZZZZZZZZZZZZZZZZ

Tutorial
Solution

1394E - Boboniu and Banknote Collection

Idea: sshwyR

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

»
3 months 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).

»
3 months 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 ?

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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)$$$

      • »
        »
        »
        »
        3 months 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.

»
3 months 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.

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

    thanks!

    • »
      »
      »
      3 months 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 :)

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

        even i considered it to be 3

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

        i ALSO considered it to be 3

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

        you thought correctly. It indeed mean that 3 white balls are added.

      • »
        »
        »
        »
        3 months 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

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

        I got WA just because of that line.

»
3 months ago, # |
  Vote: I like it +170 Vote: I do not like it

Problems are really good! But pretests... rrrrrrr

»
3 months ago, # |
  Vote: I like it +130 Vote: I do not like it

Great contest ruined by bad pretests.

»
3 months 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 :(

»
3 months 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).

»
3 months 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).

»
3 months 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).

»
3 months 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?

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

    I think all the test case of D1A is random

    • »
      »
      »
      3 months 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?

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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.

          • »
            »
            »
            »
            »
            »
            3 months 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 :-)

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

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

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

    test24 is a hack test

»
3 months 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).

»
3 months 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?

»
3 months 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

»
3 months 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;
}

`

  • »
    »
    3 months 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)

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

      You didn't get me, your example is irrevelant.

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

      here i mean, by performing OR operation b/w two integers, we can never get the answer less than the maximum of the chosen two integers. So when we are doing c1|c2|c3.... we can never get the answer less than the max(c1,c2,c3....) which is why we should try to have each 'ci' as minimum as possible, so that the final answer will be minimum. Now for each 'ci' to be minimum we must have corresponding (ai&bj) minimum , to get that we check every b with ai and then select that (ai&b) which is minimum

      UPD : My logic is wrong , In the above i was right till max(c1,c2,c3....) part. Every 'c' being small may not help always. Eg: (provided by pavlovoleg4889) 4|4 = 4 but 4|2 = 6

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

        OMG I am relieved to understand why its wrong because I was also thinking like this

  • »
    »
    3 months 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$$$.

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

      Thank you so much brother for the test case, now I understand where i went wrong :)

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

        bro can u help in this..i was also doing in the same fashion as u were doing

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

          Let's say we have choice to choose c1 and c2 from set {2, 4, 4, 6}. Our code chooses c1 = 2 and c2 = 4 thinking minimum c's give minimum answer, hence we print 2|4 = 6 as the answer. But but the right thing to do is to choosec1=4 and c2 = 4 so that the answer is 4|4 = 4 . And it is clear that we were wrong initially because 4 < 6

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      Can you please me with this solution ..... failing on third case...


      #include<bits/stdc++.h> using namespace std; #define int long long int f[9]; int solvebit(vector<int>& b,int bit,int ans,int n) { if(bit==-1)return ans; if(f[bit]==0)return solvebit(b,bit-1,2*ans,n); vector<int> zeroes; for(int i:b) { if((i>>bit)&1)continue; else zeroes.push_back(i); } if(zeroes.size()>0)return solvebit(zeroes,bit-1,2*ans,n); return solvebit(b,bit-1,(2*ans)+1,n); } signed main() { int n,m; cin>>n>>m; int a[n]; vector<int> b(m); for(int i=0;i<n;i++){cin>>a[i];} for(int i=0;i<m;i++){cin>>b[i];} for(int j=0;j<n;j++) { for(int i=0;i<9;i++) { if((a[j]>>i)&1)f[i]++; } } int ans=0; cout<<solvebit(b,8,ans,n)<<endl; return 0; }
  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Problem B For some reason, brute force does not give the minimum answer. Just look at the example case...

    case:1               
           cx =   00010         
           c2 =   10101       
      cx | c2 =   10111    
    
            case:2
           cy = 10000
           c2 = 10101
      cy | c2 = 10101

    cx is smaller than cy, but after the or operation, cy gives a smaller result. In brute force, we are always choosing the smaller value for c.

    I apologize if I am unclear.

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

      Check the above replies...you'll understand

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

i am not able to understand 1395 B please help me

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

    You already underestand? U must visit all the cells, you can "jump" in the same row or in the same column doesnt matter the order

»
3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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!

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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).

  • »
    »
    3 months 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)$$$.

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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).

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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.

»
3 months 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

  • »
    »
    3 months 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?

    • »
      »
      »
      3 months 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.

»
3 months 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.com/contest/1395/submission/89722222. Think a little bit and you will get why it works.

  • »
    »
    3 months 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!

    • »
      »
      »
      3 months 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.

  • »
    »
    3 months 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)

    • »
      »
      »
      3 months 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?

      • »
        »
        »
        »
        3 months 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.

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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

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

        Any idea why it fails bro?

        • »
          »
          »
          »
          »
          3 months 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.

»
3 months 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?

  • »
    »
    3 months 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

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

      • »
        »
        »
        »
        3 months 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

        • »
          »
          »
          »
          »
          3 months 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."

          • »
            »
            »
            »
            »
            »
            3 months 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 months 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

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

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

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

    Thank you :)

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

      could u plz explain me just this one line in brief..why all shuld be equal to A?

»
3 months 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?

  • »
    »
    3 months 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.

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

    because A[i]&B[j] can be substituted for C[i]

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

Can anyone explain Div2 C?Didn't understand the Editorial.

»
3 months 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.com/contest/1395/submission/89696347

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

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

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

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

»
3 months 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;

»
3 months 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?

»
3 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I enjoyed the problems :)

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

Can someone please explain the dp solution to Div 2C ?

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

    I wrote the following DP solution to Div 2C which is giving wrong output on sample 3. Can someone please help me why is this wrong?

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

    dp[i][v] is the best result if you reach index i with value v.

    code
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
3 months 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

  • »
    »
    3 months 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

»
3 months 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.

  • »
    »
    3 months 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}.

    • »
      »
      »
      3 months 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.

»
3 months 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

  • »
    »
    3 months 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 :)

    • »
      »
      »
      3 months 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.

    • »
      »
      »
      3 months 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

      • »
        »
        »
        »
        3 months 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?

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

          dp[i][j] stores pair wise and values ith in 1st array jth in 2nd array

          ae[i][j] builds the solution upto ith index optimum answer if ya use jth value in latter array

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

Hey, can anyone help me out with what is wrong in my code (Div2D/Div1A)? Can't seem to understand as to what should I do?

»
3 months 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.

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

    Those are the minimum no of funFactors(of type-1) which can be added to the answer,this case is when all the type-1 funFactors are consecutive.

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

i dont get how this works in div2 C (ai&bj)|A=A ? Any help ?

»
3 months 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.com/contest/1395/submission/89750243

»
3 months 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?

»
3 months 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 ?

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

    Yes of course. In fact $$$9n^2$$$ is easy too, and I think there should be a $$$n\log^2$$$ solution.

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

:v

»
3 months 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

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

    Hi SevenDeadlySins, Can you let me know what's wrong with my approach? I am using the properties of & and| OR of two numbers is greater than or equal to the maximum of those two numbers. AND of two numbers is less than or equal to the minimum of those two numbers. so if I do AND of a[i] and the smallest element of B then I will essentially minimize each element of C. And this way we can minimize the OR of all elements of c

    Thanks a lot :)

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

      Nevermind, I understood what the issue was :)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        @Code_M I tried your approach, but got wrong answer. I didn't get the issue yet. Can you please help me by explaining what the issue is ??

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

In the 1395A, in the solution part,in the elif statement it should be "check(r-1,g-1,b-1,w+3)"

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

Why DFS does not work for problem B??

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

This is my code for Div2A can someone pls tell me what is wrong in this logic .89736361

»
3 months 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

  • »
    »
    3 months 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.

»
3 months 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!!

»
3 months 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

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

    • »
      »
      »
      3 months 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.

»
3 months 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?

  • »
    »
    3 months 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 :)

    • »
      »
      »
      3 months 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.

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

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

        • »
          »
          »
          »
          »
          3 months 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.

          • »
            »
            »
            »
            »
            »
            3 months 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.

  • »
    »
    3 months 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.

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

      u can read my reply to Xellos :)

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

can someone tell me how the complexity of div2 problem c is O(2^9*n*m). We run a loop from i=8 to 0, then the complexity should be O(9*n*m) as what I think. Please correct me because I know I am wrong but don't know where I misses out....

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

Can anyone tell why dfs traversal is not working for Div2B problem. My solution https://codeforces.com/contest/1395/submission/89697375

»
3 months 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.com/contest/1395/submission/89766414.

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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).

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it
        Consider this case:
        8 3 19	
        30 20 20 20 19 19 25 20
        AC output: 93
        Your output: 75
        

        In this case you have to put the last element in the (n-1)th position which will cover 1 day instead of 0 day which is optimal in this case.

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

Need help with DIV 2D...fails on TC 16

»
3 months 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?

  • »
    »
    3 months 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...
    
»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

DIV2 C Can someone help me with this ,it is not passing 3rd pretest

#include<bits/stdc++.h>
 using namespace std;
 #define int long long
map<int,int> dp;
 int f[9];
 
 int solvebit(vector<int>& b,int bit,int ans,int n)
 {
     if(bit==-1)return ans;
     if(f[bit]==0)return solvebit(b,bit-1,2*ans,n);
     vector<int> zeroes;
     for(int i:b)
     {
         if((i>>bit)&1)continue;
         else zeroes.push_back(i);
     }
     if(zeroes.size()>0)return solvebit(zeroes,bit-1,2*ans,n);
     return solvebit(b,bit-1,(2*ans)+1,n);
 }
signed main()
{
        int n,m;
        cin>>n>>m;
        int a[n];
        vector<int> b(m);
        for(int i=0;i<n;i++){cin>>a[i];}
        for(int i=0;i<m;i++){cin>>b[i];}
        for(int j=0;j<n;j++)
        {
            for(int i=0;i<9;i++)
           {
                 if((a[j]>>i)&1)f[i]++;
           }
        }
        int ans=0;
        cout<<solvebit(b,8,ans,n)<<endl;



return 0;
}

»
3 months 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?

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
3 months 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.....

»
3 months 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?

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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.

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

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

  • »
    »
    3 months 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.

»
3 months 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?

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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 months 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.

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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..

»
3 months 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.

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

How to solve Div2C using dp?

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

Why is he using XOR operation in Div2C solution (in tutorial)?

»
3 months 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.

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

    Why it should be a permutation of 1,2,...k? In the example they clearly used repeated values.

»
3 months ago, # |
  Vote: I like it -19 Vote: I do not like it

In 1394D:

  • We can choose two challenges

In 1394E there are several corrections:

  • To be exact, the origin problem isn't asking us to calculate the number of folds, but rather the number of folding marks.
  • but you have different methods to fold it
  • The first method can be represented by
  • But is it really?
  • Firstly to be noticed
  • the definition of fold in statement always leads to
  • But you can also use different folding methods
  • because any results can be transformed
  • If you understand the folding operation intuitively, it'll be quite easy to come up with a naive algorithm that runs in polynomial time.
  • If you have already understood them, skip this section and read the algorithm part
  • two even palindromic substrings
  • Blue lines denote the center position
  • I suggest proof by contradiction is place of reduction to absurdity
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can somebody explain div2 C? The editorial is confusing.

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I wrote a simple backtracking solution for Div2C during the contest which obviously got a TLE verdict. After the contest I applied DP on top of it and got AC. If anyone's interested, here's the submission: 89782618

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

    Can you explain the base case? Like why are you returning the value of Xor computed along that path?

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

      The index variable refers to the values stored in vector $$$a$$$. For each value in vector $$$a$$$, it can be AND-ed with each value in vector $$$b$$$. The for loop denotes that part. Remember the $$$c$$$ vector stores the OR of each AND $$$(a_i \& b_j)$$$. The OR variable is just doing that. It can be solved by DP because there are overlapping sub-problems. The base case happens when you reach the end of vector $$$a$$$ i.e. you have constructed the a $$$c$$$ vector of $$$n$$$ elements whose ORs are stored in the OR variable.

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

Can someone explain me Boboniu Chats with Du approach??

»
3 months 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'...

»
3 months 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.

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

For the second question, I got this output for the first test case. But I am getting Wrong Answer. Can anyone help pls? 2 2 1 2 3 2 2 3 1 3 3 3 2 1 1 1 3 1

»
3 months 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|)$$$.

  • »
    »
    3 months 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?

  • »
    »
    3 months 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!

    • »
      »
      »
      3 months 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$$$.

  • »
    »
    3 months 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.

»
3 months 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.

»
3 months 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!!

»
3 months 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?

  • »
    »
    3 months 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

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

Please anyone help me understand the div2D/div1A solution

»
3 months 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

  • »
    »
    3 months 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?

    • »
      »
      »
      3 months 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.

»
3 months 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.com/contest/1394/submission/89813839

»
3 months 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.

  • »
    »
    3 months 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)).

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

      Yep they had given 2^9 in editorial that's why I asked. Loop runs only 9 times right?

»
3 months 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.

»
3 months 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).

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

I have tried the following approach for div.2D( div.1A):

  • Let's call elements ai>m as Y and elements ai<=m as X. We need to fill these into the n slots(X takes up 1 slot and Y takes d+1 slots)
  • The largest Y fills the last slot(so that there are no subsequent slots left to waste).
  • lets call slots left to fill as N. (initially N=n-1)
  • while N:
    • if N >= d+1 : to fill d+1 slots, we can either use one largest unused Y or d+1 largest unused Xs (whichever adds more to the final answer). N decreases by d+1.
    • if N<d+1:
      • if no Ys left to add to the slots: use N Xs to fill the remaining slots.
      • if no Xs left to add to the slots: we can add the largest unused Y by removing some small previously used Xs. (This is done only if the final answer increases)
      • if both Xs and Ys available to add into the slots: We either fill all empty slots with unused Xs or add the largest unused Y(by removing smallest previously used d+1-N Xs).

Why does this approach fail?

»
3 months 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.com/contest/1395/submission/89796424

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

Can anyone Explain The div2 D. I don't understand whether I have misunderstood the question or missing any important point.

»
3 months 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?

»
3 months 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.

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

I have a question which might be bad Doesn't taking lowest possible ci always result in best result we can achieve since OR is like addition what's wrong in my process??

»
3 months 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

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

About question 1395C - Boboniu and Bit Operations: what is the point of this piece of code? I think I understood the explanation but not the code below.

ans=(1<<9)-1;
for(int i=8;i>=0;--i)Check(ans^(1<<i))?ans^=(1<<i):0;

It seems to be updating the answer while checking if each bit can be achieved according the logic described on tutorial. Still I couldn't get this part.

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

how can i apply dp in Div2 C ?

i tried but it failed test case 9. Here is my code :

include<bits/stdc++.h>

using namespace std; int a[201],b[201]; int d[201][201]; int check(int ans,int i,int n,int m,int d[201][201],int k) { if (i >= n ) return ans;

if(d[i][k] == -1) { int mm = INT_MAX;

for(int j = 0;j<m;j++)
  {
//   cout<<i<<" "<<j<<"\n";
    int  p  = ans | check(a[i]&b[j],i+1,n,m,d,j);

    if(p< mm)
      mm= p;
  }

  d[i][k] = mm;

} return d[i][k]; }

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

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

} for(int j =0;j<m;j++) { cin>>b[j];
}

for(int i =0;i<n;i++) { for(int j =0;j<m;j++) { d[i][j]=-1; } }

//int ans = check(0,0,n,m,d,0); int mm = INT_MAX; for(int j = 0;j<m;j++) { // cout<<i<<" "<<j<<"\n"; int p = check(a[0]&b[j],1,n,m,d,j);

if(p< mm)
  mm= p;

}

cout<<mm<<"\n"; return 0; }

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

Hi, sshwyR

Thanks a lot for great problems and your extensive effort. Problem D was one of the most elegant greedy problems I have ever solved.

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

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

»
3 months 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?

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

In problem A, it's actually w+3, as each ball we select becomes a white ball, although w+1 does not change the parity,it would be more correct to make it w+3

»
3 months 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

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

Didn't Understand Div2- Problem C tutorial. Can someone please explain the logic more clearly? Please help. Write login in reply

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

For B if we define:

F(i, j) = ((S_x + i — 1) % n + 1, (S_y + j — i — 1) % m + 1)

And we print the value of F in row first order for 0<= i <= n and 0 <= j <= m, we can get the answer without odd / even branching. We just need to define the mod for negative numbers properly.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C what happens if I choose the best b[j] for any a[i] ?

If I get the Minimum (a[i] & b[j]) for every i why am I not getting the Minimum c1|c2|..cn ?

»
7 weeks 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 weeks 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 weeks 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 :)