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:
- Setters: Kanhaiya notsoloud1 Mohan, Wuhudsm wuhudsm, S.Manuj DarkSparkle Nanthan, Mayank DreadArceus Talwar, Ashley errorgorn Khoo, Chaitanya Chaty342 Darwai, Utkarsh Utkarsh.25dec Gupta
- Testers: Nishank IceKnight1093 Suresh, Satyam satyam343
- Statement Verifier: Kanhaiya notsoloud1 Mohan
- Video Editorialists: Garvit garvitvirmani0 Virmani, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc
- Text Editorialist: Nishank IceKnight1093 Suresh
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!
How to solve Strange Bitwise Operation ?
Can it be solved using trie, and using the parity of bit in original a[i] and modified a[i] ?
How to solve X and Y trees, Two Counters? :crying_face
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.
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.
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
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.
Wasn't s1-s2 for any i = xor of suffix starting at i+1. Is S1^S2 same?
can anyone give a test case on which this solution fails for two counter problem
Code
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.
10 6
1 2 4 6 8 10
1 1 2 1 2 1 Output : 5
how is output 5. on which events we increase score.
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
oh thanks.
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?
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
Some observations :
a)A node can never be one until it's all subtree nodes is not 1.
b)If root is 1, then all nodes are going to be 1, so answer would be n-1.
c)If root is not 1, then answer is going to be n-1-number_of_nodes_which are 1.
I first got all the leaf nodes, then I maintained two array which are done, and val, val[i] tells me how many adjacent nodes are one, and done[i] will tell wether ith node is one or not.
Suppose I get query 1 u, if u is done[u] is 1 no need to process, Else if it's leaf node then I would increase the cnt1(number_of_nodes_which are 1) and make done[u]=1 and val[parent[u]]++
Else if it's not leaf node then all its adjacent nodes should have been 1 that val[u]=gr[u].size()-1 (if u is not root) or val[u]=gr[u].size() (if u is root), if they are following then I will them one, done[u]=1, and val[parent[u]]++.
My solution link : Link
In case if you any more doubts you can reply below this