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

×

BLocked website long TLE

LInk to problem : https://www.codechef.com/MAY17/problems/WSITES01/

My sol : http://ideone.com/x04NBs

In subtask 2 only 13,14 are showing TLE

It shows TLE, How can i optimize it further??

EDIT : I am trying to put (+) sites in one structure and (-) sites in another structure

and for each (-) site i am comparing all (+) sites and then putting longest continous pattern for a (-) site

from all (+) site to another structure.

In worst case we can have 10^3 (+) sites and 10^2 (-) sites making time complexity O(10^5).

So why i am getting TLE?

asked 18 May '17, 18:37

chunky_2808's gravatar image

3★chunky_2808
1639
accept rate: 4%

edited 18 May '17, 19:17


There is certainly a way to solve this problem without using tries. You can store blocked and unblocked sites separately (which as you say you did). You can now try to optimize this further.

1) We observe that for every blocked site, we only need to compare it with those unblocked sites that start with the same letter. So you can use a vector of vectors to achieve this.

2) Sort the websites in both structures. While you iterate through the unblocked websites (for a particular blocked website), you keep track of the maximum number of common occurences, and once the number of occurences becomes lesser than the current maximum, you can stop your search for the current blocked website. This works because you've sorted the websites.

These optimizations should be enough to pass the required time constraint. Here is my solution for reference - link text

link

answered 18 May '17, 20:10

fayaz_007's gravatar image

5★fayaz_007
764
accept rate: 20%

That is the answer I was looking for.. I have stored blocked,unblocked sites seperately. I have also compared first letter by hashing ,just didn't sort the structures Btw thanks!!!

(18 May '17, 22:25) chunky_28083★

If you can try explaining your approach, thinking and what you intended to do, i think you will receive the answer MUCH quicker. It would help many people in understanding your code, which might else take considerable time for them. :)

BTW, roughly, even i faced same problem. 2 of the test cases showing TLE. The number of websites (value on N) in those is ~3 x 10^4 to 5 x 10^4 . So accordingly if you have any algo which depends on number of strings in both and comparisons among each of them, as well as their length, then it will time out.

EDIT:

Lets say test case has 4 x 10^4 websites, half good, half bad.

So we got, 2x10^4 bad and 2x10^4 good websites.

If you are comparing each good website to each bad one, then there are atleast 4 x 10^8 comparisons. And if it involves string length too, then its 2 x 10^9 operations. I think it will give a TLE.

link

answered 18 May '17, 19:08

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859
accept rate: 18%

edited 18 May '17, 19:31

This question can be easily solved using Trie data structure. You can study it here: https://www.youtube.com/watch?v=AXjmTQ8LEoI

link

answered 18 May '17, 19:09

rishi_07's gravatar image

5★rishi_07
31617
accept rate: 20%

edited 18 May '17, 19:12

Ya i know it can be solved using tries but i am asking Is there any way to optimize my code/approach??

(18 May '17, 19:20) chunky_28083★

this is my approach to solve this problem using trie and using dfs to display prefixes of blocked sites

link

answered 18 May '17, 20:53

srihari_v's gravatar image

2★srihari_v
111
accept rate: 0%

I solved it using Trie data structure and DFS. Here's the code for the same.

link

answered 18 May '17, 22:09

alzio26's gravatar image

1★alzio26
11
accept rate: 0%

toggle preview
Preview

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:

×397
×176
×18

question asked: 18 May '17, 18:37

question was seen: 589 times

last updated: 18 May '17, 22:25