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

×

[closed] WA in CHEFD using set stl

Please help me find my mistake

Problem code
My solution

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

asked 21 Aug '15, 20:56

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

closed 10 Sep '15, 11:19

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


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.

link

answered 23 Aug '15, 04:30

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

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.

link

answered 22 Aug '15, 05:02

ceilks's gravatar image

7★ceilks
1.8k9
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) dragonemperor3★

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

Question tags:

×278
×49
×7

question asked: 21 Aug '15, 20:56

question was seen: 691 times

last updated: 10 Sep '15, 11:19