Code Submission Evaluation System Login

Datatähti 2016 alku

Start:2015-09-28 00:00:00
End:2015-10-12 00:00:00
 

Tasks | Scoreboard | Statistics


CSES - Datatähti 2016 alku - Results
History
2015-09-30 22:05:5014
Task:Tontti
Sender:AnttiR
Submission time:2015-09-30 22:05:50
Language:Python2
Status:READY
Score:14

Feedback

groupverdictscore
#1ACCEPTED14
#2TIME LIMIT EXCEEDED0
#3RUNTIME ERROR0

Test results

testverdicttime (s)group
#1ACCEPTED0.07 / 1.001details
#2ACCEPTED0.33 / 1.001details
#3ACCEPTED0.10 / 1.001details
#4ACCEPTED0.07 / 1.001details
#5ACCEPTED0.08 / 1.001details
#6TIME LIMIT EXCEEDED-- / 1.002details
#7TIME LIMIT EXCEEDED-- / 1.002details
#8TIME LIMIT EXCEEDED-- / 1.002details
#9TIME LIMIT EXCEEDED-- / 1.002details
#10TIME LIMIT EXCEEDED-- / 1.002details
#11RUNTIME ERROR0.57 / 1.003details
#12TIME LIMIT EXCEEDED-- / 1.003details
#13RUNTIME ERROR0.64 / 1.003details
#14RUNTIME ERROR0.66 / 1.003details
#15RUNTIME ERROR0.64 / 1.003details

Code

trees = []
height,width,wantedTrees = [int(x) for x in raw_input().split(" ")]
# Last tiles you can go to in each direction
limits = width-1, height-1

# Find trees from imput and place them to an list.
for y in range(0,height):
	inputRow = raw_input()
	for x in range(0, len(inputRow)):
		if inputRow[x] == '*':
			trees.append((x,y))
			
# Find all possible squares, that are as small as possible.
foundRectangles = []

shorter_smaller = 0
shorter_higher = 0
longer_higher = 0
longer_smaller = 0

for index_1 in range(0,len(trees)):
	for index_2 in range(index_1,len(trees)):
		
		tree_1 = trees[index_1]
		tree_2 = trees[index_2]
		
		longer = 0
		if abs(tree_1[0]-tree_2[0]) < abs(tree_1[1]-tree_2[1]):
			longer = 1
		shorter = (longer + 1) % 2
		
		if tree_1[shorter] >= tree_2[shorter]:
			shorter_higher = tree_1[shorter]
			shorter_smaller = tree_2[shorter]
		else:
			shorter_higher = tree_2[shorter]
			shorter_smaller = tree_1[shorter]
			
		if tree_1[longer] >= tree_2[longer]:
			longer_higher = tree_1[longer]
			longer_smaller = tree_2[longer]
		else:
			longer_higher = tree_2[longer]
			longer_smaller = tree_1[longer]
		
		side = longer_higher - longer_smaller
		max_distance = side - (shorter_higher - shorter_smaller)

		# Shorter is the axis with varying values.
		# Max distance is the max variance from the default position.
		# Longer is the axis that has longer distance beetween the values of the two points.
		# Longer determines the size of the rectangle.
		all_positions = list(range(max(0, max_distance - shorter_smaller), min(max_distance, (limits[shorter]) - shorter_higher)+1))
		# If it is impossible to construct a square with those two trees inside, just continue.
		if len(all_positions)==0:
			continue
		
		
		
		# Find where a new tree enters or leaves the area.
		modifyTrees = dict([(i, 0) for i in all_positions])
		for tree in trees:
			if tree[longer] < longer_smaller or tree[longer] > longer_higher:
				continue
			tree_pos = tree[shorter]
			if tree_pos < shorter_smaller-max_distance+all_positions[0] or tree_pos > shorter_higher+all_positions[-1]:
				continue
			
			# The tree is somewhere in the vicinity of our rectangle. Let's find it!			
			if tree_pos < shorter_smaller - max_distance + all_positions[-1]:
				modifyTrees[tree_pos + max_distance - shorter_smaller + 1] -= 1
				modifyTrees[all_positions[0]] += 1
			elif tree_pos > shorter_higher+all_positions[0]:
			    
				modifyTrees[tree_pos - shorter_higher] += 1
			else:
				modifyTrees[all_positions[0]] += 1
		# Find areas with the correct amount of trees.
		trees_in_area = 0
		for positionModifier in all_positions:
			trees_in_area+=modifyTrees[positionModifier]
			if trees_in_area == wantedTrees:
				if longer == 0:
					rectangle = (longer_smaller,shorter_smaller-max_distance+positionModifier,side)
				else:
					rectangle = (shorter_smaller-max_distance+positionModifier,longer_smaller,side)
				if rectangle not in foundRectangles:
					foundRectangles.append(rectangle)
# Now, for every small rectangle, try to make it larger in each direction.
lFR = []

def tryLargerRectangles(rectangle):
	side = rectangle[2]+1
	recX=rectangle[0]
	recY=rectangle[1]
	for dxy in [(-1,-1),(-1,0),(0,-1),(0,0)]:
		newX = recX
		newY = recY
		
		newRecX=recX+dxy[0]
		newRecY=recY+dxy[1]
		
		if dxy[0]==0:
			newX+=side
		else:
			newX-=1
		if dxy[1]==0:
			newY+=side
		else:
			newY-=1
		
		if newX < 0 or newX > limits[0] or newY < 0 or newY > limits[1]:
			continue
		
		conflict = False
		for tree in trees:
			tree_x = tree[0]
			tree_y = tree[1]
			if (tree_x == newX and tree_y >= newRecY and tree_y <= newRecY+side) or (tree_y == newY and tree_x >= newRecX and tree_x <= newRecX+side):
				conflict = True
				break
		
		if not conflict:
			newRec = (newRecX,newRecY,side)
			if newRec not in lFR:
				lFR.append(newRec)
				tryLargerRectangles(newRec)


for rectangle in foundRectangles:
	tryLargerRectangles(rectangle)

print len(lFR)+len(foundRectangles)
		



























Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 10 1
......*...
.......*..
*..*....*.
*....*....
...
view   save

correct output
94

view   save

user output
94

view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
10 10 5
**********
**********
**********
**********
...
view   save

correct output
0

view   save

user output
0

view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
10 10 10
**...*...*
*..*.**.*.
...**.*..*
*...**.*..
...
view   save

correct output
4

view   save

user output
4

view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
10 10 5
****......
*.*.**..**
....*.*..*
...*.***..
...
view   save

correct output
16

view   save

user output
16

view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
10 10 2
**.***..*.
...*.*....
.***.*...*
***.***..*
...
view   save

correct output
30

view   save

user output
30

view   save

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
500 500 1
.................................
view   save

correct output
9552040

view   save

user output
(empty)

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
500 500 5
.................................
view   save

correct output
1536063

view   save

user output
(empty)

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
500 500 25000
**...*...**..*.*..*.**.*..*.*....
view   save

correct output
288

view   save

user output
(empty)

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
500 500 12500
**.**.*..*...*.**...*.***........
view   save

correct output
786

view   save

user output
(empty)

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
500 500 5000
.*.*.**..*.*.**.**..*..**...*....
view   save

correct output
1763

view   save

user output
(empty)

Test 11

Group: 3

Verdict: RUNTIME ERROR

input
2000 2000 1
.................................
view   save

correct output
489611392

view   save

user output
(empty)

Error:
Traceback (most recent call last):
  File "input/code.py", line 131, in <module>
    tryLargerRectangles(rectangle)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(newRec)
  File "input/code.py", line 127, in tryLargerRectangles
    tryLargerRectangles(ne

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
2000 2000 5
.................................
view   save

correct output
120725884

view   save

user output
(empty)

Test 13

Group: 3

Verdict: RUNTIME ERROR

input
2000 2000 400000
..*..**.**.**.*.***...**.*..**...
view   save

correct output
1849

view   save

user output
(empty)

Test 14

Group: 3

Verdict: RUNTIME ERROR

input
2000 2000 200000
***.*....*.*..*....**..*..*.*....
view   save

correct output
2665

view   save

user output
(empty)

Test 15

Group: 3

Verdict: RUNTIME ERROR

input
2000 2000 80000
**.**...*.***.**....**.*....*....
view   save

correct output
5587

view   save

user output
(empty)