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

×

AUG18 - Problem Discussion

0
2

Hey guys!!

Finally after 10 tiring days the August long concludes. Lets share our approaches for the problems here while editorials for problems come out (at this moment not all of them are out)? Got any interesting approach which you cant wait to share? The wait is over :)

So, which was your favourite problem? I had best time solving Interactive Matrix :). The princess gave me a run for my score xD - so I let her stay with dragons and be by herself then :p

But on a serious note, anyone who was able to save the princess (or prince...? :p). I kept on getting WA for larger TCs, so I appreciate any approaches for it :)

Let the discussion begin!

asked 13 Aug, 16:27

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857
accept rate: 18%

Can anyone share approach of Interactive matrix in short ??
@vijju123 :D ??

(13 Aug, 16:46) l_returns4★

I dont have any interesting solutions :( . I solved the first 4 problems and editoirals of 3 of them are already out. My solution for interactive matrix is pathetic as well :(

(13 Aug, 16:57) vijju123 ♦♦5★

I dont have any interesting solutions :( . I solved the first 4 problems and editoirals of 3 of them are already out. My solution for interactive matrix is pathetic as well :(

(13 Aug, 16:58) vijju123 ♦♦5★

okay np xD

(13 Aug, 17:06) l_returns4★

Where is being orange treat??

(13 Aug, 17:56) aryanc4035★

Who became orange? :o

(13 Aug, 19:39) vijju123 ♦♦5★

Oops orange is >= 2200.

(13 Aug, 20:08) aryanc4035★

ohh you missed by 48
@vijju123

(13 Aug, 20:30) l_returns4★

pseudo orange

(13 Aug, 21:11) aryanc4035★

Codechef wont let me become orange this easily :(

(13 Aug, 21:41) vijju123 ♦♦5★

....... XD

(14 Aug, 15:31) l_returns4★
showing 5 of 11 show all

Kudos to problem setters, really enjoyed the question set.

Interactive matrix was fun of all, since all I put in was sheer intuition without checking it for any sample input. My approach was to spend first (2N) queries to get details of all elements lying is primary and secondary diagonal and mark them either as smaller or larger than the number, if the search element is found, output the answer and exit the program. Moreover from values of diagonal elements, it is easy to say if a row or column is sorted in increasing order or decreasing order. Next, with the sorting order for each row and column known, with the inputs obtained from first 2N queries, some of squares can be marked off as smaller or greater than the value and hence can't be answer.

Insert the remaining possible cells (pair of {row,column} ) in a vector. While vector is not empty, randomly shuffle the last element with any of element and query for this row and cell index. Mark this cell as less than or greater than, since we know the sorting order of this row and column, we can predict about the values of elements lying in same row but different column and similarly for same column and different row. So, we can basically make a call to (i,j+1) , (i,j-1), (i-1,j), (i+1,j) and mark them accordingly. And these cells then can again call their neighbhour cells and so on and every cell visited is marked in original grid as smaller or larger value and hence the further queries should only be made for those cells who values are not known.

A better approach would have been to ask for centre of grid containing unknown squares, but random picking of cell is good enough to give better expected value.

Lonely cycle was not so lonely, the possibility of many cycles coming up together ruined my initial approach until, i finally gave up the idea of pre-processing and rather started to memorize the answer for the path travelled. A classic DP approach and the code fetching 20 points fetched 100 points.

Kcompress, it took me very long to understand what the question is about and then it was easy. Binary search with Max segment tree, some greedy approach and something like dsu (since elements having same value can have different compressed values) and it was done.

Spent some days but princess was out of reach :p, First, went for N! permutation approach to get 10 points, then 2^N approach to get another 10 points. I got an interesting conclusion that answer for all possible caves will be max(Sol[1]-k,p), where sol[1] is the minimum values required to sum up to given strength and k is ith cave. p is the answer for when the princess is in middle of cave. I couldn't solve for p and kept on trying to optimize my dp.

The river problem was good too, I think the idea was of centroid decomposition but din't tried the problem.

Looking forward for official editorials :)

A lot of things to learn as always :)

link

answered 13 Aug, 17:21

forgotter's gravatar image

5★forgotter
2024
accept rate: 0%

1

River problem was finding "Minimum vertex cover" (i.e. minimum number of nodes to remove to disconnect entire tree, in other words, minimum nodes to remove so that degree of all remaining nodes is $0$).

Lonely cycle was hugeeeee pre-processing for me. Too me 2 days to get the idea and another hour to get it working.

Interactive matrix was fun and a nice mix. Although the distribution of problem in divisions tell me it was solved by more people than intended, but loved this question nonetheless :)

Princess was a huge pain. Spent first day thinking its 2nd easiest question T_T

(13 Aug, 17:28) vijju123 ♦♦5★

Can you provide proof for that your interactive matrix solution will yield answer in less than 4N questions?

(13 Aug, 20:46) pshishod26454★
1

According to my calculations, it's (25/8)*N queries on average.

You can have a look here, https://drive.google.com/open?id=1UqZF6zDOYlLcEtrPkMWjpJuUbeQXfWut

(13 Aug, 23:25) forgotter5★

I'm talking of worst case..

(14 Aug, 01:24) pshishod26454★

Worst-case, it'll require (3/16)NN + 2N queries. Since the query if for a random cell of all probable cells in grid, consider the situation where each cell is of form (1,2),(1,3),(1,4)...then (2,3),(2,4) and so on.

Then the better approach will be of binary search, and that will take around (2N+ NlogN) queries, if everything is kept simple.

But often probabilistic methods are fast enough and rather than thinking about worst case, expected value should be seen.

(14 Aug, 08:29) forgotter5★

Interactive Matrix can be solved in O(log n^2) equivalent to O(log n).

First given a column we must be able to the identify the range in which the values are lesser than V (target value). This can be done using binary search.Take the first and last element of the column,identify whether its increasing or decreasing and perform binary search appropriately.Similar thing can be done to find range in which the values are greater than V.If the ranges are not complementary(that is union of them is not the superset) then the target is present in the column between these two ranges.So answer if found .From now on I would refer this functionality as range finder.

Now using rangefinder find out the ranges in first and last column. Let range(row numbers) lesser than V in first column be [il1,ir1] and last column be [iln,irn]. Similarly the range greater than V in first column be [gl1,gr1] and last column be [gln,grn]. We can clearly see that half of our search space can be clearly discarded. only two parts can have the solution. First part is intersection of [il1,ir1] and [gln,grn] and all these rows contain values in increasing order.Now using range finder find the ranges in mid column only for this intersection of rows.Now in range where value is less than v we need to search right and for range value greater than v we need to search left(because rows are sorted ascending).

That is we split the rectangle under consideration into four parts and discard two parts. Its easy to see that the discarded portion is half the original rectangle. We can repeat the same for these smaller rectangles and as well as the second part(but here rows are sorted descending).

Complexity analysis So initially we had square of size n^2,then we discard half the space,so in the next space we search (n^2)/2 then (n^2)/4 . So the complexity is O(log (n^2)) which is O(log n).

link

answered 14 Aug, 17:20

murugappan_s's gravatar image

5★murugappan_s
734
accept rate: 25%

edited 14 Aug, 17:22

For all those wondering why their solution fails for lonely cycle.

Try this input:

1
14 14
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 5
6 8
6 9
8 10
10 11
11 12
12 13
13 14

Output should be: 1 1 2 2 11 14 7 2 25 9 24 21 16 9

link
This answer is marked "community wiki".

answered 14 Aug, 00:16

forgotter's gravatar image

5★forgotter
2024
accept rate: 0%

1

this case contains 15 edges but the value of m you have given is 14 :|

(15 Aug, 02:21) pshishod26454★

Thanks for pointing it out.

That shouldn't be a problem earlier too since input was only till 14 edges and a single case was there.

(19 Aug, 19:04) forgotter5★

A nice set of problems, looking forward to the editorials :)
My only complaint: I would have preferred a more approachable challenge problem, especially since the other problems were harder than usual. A challenge problem is usually fun and something I turn to and try to optimize whenever I am stuck with the other problems. But this is just my opinion, others may disagree.

link

answered 13 Aug, 19:13

meooow's gravatar image

6★meooow ♦
7.0k717
accept rate: 48%

True. I tried so hard but it seemed like writing a barely working code for challenge problem was a challenge indeed!!

(13 Aug, 19:37) vijju123 ♦♦5★

Two 'alternative' approaches to solve Interactive Matrix:

  1. Write a function which takes a row index as input and searches for the key in that particular row. To reduce the number of queries, design a small 'value predictor' function which attempts to calculate the minimum and maximum possible value of the cell (i, j). Query Chefina only if the value to be searched lies within the predicted value range.
    Now, select random row indices, and feed it to the above function (YES, random rows, because quite obviously, one cannot completely the search the matrix using this approach; therefore, "take a chance").
    Solution link: https://www.codechef.com/viewsolution/19605485

  2. Well, there is always an option to implement binary search in real life... Search through the first 400 rows and note down the test cases passed. Then search through the first 200 rows and repeat the same, until you obtain the set of row indices which might contain the key. During the final run, search through these obtained row indices only. Solution link: https://www.codechef.com/viewsolution/19620555 Take a look at this solution and admire the effort put behind it...

link

answered 13 Aug, 19:37

sarthakmanna's gravatar image

6★sarthakmanna
946115
accept rate: 39%

edited 13 Aug, 19:41

1

LOL. I used your approach one except for my search function (which selected rows to search) involved statistics and interval heuristics. I thought it was dumb of me to get AC that way but now I'm feeling good :3

(13 Aug, 21:43) vijju123 ♦♦5★
1

@avijit_agarwal after solving INMAT: link

(13 Aug, 23:44) meooow ♦6★

For K-Compressed problem, I thought it could be solved using topological sort. Think about it as there is an edge from smaller vertex to larger, in subarray. Vertex with 0 inDegree is assigned currentNumber, and currentNumber is incremented on each iteration. Vertex with same values are assigned together.

Got 40 Points. Turns out Segment Tree is the answer ¯\(ツ)

link

answered 13 Aug, 16:51

njkevlani's gravatar image

4★njkevlani
1
accept rate: 0%

If you look at the question from direction of "Ok, how do I make the sequence B" you get the problem reduced to "You need to find maximum element in given range to assign correct value to $B_i$". This gave a big hint of seg tree for me.

(13 Aug, 16:58) vijju123 ♦♦5★
1

I would argue that segment tree is not the answer, it is only the means to calculate the cost for a particular $K$ quickly. The crucial part here is binary search.

(13 Aug, 19:01) meooow ♦6★

A Lot of Programmers got 40 points for KCOMPRES.

I have used binary search+ max segment tree and I am not getting why my last test testcase of final subtask Failing!

can anybody look into it

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

link

answered 13 Aug, 20:13

raman3217's gravatar image

5★raman3217
805
accept rate: 16%

edited 13 Aug, 20:14

Check out this type of case- [4,4,4,3,4,4,4]. For $K>0$ the sequence $B$ should be of form [2,2,2,1,2,2,2] instead of [1,1,2,1,2,2,2].

(13 Aug, 21:49) vijju123 ♦♦5★

I am also getting the same sequence for K>0 i.e [2,2,2,1,2,2,2]

(14 Aug, 11:35) raman32175★

GCDMOD overflows :/

I submitted it ~10 times in C++ trying out variations of bigint classes which all failed

Then I tried to implement it in Java with bigint(I've never used Java before :p) and that TLEd for the second and third subtasks

So I took the easy way out and stuck to Python

link

answered 13 Aug, 21:04

benritmico's gravatar image

4★benritmico
1
accept rate: 0%

My long long int passed fortunately xD

(14 Aug, 01:22) vijju123 ♦♦5★

For LONELY CYLCES I constructed a spanning tree of graph such that any edge which is not included in it connects u and v such that (lca(u, v) != u and lca(u, v) != v).

Then I marked all the edges which are part of cycles as blocked and which are not in spanning tree as red.

Then I just ran dfs to calculate the number of possible vertices I can reach from a given verices using dpdown - when I go down, dpup -> dp up taking care that I never visit more than 1 blocked edge.

Then calculated the answers for each type of edge, normal , red, blocked accordingly

I tried a lot of test cases and on each I was getting the right answer still got WA. If anybody can point out what I am missing..

My submission

link

answered 13 Aug, 21:05

pshishod2645's gravatar image

4★pshishod2645
815112
accept rate: 13%

In the princess and dragons problems can the values of the dragon strengths be negative?? I tried to solve the problem for the first 3 subtasks but got WA on the 2nd and 3rd but the first one passed. I am having this confusion because although it says the main constraint is 1≤Si≤105 but in the constraints of the subtask 3 which i got WA on says Si≤2,000 , nothing mentioned about the lower limit . Thank you .

link

answered 13 Aug, 21:09

battlejonin's gravatar image

3★battlejonin
1
accept rate: 0%

No, the main constraint said they will be greater than 1.

(13 Aug, 21:49) vijju123 ♦♦5★

I solved GCDMOD with a greedy approach, still cant prove that is right but i got AC A = gcd( a^n+b^n, |a-b| ) = gcd( a^n + b ^n , |a-b|, a^n - b ^n) : assume: a>b, if(a=b) its simple => A= gcd( 2a^n, 2 b^n, |a-b|) = gcd ( 2*gcd(a,b)^n, |a-b|) so now its simple

link

answered 13 Aug, 21:14

quy_tien's gravatar image

4★quy_tien
1
accept rate: 0%

We still have to find gcd of some x^n and |a-b|. How does this make it simpler? We still need to use the gcd(a, b) = gcd(b, a % b) property.

(17 Aug, 01:29) rashomon4★

I don't think this was the intended solution, but in the GCDMOD problem, we get the same answer whenever $n > 1$. If $n >= 2$, set $n = 2$ and print the answer directly. Only special case is $a == b$, in which the answer is $2 \times a^n$. Here's my AC Submission.
Can anyone prove why this works?

link

answered 13 Aug, 22:02

rahul_g's gravatar image

5★rahul_g
133
accept rate: 0%

edited 13 Aug, 22:10

This is simply not true: demo. Maybe there is a high probability of this and/or you got lucky.

(14 Aug, 02:53) meooow ♦6★

@meooow Then I must have got really lucky with those test cases :p Thank you for disproving!

(14 Aug, 14:32) rahul_g5★

Can the interactive matrix problem be solved by the following approach. First 2*n queries to determine the nature of the rows and columns(increasing or decreasing) Now, Select a mid=(l+r)/2; now in the column mid apply a binary search to find the range in which possible value of key can lie now in the row mid apply a binary search to find the range in which possible value of key can lie Select only those cells which are part of both row and column range and make a new matrix of only these cells. Continue the process till only 1 element exists.

Total queries =2n+1+lognlogn

link

answered 13 Aug, 22:25

sujeetsawala's gravatar image

3★sujeetsawala
1
accept rate: 0%

Seems promising but how will you exactly carry out this step-

now in the column mid apply a binary search to find the range in which possible value of key can lie now in the row mid apply a binary search to find the range in which possible value of key can lie

(14 Aug, 01:23) vijju123 ♦♦5★

Can someone please discuss their approach for princess and dragon problem? Thank you

link

answered 13 Aug, 23:21

nik_84's gravatar image

5★nik_84
536
accept rate: 0%

1

If the princess is in an end cave, then put the strongest dragons near the princess to defend on just one side. For this, sort the dragons into decreasing order, and find the number of dragons so total power is $\ge P$

If the princess is in the middle, then first put the strongest dragon in the princess's cave. Then find the smallest number $n$ so that the next $n$ strongest dragons can be split into two groups, one group each side, sufficient to defend the princess. This is a classic hard problem, but has a dynamic programming solution when the strengths are integers, and not too large.

(14 Aug, 02:22) john_smith_36★
1

I arrived at the same strategy, however I was unable to solve it. Can you provide any resources for the dynamic programming solution or explain it briefly?

(14 Aug, 02:25) meooow ♦6★

Yes that dp thing was deduced by me, that we need to split them such that sum of number of dragons on left and right is minimized. But even after lot of searching I was unable to find anything on it. Any resource will be really helpful!

(14 Aug, 03:19) vijju123 ♦♦5★

I also tried the similar approach of dp, first I found minimum numbers that can form p-(max) and remaining numbers in decreasing order but I found counter case for that. So messed up

(14 Aug, 09:56) nik_845★
1

Function count2b in https://www.codechef.com/viewsolution/19716800 gives the dynamic programming part of the solution.

Given a strong test case, it wouldn't be fast enough. But often a simple greedy allocation of dragons (function quick_count2) will show that the first $n$ dragons with combined strength $\ge 2P$ can be split into two sets, each with combined strength $\ge P$. If the greedy solution fails, I apply the dp algorithm.

(14 Aug, 11:44) john_smith_36★

For lonely cycle, I am not able to find a test case where my logic goes wrong... My submission is-submission

My logic goes as such... For each node x, I find in and out which are pairs... 1st index stores without cycle 2nd stores with cycle...in[x] means within the subtree of node x and also considering x... for this I merge its children's "in" values and also some node in its subtree from which there is back-edge to x.

Out[x] position means same as above...It means the nodes we can visit in the tree except its subtree but including the node itself...for this I merge its parent's out and also it's siblings in...Also in case of back-edge from x to some node higher in the dfs traversal tree, I merge its out...

For answer, consider for edge (a-b)

case (i):(a is dfs_par[b] or vice versa... and not part of same cycle) answer is (in[b])*(merge(out[a], sibling[b]))

case (ii):(neither is parent of other but are part of cycle connected by back-edge)answer is (in[b])*(out[a]) (consider a comes before b in dfs traversal)

link

answered 13 Aug, 23:52

v1a9r9u8n's gravatar image

5★v1a9r9u8n
42
accept rate: 0%

edited 13 Aug, 23:53

I'm not able to access LONCYC and KCOMPRES Editorials. @admin please help.

link

answered 14 Aug, 00:22

ankit_btech's gravatar image

3★ankit_btech
194
accept rate: 0%

Try tomorrow.

(14 Aug, 01:23) vijju123 ♦♦5★

Can anyone share their approach of solving Safe Partition ?

link

answered 14 Aug, 06:36

vivek_shah98's gravatar image

5★vivek_shah98
966
accept rate: 0%

Just noticed I spent almost 9 days on the princess and compression only. And I so much wanted to try both lonely cycles and myst. Shame on me. Not sure 10 days is short or I'm just too slow:P Princess sure was both annoying and enjoyable. I thought I had perfect solution for it but only got 10 points at first attempt(with 5 AC tasks). Putting princess with the most powerful dragon and creating main force most close to P and shortest with binary search, then backup force from remaining dragons. After lots of different approaches I added brute force for subtask 2 and got 20 points, and I was happy xD. Need to solve it again with the help of editorial to see what was my error.

link

answered 15 Aug, 16:41

tieros's gravatar image

4★tieros
734
accept rate: 12%

Just curious why I can't see "add new comment" button to reply other answers? Cause I'm kinda new here?

(15 Aug, 16:59) tieros4★

Need 50 karma for that.

(15 Aug, 18:48) vijju123 ♦♦5★

My solution is not working for SHKNUM ,for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013

link

answered 15 Aug, 19:01

ishan99's gravatar image

2★ishan99
11
accept rate: 0%

My solution is not working for SHKNUM ,for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013

link

answered 15 Aug, 19:01

ishan99's gravatar image

2★ishan99
11
accept rate: 0%

My solution is not working for SHKNUM ,for the last test case, kindly check it at https://www.codechef.com/viewsolution/19552013

link

answered 15 Aug, 19:01

ishan99's gravatar image

2★ishan99
11
accept rate: 0%

Please help me to find counter test case of my code of the problem KCOMPRES. Only two task remaining. My solution included segment tree approach. My Code

link

answered 15 Aug, 19:25

decentgeek's gravatar image

1★decentgeek
112
accept rate: 0%

My approach to INMAT was to use a 'quad search', which is a two-dimensional version of a binary search, where we search recursively one quadrant at a time. This took only a maximum of 0.04 seconds per test to earn 60 points. I expect that it took more than 4000 queries in some of the later test cases.

It looks as if the method needs polishing somehow, to reduce the number of queries.

Here is my code https://www.codechef.com/viewsolution/19740240

link

answered 16 Aug, 12:49

david_s's gravatar image

4★david_s
911
accept rate: 14%

I'll share my (partial) solution for princess and dragons that helped me get AC on sub-tasks 0,4,6,8.

You start by reverse sorting the strength array, and define the largest value as the anchor. For each i, let the dragon with the anchor strength be at the ith position.

For P <= anchor, output is n for each i. Similarly for sum-over-strengths < anchor, output is 0 for each i.

For other non-trivial cases you iterate over the reverse sorted strength array trying to form two groups of sets such that the sum of strengths in each group when added to the anchor is just larger than P. We do this such that the size of the first set is <= size of the second set. Here again we have two cases : (1) We are able to get both sets, (2) we are able to get only one set. Other cases are eliminated by the two trivial cases on the above paragraph. We should aim to find set 1 and set 2 such that they have minimum size, while their sum being larger than P.

For case (1): We keep the set 1(that has the smaller size) on such a side of the ith position that allows it protects maximum dragons after it. Hence, we keep the smaller set on the larger side(if it fits there). We then try to adjust the larger set after it, either on the smaller side or the larger side.

For case (2): We keep set 1 on the larger side of the ith position, again so that it protects maximum positions. If that is not possible we return a string of n 0's.

There are other subtleties too, such that the last element of the first set should be chosen such that the sum just equals P, and that we don't waste strength that can be used in set 2.

Although this approach works for larger test-cases, it couldn't even clear the smaller sub-tasks and hence I think I'm missing some conceptual point here that was tested in some test cases.

You can check my final code here : https://www.codechef.com/viewsolution/19707035

link

answered 17 Aug, 03:38

adi_ahuja's gravatar image

3★adi_ahuja
11
accept rate: 0%

edited 17 Aug, 03:39

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:

×196
×150

question asked: 13 Aug, 16:27

question was seen: 2,438 times

last updated: 19 Aug, 19:03