September Lunchtime Problem Discussion

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

2 Likes

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

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

Summary

CC problem setting these days.
Pick a trivial problem. Add meet in the middle flavour. Use it in contest.

4 Likes

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?

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?

can someone please help me, why the following code is giving WA for problem - https://www.codechef.com/LTIME76B/problems/WATCHFB :

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

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.

1 Like

can you please explain a little bit more?

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

4 Likes

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

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

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

Thank you!

1
bbd
aaabbbcccddd

Your code gives aaabbdbcccdd while correct answer is aaabbbdcccdd

2 Likes

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

1 Like

Connect u,v if cmp(u,v) returns true.
If this graph forms a DAG you can use it in buit sort.

1 Like

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

1
bba
aaabbbcccddd

Your code gives aabbbacccddd while correct answer is aabbabcccddd

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 https://codeforces.com/blog/entry/63533 for problems of this kind.

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