September Lunchtime Problem Discussion

1

for discussing the problems and solutions after the contest(10:30)
Please don’t discuss before that

2 Likes
2

good problems were there. I liked them. I might be 4 star after this. BTW, Fourth problem(All substring) was similar to this hackerearth circuits problem

3

how to solve TREEVERS and ICECREM(was it DP or meet in the middle)

4

(post deleted by author)

4 Likes
5

For TREEVERS I have seen your solution. Can you please explain how do you come up with that comparator?

It is trivial in case of two pairs but how did you generalize it?

6

How to approach the pair sum problem? I think it like if there are intermediate sum available then we can only find the required sum. But couldn’t implement it.
Is there any good approaches to solve these type of questions?

7

can someone please help me, why the following code is giving WA for problem - CodeChef: Practical coding for everyone :

for _ in range(int(input())):
    n = int(input())
    p,pa,pb = 2,0,0
    for _ in range(n):
        m,a,b = map(int,input().split())
        if m == 1:
            print('YES')
            p,pa,pb = m,a,b
        elif p == 2:
            if a==b:
                print('YES')
            else:
                print('NO')
            p,pa,pb = m,a,b
        else:
            if pa==pb:
                print('NO')
            elif (min(a,b) < max(pa,pb)) or (a==b):
                print('YES')
            else:
                print('NO')
            p,pa,pb = m,a,b
8

It’s basically sorting the points {subtree_0s[node],subtree_1s[node] } with their polar angle using cross product. This correspondence proves that such a comparator is valid i.e does not have any cycles.

9

can you please explain a little bit more?

10

why aren’t editorials put up immediately after the contest?

4 Likes
11

can you elaborate the meet in the middle strategy in this problem

12

Assuming you already knows meet in middle technique, the only thing we should focus is to how to merge the two parts.
Consider a possible arrangement in the left side, find the minimum waiting time (the time for which the next person has to wait) then on the right side store “the minimum time that one can wait (i.e. they can wait for this much more time)” and then simply we have to perform binary search on the right side.

Don’t know if I explain it clearly or not but you can ask if something is unclear.

1 Like
13

For all substrings problem,
which case am i missing?
https://www.codechef.com/viewsolution/26844377

Thank you!

14

1
bbd
aaabbbcccddd

Your code gives aaabbdbcccdd while correct answer is aaabbbdcccdd

2 Likes
15

Nice :ok_hand:t2:
(How you guys manage to get that :stuck_out_tongue:)

1 Like
17

Which case am I missing?
https://www.codechef.com/viewsolution/26840813

18

1
bba
aaabbbcccddd

Your code gives aabbbacccddd while correct answer is aabbabcccddd

19

If there are only 2 subtrees we check the sign of subtree_0s[u]*subtree_1s[v] - subtree_0s[v]*subtree_1s[u] .This is basically the crossproduct of the points {subtree_0s[node],subtree_1s[node] }. To generalise this for k subtrees we need to prove 2 things, first if there are 2 adjacent nodes which satisfy this then we can get a better answer by swapping them (this is obvious) and the comparator has to define order, [My interpretation of order is that if you form a directed graph using the comparator to decide the direction then it should be acyclic] ,this is true since the sign tells us the orientation of 2 points with respect to the first. See Lecture #3 — Exchange arguments (sorting with dp) - Codeforces for problems of this kind.

20

The same mistake which I did.:sweat_smile:
For the test case,
1
baa
aaabbbcccddd
The output given -
abbbaacccddd
Correct output-
abaabbcccddd

21

For all substrings I am getting partially correct answer. Can anybody tell me what I am missing?
my code link: CodeChef: Practical coding for everyone
Thank you in advance.