×

[closed] WA in CHEFD using set stl

 0 Please help me find my mistake I followed the approach mentioned in the editorial but am getting WA asked 21 Aug '15, 20:56 893●2●11●35 accept rate: 10%

The question has been closed for the following reason "The question is answered, right answer was accepted" by dragonemperor 10 Sep '15, 11:19

 1 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. answered 23 Aug '15, 04:30 7★ceilks 1.8k●9 accept rate: 36%
 1 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. answered 22 Aug '15, 05:02 7★ceilks 1.8k●9 accept rate: 36% 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? (22 Aug '15, 09:17)

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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

Question tags:

×278
×49
×7

question asked: 21 Aug '15, 20:56

question was seen: 691 times

last updated: 10 Sep '15, 11:19