FATCHEF-Editorial

editorial
, , ,
2

What is wrong in this solution? Help…!!

static int mod = (int)(1E9 + 9);

static void solve()
{
for(int T=nextInt();T>=1;T–)
{
int n=nextInt(), m=nextInt();
int x,y;
int color[] = new int[n];
for(int i=0;i<m;i++)
{
String s[] = nextLine().split(" ");
x = (int)(s[0].toCharArray()[0]);
y = Integer.parseInt(s[1]);
color[y-1]= x;
}
int flag=0,prevI=0,total=1;
for(int i=0;i<n;i++)
{
if(color[i]!=0)
{
flag++;
if(flag==1)
{
prevI=i;
}
else
{
if(color[i]==color[prevI])
{
prevI=i;
total = total%mod;
}
else
{
total = ((total%mod)*((i-prevI)%mod))%mod;
prevI=i;
}
}
}
}
out.println(total);
}

3

Also worth mentioning is the use of the property (axb)%val=((a%val)x(b%val))%val!!
As this would not let the integer overflow happen.

5 Likes
4

I think that the problem was not tested properly. Solutions of similar complexity in Java are getting different verdicts. One is AC and other is TLE. For example, here is AC solution and a similar solution but TLE.

5

I did the same thing as mentioned here . Still I was getting TLE . It would be great if someone points out the mistake in the given code.

http://www.codechef.com/viewsolution/5123371

1 Like
6

Why is my solution giving TLE even if i have solved in O(n)… Please help me .Here’s the code: CodeChef: Practical coding for everyone

7

the same algorithm steps are done in Java and got TLE. anyone know a way to speed up the input read ?

8

For those using C++, this might help for TLE - my answer

2 Likes
9

What is wrong with my solution? I have used the same approach in JAVA.
Here is link to my solution. Please see to it and HELP…!!
Thanks in advance.

http://www.codechef.com/viewsolution/5131646

10

All those getting a TLE, please use fast I/O. Use this implementation of fast I/O or any other that you would like.

11

Edit:- beroul has pointed out my mistake. There is no flaw in the answer.

I think this answer has a flaw.

If you consider 1000200030004 as input(as used in the editorial).

If some point between first and fifth is coloured 2, it means it can only be start or end.

Space between bucket is used in following lines, for 1 and 2 it refers to the zeros at positions 2nd,3rd,4th

It means that there can only be 2 gaps between buckets, which are coloured with colours on either side buckets.

But, this answer assumes that 1111223333444 is possible, which is having 3 spaces between buckets.

I tried to ask about this via comment but there was no reply from admin.

12

I did exactly the same as mentioned.But still getting the WA .
anyone could tell me why.?
here is the link to my solution
http://www.codechef.com/viewsolution/5152710

13

what is the answer to above example.?i.e the total number of combinations after modulo.?

14

anyone could please point out the mistake in my code ?
I am getting wrong answer again n again.
link to my solution → CodeChef: Practical coding for everyone

15

prob with code , gives WA . please point out :

https://code.hackerearth.com/12ad60I

16

I didn’t use Fast I/O being a java user.Instead I did an optimization i.e start from the minimum position(which is painted) and go till Max Position(which is painted).
Hope that helps.

Here is my


[1] for reference.


  [1]: https://www.codechef.com/viewsolution/15878434
17

It’s a good question on combinatorics :slight_smile:

18

I did the same thing as mentioned here . Still I was getting TLE . It would be great if someone points out the mistake in the given code.

http://www.codechef.com/viewsolution/5123371

19

why wrong answer???
http://www.codechef.com/viewsolution/5064542

20

For java , time limit was too strict. I submitted the same code in C and it was accepted. Why so?

21

I took the same approach and got TLE. CodeChef: Practical coding for everyone