PRTAGN - Editorial

editorial
, , , , ,
22

My implementation is O(q * s.size())
https://www.codechef.com/viewsolution/25079488

The basic idea was this -
Let A and C be numbers having odd number of ones in thier binary representation
Let B and D be numbers having even number of ones in thier binary representation

Then ,
A XOR C has even number of 1s
A XOR B has odd number of 1s
B XOR C has odd number of 1s
B XOR D has even number of 1s

It means that when the parity of number of 1s is same, we get even numbers of 1s in XOR, but if parity is different, we get odd 1s in XOR

23

Got it! My bad…wrongly put the size of flag array.Thank you buddy

24

In Java, using Fast I/O helped me get rid of the TLE in Java. Big time! 2+ sec execution dropped to 0.8 sec. Also, make sure to use HashSets.

1 Like
25

I copied your solution and it’s showing WA

26

how is it possible in unsorted list ??

27

How to use fast I/O?? I did use HashSets but still it wasnt of much help

28

I tried using this but the duplicate case is bit difficult to remove without actually knowing the elements… i tried it but i got WA :frowning:

29

And for your information the same logic doesnt work on java. It shows TLE whenever we use 3 nested loop (which you did in your solution)

30

i solved this by keeping a flag array to find if the element is repeated then applied the logic that
xor of numbers with same parities has even parity else it has odd parity

31

C++ solution with STL

Used a global map and a temprory vector, every time a new query comes check if it already exits, break loop if it does. Else insert new numbers that will be formed by xor of map elements and new number “x” in a vector along with their parity which can be decided by parity of “x” the new query and previous query increement odd or even accordingly.

odd–odd–>even
even–odd–>odd
odd–even–>odd
even–even–>even

After iterating the map and forming the needed vector of new numbers insert the “x” in he map followed by inserting vector elements in the map.

link to solution: CodeChef: Practical coding for everyone

1 Like
32

How come my naive solution is passing all test cases, I am checking parity everty time before insertion. Someone comment on this please.
https://www.codechef.com/viewsolution/25202018

1 Like
33

Could anyone tell me if this algorithm is correct and fast enough?

  • Take input of x.
  • Check if x already exists in x (linear search).
  • If it does not exist, push_back(x) and use __builtin_popcount() on x to do o++ or e++.
  • Now, push_back(x^y) and use __builtin_popcount() on x^y to do o++ or e++ (where y is
    every pre-existing element in the set).
  • Print e and o.
1 Like
35

Here you are printing the value of all previous test cases with the next one.
Just write the print statement on braces after.:hushed:

36

:man_facepalming: Thanks!

I have a couple of questions -

  1. What is find() doing? I know it’s bit counting but how did you figure this out? Where do I learn these sort of things?

  2. Why did you use find() in the last if block instead of check[x]?

37

I agree with you @srishab55, my solution in Java was failing task 5 and 7, link to the solution: Java Solution. I used fast reader and the approach given by author. Although with the same approach my c++ submission got AC for all tasks, link: c++ solution. If anyone can point out any issue with my java code please reply here.

38

I am not able to understand how is the TC O(Q+max_val). Can anyone please explain?
Thanks in advance.

39

I used the find() function initially but got TLE in some test cases. So, I had to implement 2D array to check for duplicates and got AC :blush:

1 Like
40

Can you explain how gauss elimination can be used here?

1 Like
41

can someone explain the above written time complexity?

42

Can anyone help me with time complexity explanation?