Election Posters - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

Site Related Forums

The Yak Corral

Election Posters

Author

Topic

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2005-01-06 : 14:31:54

I've just thought to myself:
this real problem (not too hard one; I did it in pascal) looks quite / very good for t-sql
http://spoj.sphere.pl/problems/POSTERS/

btw,
all the problems are available in this pdf file: http://spoj.sphere.pl/problems.pdf

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2005-01-06 : 15:05:55

[code]create table dbo.posters (n int identity(0,1), l int, r int)

insert into posters
select 1, 2 union all
select 5, 6 union all
select 1, 4 union all
select 2, 6 union all
select 8, 10 union all
select 3, 4 union all
select 7, 10
go

create function dbo.isblocked (@n int, @l int,@r int)
returns bit
as
begin
declare @isblocked bit
set @isblocked = 0

if exists
(
select 1
from dbo.posters where l <= @l
and r >= @r and n > @n
)
set @isblocked = 1
return @isblocked
end
go

select l,r,dbo.isblocked(n,l,r) blocked
from posters
order by n desc
go

drop table posters
drop function dbo.isblocked[/code]

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2005-01-06 : 15:12:10

you're kidding me. ehorn you had that stashed somewhere didn't you

Go with the flow & have fun! Else fight the flow

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2005-01-06 : 15:51:28

lol!
obviously it can't be accepted! or can? haha
that's why I love that e-judge. You can't cheat "him"!

btw, time limit is the crucial point of 80% of those problems..
.. and seriously, 70% of them are very very very hard problems.

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2005-01-06 : 16:39:48

quote:
you had that stashed somewhere didn't you..

LoL.. Nah, just a slow Thursday

Not even sure if it satisfies all inputs

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2005-01-11 : 14:11:13

Just for our fun.

I bet no-one here can solve this really easy prob even in 3 days.

PS Feel free to post your solutions written in t-sql. I'll check them.

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-02-26 : 11:42:00

quote:
Originally posted by Stoad

Just for our fun.

I bet no-one here can solve this really easy prob even in 3 days.

PS Feel free to post your solutions written in t-sql. I'll check them.

I guess my euclidian geometry skills are not up to date.
Geel free to post a solution.

rockmoose

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2005-02-26 : 18:57:42

rocko, it's not interesting (a right solution). I just was waiting for
someone come up with "oh! it's so easy! iif (a<c) AND (b<d) then ... ".
And of course, this solution is wrong ... in general case.

uses math;
var tc,tcs,aa,bb,xx,yy: longint; a,b,x,y,e,h: double;
begin
readln(tcs);
for tc:=1 to tcs do
begin
readln(aa,bb,xx,yy);
a:=min(aa,bb); b:=max(aa,bb); x:=min(xx,yy); y:=max(xx,yy);
if (x<a)and(y<b) then writeln('Escape is possible.')
else
if (x>=a)or(y*y>=a*a+b*b) then writeln('Box cannot be dropped.')
else
begin
e:=x*(a*x+sqrt(sqr(a*x)+(x*x+y*y)*(y*y-a*a)))/(x*x+y*y);
h:=(b*y-y*y*e/x)/(a-e);
if (sqrt(y*y-(a-e)*(a-e))<b)and(h>x)
then writeln('Escape is possible.')
else writeln('Box cannot be dropped.');
end;
end;
end.

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-02-27 : 06:51:58

The diagonal/general case is non-trivial.
Got me stumped, makes me really annoyed.
Can't get e the way Yo do... e=f(a,x,y)
Oh well, maybe another day I'll try again.

rockmoose

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2005-02-27 : 07:45:43

> Got me stumped, makes me really annoyed.

Yes, rocko. It's an extremely irritating problem.
I myself was in amok state while been trying to solve it.

How about next SQL problem:
create table processes (t1 datetime, t2 datetime)
t1 and t2 mean: a process was running from point in Time t1 to point in Time t2 (including).
Problem: to write the most efficient and compact query which counts the maximal number
of processes running simultaneously.
For simplicity we can use int datatype instead of datetime datatype.

create table p (n1 int, n2 int)
go
insert into p
select 3, 8 union all
select 0, 2 union all
select 3, 8 union all
select 6, 7 union all
select 7, 9 union all
select 3, 8
go
answer is 5.

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-02-27 : 08:11:09

>> I myself was in amok state while been trying to solve it.
Don't even speak of it... Aaaaarghh.

select top 1 count(*) from
	(select distinct n1,n2 from p) p1 join p p2
	on p2.n1 <= p1.n2 and p2.n2 >= p1.n1
group by p1.n1,p1.n2
order by 1 desc

I guess it's my turn to find a puzzle, I'll see what I can come up with.

rockmoose

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-02-27 : 09:04:30

--Given a table t with one column a(int) with 3 rows,
--How many rows will this query return ?
select a from t where (a=1) or not(a=1)

rockmoose

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2005-02-27 : 09:22:22

emmm.... all.

Go with the flow & have fun! Else fight the flow

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-02-27 : 11:00:23

You know it depends....
Given the uncompleteness of the information, the query could return 0,1,2 or 3 rows.

If I give one more piece of information:
"a is unique"

How many rows will the query return?

rockmoose

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2005-02-27 : 11:18:04

can you shom me how it can return less than 3???


declare @t table (a int)
insert into @t
select 1 union all
--select 1 union all -- uncomment for un-uniqueness
--select 1 union all -- uncomment for un-uniqueness
select 2 union all   -- comment for un-uniqueness
select 3             -- comment for un-uniqueness

select * from @t where (a=1) or not(a=1)

because as i see it the where always evaluates to true

Go with the flow & have fun! Else fight the flow

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-02-27 : 11:31:15

It's somewhat of a trick question.....

declare @t table (a int /*unique*/)
insert into @t values(1)
insert into @t values(2)
insert into @t default values
select * from @t where (a=1) or not(a=1)

rockmoose

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2005-02-27 : 11:35:34

huh??
what's with the
insert into @t default values ??
you don't specify it anywhere.


declare @t table (a int default(1) /*unique*/)
insert into @t values(1)
insert into @t values(2)
insert into @t default values

-- returns 3 rows if /*unique*/
select * from @t where (a=1) or not(a=1)

-- errors out if unique
select * from @t where (a=1) or not(a=1)

Go with the flow & have fun! Else fight the flow

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-02-27 : 13:17:07

The default value for a column = null when no explicit default is provided.

The point is that the rules of 3VL(true/false/NULL)
are NOT the same as the rules of "ordinary" 2VL logic(true/false).
(for this example NULL simply represents "value not known", and makes no distinction as to why - (not entered, n/a, unknown, not valid etc...))

In 2VL:
A OR NOT(A) = TRUE

With nulls:
A OR NOT(A) OR (A IS NULL) = TRUE

This was an extremely trivial example,
but nonetheless I think it demonstrates that NULL can be a source of confusion and error.

rockmoose

Stoad
Freaky Yak Linguist

1983 Posts

Posted - 2005-02-27 : 13:27:45

quote:

Originally posted by rockmoose

select top 1 count(*) from
	(select distinct n1,n2 from p) p1 join p p2
	on p2.n1 <= p1.n2 and p2.n2 >= p1.n1
group by p1.n1,p1.n2
order by 1 desc

a bit impolitely of you to produce this brilliant solution ...
... soooo fast! :)

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2005-02-27 : 14:16:44

moose: ooooohhhhhhh..... that's your point.

ok then.

Go with the flow & have fun! Else fight the flow

rockmoose
SQL Natt Alfen

3279 Posts

Posted - 2005-02-27 : 15:48:59

>> moose: ooooohhhhhhh..... that's your point
Well yeah, no more no less, setting a tiny "logic trap"

>> a bit impolitely of you to produce this brilliant solution ...
... soooo fast! :)
Good problem...

You must unlearn what you have learnt

rockmoose

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources