10587 - Mayor's posters

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm

10587 - Mayor's posters

Post by Tomson » Sun Dec 21, 2003 5:57 pm

How to solve it ? I always got TLE.
Could anybody give me some hints?
Thanks very much!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Dec 22, 2003 1:16 am

Sort the intervals by x, then y, and scan.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Mon Dec 22, 2003 5:09 am

Larry wrote:Sort the intervals by x, then y, and scan.
What y ?
Sort just by X. :)))
Do not forget that left X and right X of poster is not the same things :)))

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Dec 22, 2003 6:18 am

Heh, you probably don't need a y, but I made it simpler by putting a y for the positiion of the posters, made it easier.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Mon Dec 22, 2003 8:43 am

Larry wrote:Sort the intervals by x, then y, and scan.
I don't know your meaning.
Could you give more detail description?
Thx :)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Dec 22, 2003 3:34 pm

There is probably be a slicker way to do it, but basically, I place a y for each poster (distinct), so I'll know what's "on top", sort as follows, and then keep an array of what's "in", and a variable for being on top, and whenever that changes, I increment..

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm

Post by Tomson » Mon Dec 22, 2003 6:20 pm

Larry wrote:There is probably be a slicker way to do it, but basically, I place a y for each poster (distinct), so I'll know what's "on top", sort as follows, and then keep an array of what's "in", and a variable for being on top, and whenever that changes, I increment..
Oh, I still cannot understand your meaning.
Could you give me some more explanation?
Thanks,!!!

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Mon Dec 22, 2003 7:25 pm

Tomson wrote:
Larry wrote:There is probably be a slicker way to do it, but basically, I place a y for each poster (distinct), so I'll know what's "on top", sort as follows, and then keep an array of what's "in", and a variable for being on top, and whenever that changes, I increment..
Oh, I still cannot understand your meaning.
Could you give me some more explanation?
Thanks,!!!
I'll try to explain.
All posters have two X-coordinates (left and right)
We sort all X-coordinates and remember which posters it relate to, and what bound it is (left or right).
Then we go through all sorted X from left to right and if current coordinate is left boundary we add in stack number of poster (then number more then poster higher over other posters, Do you understand what I mean ?).
If current coordinate is right boundary we remove from stack number of poster related to this coordinate. Then If current X coordinate does not coincide with previous one we remember number of poster which number is highest in stack.
I hope you understand my explanation.
Sorry for my english. :)

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm

Post by Tomson » Tue Dec 23, 2003 7:27 am

Thank you very much! :) I almost understand your meaning.
And finally, I solved it using a heap, it seems that 's faster than a array. my program solved it during 00.5 s.

Thank you anyway!

miko'mized
New poster
Posts: 8
Joined: Thu Dec 04, 2003 4:56 pm

10587

Post by miko'mized » Mon Jan 26, 2004 9:49 pm

I'm still getting WA, i solved that problem using a heap and i'm sure it works. Do you have any "tricky" input sample to test my program ?

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Re: [10587]

Post by rotoZOOM » Wed Jan 28, 2004 1:55 pm

miko'mized wrote:I'm still getting WA, i solved that problem using a heap and i'm sure it works. Do you have any "tricky" input sample to test my program ?
Try this one:
1
3
1 4
5 10
3 7

Right answer is:
2

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Re: [10587]

Post by rotoZOOM » Wed Jan 28, 2004 1:58 pm

miko'mized wrote:I'm still getting WA, i solved that problem using a heap and i'm sure it works. Do you have any "tricky" input sample to test my program ?
Try this one:
1
3
1 4
5 10
3 7

Right answer is:
2

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Apr 17, 2004 10:15 pm

Obviously, this input/output pair is wrong........
Please delete/correct it
It confuses me for few days until I read the problem for many many times and make sure I understand the problem correctly........
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Mon Apr 19, 2004 3:46 am

.. wrote:Obviously, this input/output pair is wrong........
Please delete/correct it
It confuses me for few days until I read the problem for many many times and make sure I understand the problem correctly........
Yeah, I'm sorry.
My bug.
Correct input is:
1
3
3 7
1 4
5 10

Right answer is:
2

Sorry again.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Apr 15, 2006 4:51 am

Hi there fellow sufferers!

This problem seem me easy, but I'm getting WA and can't encounter any case where my code fails.
Could anyone take a look to my code or give me some good test cases where my code fails?

Code: Select all

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cmath>
#include <cassert>
#include <list>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;

struct lrn {int lr,n;};
struct comp_lrn
{
    bool operator () (lrn a, lrn b) const
    {
        return a.lr<b.lr;
    }
};
set<lrn,comp_lrn> wall;
set<int> difs;

int main ()
{
    set<lrn,comp_lrn>::iterator it, itend;
    set<int>::iterator itd;
    lrn g;
    int casos, N, l, r, i;
    
    cin >> casos;
    while (casos--)
    {
        cin >> N;
        wall.clear();
        for (i=0; i<N; i++)
        {
            cin >> l >> r;
            
            /* I hide the limits of other possible coincident posters */
            g.lr=l, wall.erase(g);
            g.lr=r, wall.erase(g);
            /* I insert this new poster */
            g.lr=l, g.n=i, wall.insert(g);
            g.lr=r, g.n=i, wall.insert(g);
            /* If l==r all the possible limits poster that must be deleted was already deleted */
            if (l==r) continue;
            /* I find the limits of the new poster in the data structure */
            g.lr=l, it=wall.find(g);
            g.lr=r, itend=wall.find(g);
            difs.clear();
            for (++it; it!=itend; ++it)
            {
                /* I store the limits of some posters hidden by the new poster */
                difs.insert((*it).lr);
            }
            /* I erase all the poster limits hidden by the new poster */
            for (itd=difs.begin(); itd!=difs.end(); ++itd)
            {
                g.lr=*itd;
                wall.erase(g);
            }
        }
        /* Finally, I make a set of all the different posters */
        difs.clear();
        for (it=wall.begin(); it!=wall.end(); ++it) difs.insert((*it).n);
        cout << difs.size() << "\n";
    }
    return 0;
}
P.S. Sorry for posting code

Post Reply

Return to “Volume 105 (10500-10599)”