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

×

explain logic

asked 06 Mar '17, 09:07

akshay29's gravatar image

2★akshay29
894
accept rate: 0%

Even I cant get that "(x+m)%3" thing in the function. Waiting for an answer now lol XD

(06 Mar '17, 18:25) vijju123 ♦6★

@naksh9619 Asking for mark is not a good way. It seems that you are helping the people only because of earning karma points.

(10 Mar '17, 09:15) bansal12325★

yeah sure.Lets see this part in detail.
We have to find number of substrings divisible by 6 and now
1.A number is divisible by 6 only if it's divisible by both 3 and 2.
2.We can check divisibility by 2 by checking simply (number%2).
3.For a number to be divisible by 3 sum of digits must be divisible by 3.So initially m is set to 0 and every time you traverse a number, take its modulo with 3 adding the part that you have got previously (the previous value of m).This is what (x+m)is doing. for example say 975 ,for it to be divisible by 3 ,(9+7+5)%3 or (9%3+7%3+5%3) must be divisible by 3 what's the difference... Like (9%3=0) now m is 0 then comes 7,previous value of m i.e. (0+7)%3 becomes 1 and now comes 5,previous value of m which is now 1,check for (1+5)%3.
Hope You got this now.. :)

link

answered 06 Mar '17, 20:35

naksh9619's gravatar image

4★naksh9619
6196
accept rate: 12%

Good explanation, but regarding remainder I got 1 query.

We know that if we are getting remainder of, lets say 2 when we divide 5 by 3.

Then its a sure fact that (5-2)%3=0. Meaning, number - remainder would be surely divisible.

So why are we doing addition in form of (x+m) instead of using subtraction property I wrote about above. I would appreciate if you can help me here :)

(06 Mar '17, 20:39) vijju123 ♦6★
1

We are traversing every number and starting for index i of string and checking if its divisible by 3 and 2.
Lets say 975 first we will check every possible case In this case for (9,97,975) which start at index 0 then for cases which start at index 1 (7,75) and then cases which start at index 2 i.e 5 in total 6 cases 9,97,975,7,75,5.For your query i.e."Then its a sure fact that (5-2)%3=0. Meaning, number - remainder would be surely divisible." We are storing it to check for the next digit of string (Remember we have to check ever substring of the given string)
Hope you got this :)

(06 Mar '17, 20:55) naksh96194★
1

I think I need a bit more practice of dynamic programming to truly appreciate what you say. I am getting it, but there are multiple 'whys' and 'ifs' which can be best resolved by a future attempt with a much more refined skill in dp. Thanks for your effort and explanation dear ^_^

(06 Mar '17, 21:01) vijju123 ♦6★

It's all about dynamic programming. If you are not aware of dynamic programming then please try your hand on these problem unless you could not able to crack that logic. On other hand, editorial has already been provided so i suggest you to check out and tell me which line you are having a problem. Author solution is also to the point so overall the editorial and question are clear.

Please check out and comment here after that

link

answered 06 Mar '17, 11:08

bansal1232's gravatar image

5★bansal1232
2.8k1417
accept rate: 16%

1

@bansal1232 i know dynamic programming but still i m not able understand. https://www.hackerrank.com/rest/contests/hourrank-18/challenges/super-six-substrings/hackers/gvaibhav21/download_solution. if((s[i]-'0')%2 ==0) ans += cnt[presum%3]; if(i+1 == n || s[i+1] != '0') cnt[presum%3]++; if(s[i]=='0') ans++;

if 1,2 is the remainder by taking modulous by 3 then how it is divisble by 6.

(06 Mar '17, 13:52) akshay292★

@akshay29 read the observation part of the editorial,you will get to know what they are trying to say. They are saying the number is divisible by 6 only if it's divisible by both 3 and 2.They are checking both for 2 and 3 not just for 3. Hope You get this.

link

answered 06 Mar '17, 19:03

naksh9619's gravatar image

4★naksh9619
6196
accept rate: 12%

edited 06 Mar '17, 19:09

You're right here, but can you explain the " "(x+m)%3" thing in the function." ??

(06 Mar '17, 19:52) vijju123 ♦6★

m is running sum of digits of substring starting at i . Now if we extend this interval and x is the next digit, then if (x+m)%3==0 and x%2==0 then we can extend the interval and hence we memoize this answer.

m here is just used to remember the sum of last seen substring to check if next substring is super substring or not. So if previous m was 1 and now x is 2 then we have a super substring((1+2)%3==0 &&2 is even).

Had we not memoized m then we would have to find the running sum of subset again which will blow up the time constraints.

Hope this helps

link

answered 07 Mar '17, 08:15

inovation123's gravatar image

4★inovation123
4537
accept rate: 10%

What if x is not two but some other remainder like 0 or 1?

(07 Mar '17, 11:05) vijju123 ♦6★

Compute all the subarrays. Refer Link
Now for each subarray check its divisibility by 2 and 3. If number is even then it is divisible by 2 and if sum of all elements of substring is divisible by 3 the substring is divisible by 3. Also don't forget to count presence of zero in substring.
Hope it Helps.

link

answered 10 Mar '17, 09:43

swamicoder's gravatar image

4★swamicoder
2347
accept rate: 10%

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:

×290

question asked: 06 Mar '17, 09:07

question was seen: 716 times

last updated: 10 Mar '17, 09:43