FENCING PROBLEM - April 19 long challenge

general
,
1

Can we solve this question by using char array and not by using vector,map etc.

i have solve it but i got partially correct.
my code

1 Like
2

Hi @goku_11,

I think that your code should have:

char a[10**9][10**9]={'\0'};

This is because n,m according to the constraints are within the range 1 <= n,m <= 10^9
I don’t know if this will result in a TLE or any other error. (don’t know about memory handling)
If it works, please do let me know.

Cheers
Aadarsh…

1 Like
3

I guess you are getting partially correct because you are trying to access something out of bound or something related to memory. I’m not sure of it, though, I think if you solve this problem using structures it will be better.
Even I had the same problem at first because of using a 2d array to store data. This fetched me partially correct answer. but then I Improved of some better logic and got AC.
My first solution- (30 points)- using array-CodeChef: Practical coding for everyone
My second solution (70 points+30 points)- Using class(structure)- CodeChef: Practical coding for everyone

1 Like
4

Your logic is correct, but using a matrix is not feasible, as matrix as big as [10^9][10^9] will blow up the memory and time limits :slight_smile:

Try using an efficient approach and check the editorial :slight_smile:

4 Likes
6

Even I cannot find the editorial for FENCING
pls attach it

1 Like
7

a[109][109] memory size you can not be use because their had limit is given for memory 500000 bytes and your array use more space .
you need to create size of a[k][2] .

2 Likes
8

this problem can be solve using only array use don’t need to use map/vector
simply create a[k][2] size array
link:
https://www.codechef.com/viewsolution/23881868

2 Likes
9

finally solved it using simple two simple operations
binary search and quick sort
simple implementation using C

2 Likes
10

Can anyone tell me why this solution gives AC for subtask 2 but not for 1? What I am doing is calculating the sum on the fly by -

  1. storing each input plant’s position in a hashmap
  2. starting with a fence value of 4, subtracting 2 for every plant found on its sides (which is done by checking if there is a key for those positions in the hashmap)
  3. adding the final value to the sum

This seems like a good solution but since it’s failing, I think the logic is wrong somewhere.

2 Likes
11

My solution using a single dictionary data structure:

https://www.codechef.com/viewsolution/23792767

1 Like
12

this will result in RE, if defined within main().

1 Like
13

@sammy00747,

As I mentioned above, I didn’t know about memory handling and time limits in C++. I also tried to use a matrix-like structure but resulted in TLE for the 2nd subtask. So, I used a dictionary data structure to store the co-ordinates for easy access (something similar to yours.

My code: CodeChef: Practical coding for everyone

Cheers
Aadarsh…

1 Like
14

@anon8049083 Nice solution. What is the logic behind the solution? What does matrix[i] contain?

15

@anon31395802
here’s my editorial