You are not logged in. Please login at www.codechef.com to post your questions!

×

INCXOR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Lewin Gan
Testers: Kamil Dębowski
Editorialist: Lewin Gan

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Bitmask DP, Digit DP

PROBLEM:

Find the number of increasing sequences that are also increasing when XOR-ed by another sequence.

QUICK EXPLANATION:

First, it's helpful to be familiar with digit dp. The state we need to keep is whether or not b_i is strictly less than b_{i+1} and a_i XOR b_i is strictly less than a_{i+1} XOR b_{i+1}. This is a total of 2^(2(N-1)) states per digit.

EXPLANATION:

Using the logic above, we can solve $f(bit, mask1, mask2)$ denoting number of ways given we can fill in the bits 0 to bit. The i-th bit in mask1 (resp mask2) is 1 if and only if b_i (resp a_i XOR b_i) is strictly less than b_{i+1} (resp a_{i+1} XOR b_{i+1}).

Using this logic, we can brute force over all 2^n ways to fill in the current bit for b, make sure they satisfy the constraints in mask, and recurse to smaller cases.

To see more details, see the setter's solution.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester Solution will be added soon.

This question is marked "community wiki".

asked 19 Mar, 22:03

lg5293's gravatar image

7★lg5293
511212
accept rate: 10%

edited 20 Mar, 00:22

admin's gravatar image

0★admin ♦♦
14.6k347483502


The problem setters code is in Java. Can u add the testers or the editorialists code if it is in c++.

link

answered 20 Mar, 00:24

mathecodician's gravatar image

5★mathecodician
2.2k214
accept rate: 8%

Hi, Could someone please explain this line

The i-th bit in mask1 (resp mask2) is 1 if and only if b_i (resp a_i XOR b_i) is strictly less than b_{i+1} (resp a_{i+1} XOR b_{i+1}).

in a little more detail.

Thanks a lot for the editorial! :D

link

answered 20 Mar, 00:23

s4shyam95's gravatar image

5★s4shyam95
1995
accept rate: 20%

First, you should be familiar with digit dp. If not, most of the following will not make sense. Let's just talk about mask1 (mask2 is identical). Since we're iterating from highest bit to lowest bit, we know that p < q if and only if the highest bit in which p and q differ has a 0 in that position for p and a 1 in that position for q. So, we know that b_i and b_{i+1} have to be the same until some certain bit where b_i has a zero and b_{i+1} has a 1, and after that, they can be whatever they want. Thus, the mask helps us keep track of that state for us.

(20 Mar, 03:33) lg52937★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×10,054
×722
×60
×54
×26
×4

Asked: 19 Mar, 22:03

Seen: 657 times

Last updated: 20 Mar, 03:33