iamalwayshappy's blog

By iamalwayshappy, history, 6 weeks ago, In English

Is there anyone who gave zio 2022 held on 5 december? Can we discuss it's solutions here??

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

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

There's already a discussion thread on CodeChef.

Quoting the questions from there:

Q1) Given a binary string (represented by B and G for boys and girls in question), find the least number of switches (switching position of B and G from any index counts as 2) that maximizes the number of adjacent characters that are not the same.
Q2) Ways to partition an array (consisting of 1,2,3,…,n) into less than or equal to k sub arrays such that for any two sub arrays A and B, there are no elements a,c ∈ A and b,d ∈ B such that a<b<c<d.
Q3) Given a tree with bidirectional weighted edges. Pair nodes such that the sum of distances between each pair is minimized.
Q4) Lexicographically reorder all arrays whose individual elements add up to 1, 2, 3, so on. That is, the reordered list will be: [1],[1,1],[2],[1,1,1],[1,2],[2,1], [3]… and so on. Find the sum of the digits in the 10^6th element of list and product of the digits in the 10^9th element in the list.

These questions are a summarized version and I have skipped over a few details/story-setting.

And the answers (I also got the same except for Q2)

Q1.
 a)4
 b)6
 c)6
Q2.
 a)46
 b)42
 c)16796
Q3.
 a)127
 b)40
 c)236
Q4.
 a)2
 b)20
 c)864
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    IDK but for ,first my ans are (we have to make max pair of the opposite genders and max no. of pair would be min(no.of boys,no. of girls) 4 2 4

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

      That's cause you would have considered that one girl and one boy can be a part of only one pair.

      For example: in GBG there can be 2 pairs: GB and BG but if you consider that one boy can be a part of only one pair then you will be forming only 1 pair either GB or BG.

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

        Do you know 2nd testcase of first question?

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

          GGGBBBBBBBG

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

            MY answer : (GB)(GB)(GB)BBB(BG)

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

              According to your answer, there will be 6 pairs

              1 2 3 4 5 6 7 8 9 10 11
              G B G B G B B B B B  G
              
              1.(1,2) = GB
              2.(2,3) = BG
              3.(3,4) = GB
              4.(4,5) = BG
              5.(5,6) = GB
              6.(10,11) = BG
              

              So, totally 6 pairs such that adjacent elements are not of the same type.

              But another which performs better is BGBBGBGBBGB

              1 2 3 4 5 6 7 8 9 10 11
              B G B B G B G B B G  B
              
              1. (1,2) = BG
              2. (2,3) = GB
              3. (4,5) = BG
              4. (5,6) = GB
              5. (6,7) = BG
              6. (7,8) = GB
              7. (9,10) = BG
              8. (10,11) = GB
              

              Hence, giving us 8 pairs such that adjacent elements are not of the same type.

              The swaps to achieve the order would be:

              GGGBBBBBBBG => GGGBBBBBBGB => BGGBGBBBBGB => BGBBGBGBBGB

              After changing positions of 6 students you achieve this arrangement.

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

I am getting different answers for ques 2? Is there anyone else who are getting different answers for ques 2.

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

    My Python code for Q2 gives the following answers:

    A) 46

    B) 42

    C) 16796

    Though my approach is just brute force (and definitely not the intended one, but nevertheless it verifies the answer)

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

Any idea about cutoff for class 9?