WA in CHEFD using set stl

general
, ,
1

Please help me find my mistake

Problem code

My solution

I followed the approach mentioned in the editorial but am getting WA

2

I found a possible bug:

You may not use iterators to an element you just deleted. They are invalid. In general this will result in undefined behaviour, so possibly WA.

Addiotinially (not wrong but time-consuming):

Don’t use lowerbound function for std::set. Set doesn’t have random-access iterators, so complexity will be O(n) instead of O(log(n)). for O(log(n)) retrieval use the lowerbound member function of set.

I don’t know if your solution will pass after the corrections, but it’s a start.

1 Like
3

Bro, can you please explain a bit? I didn’t get you. I am not revisiting any element that are deleted. Where am I accessing invalid elements?

4

Doesn’t fit into a comment so a second answer…

I was referring to this part of your code:

                            
              for(;i!=five.end();i++)
				{
					int temp=*i;
					if(temp>r)
						break;
					if(arr[temp]%5==0)
						arr[temp]/=5;
					if(arr[temp]%5!=0)
						five.erase(i);
				}

You are erasing the element pointed to by the iterator i. Before the next loop i gets incremented. But where is i pointing to before being incremented? Since i has been erased, its not in the set anymore.

What is happening is implementation-dependent. Sometimes, you may succeed in iterating to the next element (because the structure of the set is not actually deleted). But somtimes you don’t, e.g if the tree implementing the set is rebalanced after erasing.
Looking at a stl reference, it says under iterator validity of the erase operation:

Iterators, pointers and references referring to elements removed by the function are invalidated.

So its not save to use i after erasing.

1 Like