IceKnight1093's blog

Invitation to CodeChef Starters 70 — 21st December, rated till 6-stars.
By IceKnight1093, 16 months ago, In English

We invite you to participate in CodeChef’s Starters 70, this Wednesday, 21st December, rated till 6-stars (ie. for users with rating < 2500).

Time: 8 PM — 11:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.

The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

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.

Hope to see you participating. Good Luck!

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

Comments Comments (16)
| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Strange Bitwise Operation ?

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

    How to solve X and Y trees, Two Counters? :crying_face

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      For Two Counters I used dp. Value of a-b can only be in between -2 and 2. Because it doesn't make sense to increase or decrease it further. You can use dp(i,j) where i is the number of seconds passed and j is the value of a-b.

      → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      In XY trees, you can use segment tree over euler tour to get the sum in a subtree. A node can only be one iff every node in its subtree is 1. For the count of good edges, it will decrease when any node will become 1 (why ?), except when the root is 1.

      For the two counters, I did exactly what @mafailure has commented.

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

      For X and Y Trees, I just stored number of descendats for each node, and parent of each node, then starting from the leaf as per query i updated the node value from 0 to 1 only when all its descendats nodes are set to 1 moving upwards from there till root node. Here is the link

      → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    s1-s2 is equivalent to s1^s2 and changing ith position element will change s1^s2 for first i-1 element as s1^s2^old_a[i]^new_a[i] and for >i it will remain same, so trie can be used to find the maximum xor.

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

      Wasn't s1-s2 for any i = xor of suffix starting at i+1. Is S1^S2 same?

      → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone give a test case on which this solution fails for two counter problem

Code

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    for any two consecutive events, we can at least choose one of them. so I am greedily increasing score in the events we can increase score, given its previous events.

    → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    10 6

    1 2 4 6 8 10

    1 1 2 1 2 1 Output : 5

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

      how is output 5. on which events we increase score.

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        For i=1, increase value of b by 1 then a = 0, b = 1 and event 1 is applied and so a = 0, b = 0

        For i = 2 increase value of a by 1 then a = 1, b = 0 and event 1 is applied so our score is 1

        For i = 3 increase value of b by 1 then a = 1, b = 1 and no event is applied

        For i = 4 increase value of b by 1 then a = 1, b = 2 and event 2 is applied so our score is 2.

        For i = 5 increase value of a by 1 then a = 2, b = 2 and no event is applied

        For i = 6 increase value of a by 1 then a = 3, b = 2 and event 1 is applied so our score is 3

        For i = 7 increase value of b by 1 then a = 3, b = 3 and no event is applied

        For i = 8 increase value of b by 1 then a = 3, b = 4 and event 2 is applied so our score is 4

        For i = 9 increase value of a by 1 then a = 4, b = 4 and no event is applied

        For i = 10 increase value of a by 1 then a = 5, b = 4 and event 1 is applied so our score is 5

        → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How To Solve X And Y Trees? I Was Trying To Solve It Using Euler Tour And Segment Tree. Anyone Who Implemented The Same Idea Or Any Other Sort Of Thing?

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

    I did it using that. Answer will decrease from n-1 to 0 until the whole tree becomes 1 then it will remain n-1. Code

    → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Some observations :

    Spoiler 1
    Spoiler 2
    Spoiler 3
    My solution

    In case if you any more doubts you can reply below this

    → Reply