smurf's blog

By smurf, 9 days ago, In English,

We invite you to participate in CodeChef’s May Cook-Off, this Sunday, 24th May, from 9:30 pm to 12:00 am IST. 2.5 hours, 5 problems.

We will also be hosting a live problem discussion sessions for Cook-Off problems with our panelist Rajarshi RestingRajarshi Basu. You can register by clicking on the GOING button on the top right corner here. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Joining me on the problem setting panel are:

  • Setters: Ritesh rishup132 Gupta, Vikas [user: cus_pandey__ji] Pandey
  • Admin: Teja cache Vardhan Reddy
  • Tester: Raja smurf Vardhan Reddy
  • Editorialist: Akash whiplash99 Bhalotia
  • Post-Contest Streaming: Rajarshi RestingRajarshi Basu
  • Statement Verifier: Jakub Xellos Safin
  • Mandarin Translator: Qingchuan Zhang
  • Vietnamese Translator: Team VNOI
  • Russian Translator: Fedor Fedosik Korobeinikov
  • Bengali Translator: Mohammad solaimanope Solaiman
  • Hindi Translator: Akash Shrivastava

Prizes: Top 10 Indian and top 10 Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

Good luck and have fun!

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

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

Hoping for a set of balance problems in DIV 1.

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

That's the shame that my bitset solution got TLE in Curious Queries. Is Divide & Conquer and FWHT necessary to get AC?

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

    Intended complexity was log(a_i)*N*logn. What was your complexity (is it better than it)?

    Solution was on lines of solving bit by bit and using fft.

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

      I had n^2/32 * log(A) during a contest. I tried to implement an idea with FFT and it got TLE as well. I wonder how it can pass if for maxtest you do 4 times FFT of size 2^18 and you must do it for each bit. It seems to have huge constant factor. Any tips?

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

        I did some testing over your code. I think, your FFT implementation is too slow and that would cause TLE.

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

Man this Problem (Chef, Chefina and Their Friendship) even accepted bruteforce TLE Solution

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

    Yeah that was terrible but its codechef so we can expect that.

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

      We can accept the issue from the server side, but this was hilarious, if someone has framed the question with such constraints he should do stress testing also, this shows how careless they are

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

        That also explains why so many Accepted solutions in Div2 than Div1 because Div1 people were trying string hashing, z-function etc. and Div2 people just tried the brute force solution(most of them might be thinking s.substr() takes O(1) time) and got it Accepted.

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

    Yes, it was a mistake. We had anti tests for the brute forces. But we had only one such test in a file which surely was not enough to stop them (we thought it was enough).

    It was also partly due to me asking to try to reduce the test files and constraints a bit to reduce load on servers. We reduced constraints on sum of lengths after everything was prepared.We messed up somewhere around there.

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

      Good to see quick response from your side hoping that you will resolve this issue

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

    Yeah I realised it as soon as I saw the no. of people who solved it in div 2 but it was too late :(

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

    Hi,

    Test cases are updated. You will have new test cases in the practice section.

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

    That's not cool! my solution wasn't getting accepted and i lost 160 rating and i am back to 3* and during the contest i saw some people solving it quite fast and after reading this comment when i checked their solution most of them used just substr function specially div2 participants :(

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

Someone passed Chefland Squads and the Army Chief with wavelet matrix ? (I got AC with fenwick tree ):)

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

    Can you explain how you used fenwick tree for the question?

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

      You can count the number of squads with strength <= K using a two-pointer method in O(n), then binary search on K for the answer.

      Edit: it's actually O(n log n) because of the Fenwick tree.

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

        Can you explain how you do that in O(n), smh

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

          Sorry, I just realized I made a mistake in my response. The runtime is O(N log N) (there are O(N) calls to a Fenwick tree).

          For each L = 1, 2, ... N, we'll count the number of R >= L such that the subsequence with indices {L, L+1, ..., R} has <= K inversions. Start with L = R = 1. Now if we increment R to R+1 we get |{L <= i <= R | A[i] > A[R+1]}| extra inversions. We can keep track of this number with a Fenwick tree. Increment R as many times as possible while keeping the number of inversions <= K. Now add (R-L+1) to the total number of squads. Next, increment L to L+1, subtract the number of inversions involving L (just like above, use the Fenwick tree), and increment R again as many times as possible. Continue until L = R = N. Since we only increase L and R, the whole runtime is O(N log N)

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

    Would it be better than $$$O(N\log^2(N))$$$?

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

      Same complexity, doesn't need any updates but with a worse constant in the query, so it's more slow :(

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

Can someone please help why greedy would fail in CHEFTRIP? Link to the explanation — https://discuss.codechef.com/t/why-greedy-fails-in-cheftrip/66605

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

    Hi, I briefly read your description and I think you're making the false assumption that the leader(?) node in your DSU must be the point where the sequence goes from increasing to decreasing.

    I tried your code locally and it doesn't work for this case

    1
    4 1
    1 2
    1 4
    2 3
    3 4 3 2
    3 4
    
    • »
      »
      »
      6 days ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Hi, thanks for the test case, by my assumption, all vertices for above tc will be in 1 set, and have leader 2 (since its height is max). and answer for the query should be 1. Actually, in my solution, I was checking h[v] < h[u], but I forgot h was sorted, so indices are not correct (Apologies for messed up code). I have now corrected it.

      I made the changes here which passes your counter example — https://www.codechef.com/viewsolution/33321951. But fails the system TC.

      Can you please tell why my assumption is wrong? Thanks.

      UPD: It fails if for a element there are 2 disjoint sets with which it could be a part of decreasing sequence. e.g.

      1
      4 1
      1 2
      2 4
      1 3
      1 2 4 3
      1 4
      

      since vertex 1, can be a part of 2 sets, I was ignoring that in my solution.

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

        try this

        1
        7 1
        1 2
        1 3
        2 4
        2 5
        3 6
        3 7
        1 6 5 9 2 8 6 
        7 1
        

        If I understand your code correctly, node 4 with value 9 will become the leader of 1 and your find_set check will fail because 7 is its own leader.

        Btw my approach in the contest was to decompose the increasing/decreasing parts of the path and use LCA/binary lifting to quickly check some cases. I didn't see an editorial posted yet, so you can refer to my submission here

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

          Yes you have understood it correctly. Your test case, is somewhat similar to the one I posted in update section, but still different in the way, since both '1' and '7' are in different sets, and a path between them have a component itself ('3' is in a different set). I got it now why it is failing. Thanks once again for your time. Will refer your solution, thanks for that too :).

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

This is my first and last time participating in Cookoff contest. I believe submatrix means “subset of rows and columns”, but surprisingly it wasn’t. I wasted tons of time debugging sample, and after realizing this I just ragequitted. You should clarify this in the statement.

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

    WTF, what’s wrong with the downvotes? The statement is clearly wrong, and there was no way to do a clarification. In vast context, e.g. the definition of determinants, submatrix is a subset of rows/columns, and it’s how Wikipedia defines it too. I don’t see any reason to assume something is contiguous (such strong assumption SHOULD BE noted)

    It’s also not like the sample explanations were clear. You have to count the number of entries, hope author didn’t excluded some terms for brevity, and then guess which kind of strange assumption author had made.

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

      You are right. As per wikipedia it is a subset.We are sorry for it, None of us in the panel never thought of it and we thought it was a straight forward definition. Hence, we never thought of it even being ambiguous. I assume the same with people who downvoted you. Also I tried to check in few other cf problems, they have described the definition of submatrix. Few things to my defence:

      a. All of the problems I have checked that used submatrix used the contiguous version (though most or all had the definition mentioned).

      b. you could have asked for a clarification, there was a comment option below every problem which is the way clarifications happen in codechef.

      c. Sample explanation had all the terms enlisted. I would not assume some terms were excluded for brevity since he got the correct output using those terms. So he could have only excluded zeros (but if you looked at it, you would know he did not assume it).

      Finally, I want to understand how to avoid such scenario in future because it is not like we missed something here. Because we never had suspicion in the definition we used (Also I think majority would have had the understanding we had though it is wrong). That was the reason we did not explain it.

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

        I got the point b now (but trust me, I tried hard to find it). Thanks for the information.

        For the last part, I don't really know. I think you should be obviously careful about the subset being contiguous or not. But surely people can make a mistake.

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

        This is Polygon advices aka Mike's rules for problem setters. Can be useful for you.

        One of them is always copies pasting standard statement instead of reinventing (defining subsequence, substring, subsegment with the same definition). They even define GCD, AND operator, XOR operators always using a Wikipedia link.

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

      Because you are the only person in the world who thinks submatrix is not a contiguous rectangle. And probably you are also a Wikipedia vandal. Look at more reliable source.

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

        you are also a Wikipedia vandal

        novel way of refuting a Wikipedia reference, I approve

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

          Wikipedia generally should not be the end of search of proof, but in this case references for this definition are quite solid

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

        I guess ko_osaga would have to vandalize all the sources provided there as well

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

I read the problem CROADS wrong, thought the ^ operator as XOR instead of AND. But the interesting fact that I observed during the contest was that the answer is exactly the same for XOR and AND operators except when n is a power of 2.