Karavaiev's blog

By Karavaiev, history, 4 years ago, In English

1388A - Captain Flint and Crew Recruitment

Idea: Denisov

Tutorial
Solution (Karavaev1101)

1388B - Captain Flint and a Long Voyage

Idea: Karavaiev

Tutorial
Solution (Karavaev1101)

1388C - Uncle Bogdan and Country Happiness

Idea: Karavaiev

Tutorial
Solution (Karavaev1101)

1388D - Captain Flint and Treasure

Idea: Denisov

Tutorial
Solution (Denisov)
Solution (Karavaev1101)

1388E - Uncle Bogdan and Projections

Idea: perekopskiy

Tutorial
Solution (perekopskiy)
  • Vote: I like it
  • +245
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +60 Vote: I do not like it

Thanks for the quick editorial!

»
4 years ago, # |
Rev. 4   Vote: I like it +207 Vote: I do not like it

Feel free to downvote, but this is my honest opinion; Personally, I think that the grammar of problem C made it abit annoying to understand.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Agreed. If not for the notes, I probably would have wasted a lot of time understanding the statement.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +17 Vote: I do not like it

      Yup, I don't mean to complain, but statements similar to these felt somewhat distracting-> "Every person has its own mood: somebody leaves his workplace in good mood but somebody are already in bad mood."

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        Totally disagree. You can of course point out a few subtle grammar mistakes, but they don't obscure the general idea.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    was writing " was made it a bit annoying" on purpose? If so, it's funny. If not, it's sad XD

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Lengthy background but interesting problems.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    I agree. you know most of the participants mother language isn't english and they can't get the statement easily, when you make the statement hard to understand, it will be really hard for them and sometimes they just skip the problem and lose it points because they can't understand the statement, and that will give them a really bad point at the contest. so please take more care for the statements.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes, I totally agree with you. As I am not a native English speaker or a native Russian speaker(I am Chinese), for some problems the statement is very difficult to understand(QAQ) and extremely complicated, although the statement itself is quite easy.

»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Lol I was in bad mood after reading the long statement of C. Missed it by one case

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D--can anyone please explain or give a test case where my solution is going wrong. The testcases in problem are too big to debug.

Here is the link to my submission.

I am bascially making a directed graph where an edge from u to v denotes that operation on u-th element must be done before v-th element of the array a. Then I am running a dfs on transpose of this graph and updating all elements(suppose v-th and w-th index element needs to be operated before u-th element, then updating a[u]=a[v]+a[w]) and adding those to answer while maintaing this order.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Your solution fails on that test case:

    test
    Answer

    Your solution works that way because after doing some operations $$$a_{b_i}$$$ can become positive and you can improve other $$$a_j$$$ using that $$$a_{b_i}$$$

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      How to solve D if we remove additional constraint ( if Cycle is there ) ?

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Would anybody help me with Question D?
My submission --> 88521832.
Approach: I made a 2D array of row size n to see whether there is any index that must be ahead than index i(0<=i<n). And then I just simulated for indices based on the array to determine the answer.
Variables: a and b are input array, c is array to determine which indices should come prior index i. array d is for storing the answer array. ans is calculated based on d. s is just counter to see all n indices are in d. every array is 0-indexed.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I'm sorry that my English is not very well.

    There's a situation in the process of Adding $$$a_i$$$ to $$$a_{b_i}$$$ that it may change $$$a_{b_i}$$$ from negative to positive.In this situation,if $$$b_{a_{b_i}}$$$ doesn't equal to $$$-1$$$,it should be also ahead some than some index.But it seems that you didn't manage to do this.

    Note that there's a principle that no matter what $$$b_i$$$ is,we should always put the index with $$$a_i > 0$$$ ahead of the index with $$$a_i < 0$$$.

    there's a sample that your algorithm makes mistakes:

    Input

    3

    -2 -1 4

    -1 1 2

    Output

    8

    3 2 1

    But your output is:

    5

    1 3 2

    Hope my reply could help you.

»
4 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Video solution of the whole problemset

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why don`t topological sort works in D?88526038

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I solved this problem using topological sort. You can check my submission.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    here's my AC submission with topological sort -> 88536305

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can You Explain it.

      How are you maintaining the last sequence ? UPD: I got it.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    Performing the operation on any ai < 0 before any aj > 0 may decrease the maximum sum, right?

    That's why you have to perform the operation on those positions at last (from bottom to top in topological order, so that it won't affect any ai < 0 too), so that it won't affect the maximum sum.

    My submission using topsort

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    In fact,the solution by Karavaev1101 is topological sort,though it's hard to tell.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It's my 2nd contest.I solved a no. problem.But still no rating given.How long does it take to get ratings after a contest is finished?

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

In my humble opinion problem set was amazing, but problem B was made a lot obvious by the example input, it could have been swapped with problem A if problem A constraints were made a bit tighter and brute force was not allowed.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Hey I think prob A was very easy...

    I mean just look at the code, it's basic brute force...

    ll n;
    cin >> n;
    if(n<=30) cout << "NO" << endl;
    else
    {
    	if((n-30)==6 || (n-30)==10 || (n-30)==14)
    	{
    		cout << "YES" << endl;
    		cout << 6 << " " << 10 << " " << 15 << " " << (n-31) << endl;
    	}
    	else
    	{
    		cout << "YES" << endl;
    		cout << 6 << " " << 10 << " " << 14 << " " << n-30 << endl;
    	}
    }
    

    ``

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah isn't B also a relatively basic observation.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yeah sure but I missed a very important line NOTE resulting in my WA twice and then I was able to get it right...XD

        Because of that I missed problem C.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          hello, in problem B if I have n = 5 then the number must be 9 9 9 9 9

          • in binary : 1001 1001 1001 1001 1001

          • but after removing last 5 digits then it become

          • 1001 1001 1001 100- ----

          • which makes it a 4 digit number, so making that 5 digit number I need to make it all 0s :

          • 1001 1001 1001 1000 0000

          • but this doesn't the case.

          • Can anyone help me with that ?

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Why do you think 0's binary is considered 0000? Why not 0000000000000 or anything else? Answer this and you'll get your answer as well.

»
4 years ago, # |
  Vote: I like it +55 Vote: I do not like it

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    did u know, you wasted 61 seconds in this counting!! lol :>

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

what kind of error is it "wrong output format Unexpected end of file — int32 expected" ? i did not see before . 88520911

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The grader was expecting more numbers(int32) in the output, but your solution did not print them. Check if you are printing the required output in the specified format. You can check my submission for more clarity.

»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Great round, guys!

»
4 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

In problem C How can (av+hv)/2 count the number of people in a good mode?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    suppose X are the people that were happy at city A and Y were the people that were not happy at the same city. Then X+Y = total citizens that visited the city(total citizens in subtree of that city). X-Y = (happy-sad) given for city. Add both equations and get the value of X which is same as described in the editorial.Hope you understand.

    Edit- by happy i mean good mood as in problem statement.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Honestly I didn't solve it like that, but I'll explain.
    Think that moods are G good and Y bad, in a city with P people. Do you agree that P == G + |Y|? Do you agree that H = G — |Y| ?
    Then P + H = G + |Y| + G — |Y| = 2G, and we are done.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    let gv be the number of people in a good mood that passes through node v, and bv the number of people in a bad mood. With that we can write the following system of equations: gv-bv = hv and gv+bv = av. If we sum the both equations we get 2gv = av + hv and thus gv = (ah+hv)/2

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Me to the second question :: WHy you do this to me????? :(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1388/submission/88510199 whats wrong with this submission for C?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand, in problem E — isn't there an easier way to calculate the projections? I don't know what the Convext Hull Trick is, but I mean, you have the angle and you have the height, that should be enough. Is the problem the fact that there could be error in the calculation and you will get a wrong result?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's a problem that you can't project every segment for every angle because it takes too much time, so we need to find the rightmost and leftmost projections quickly

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If you calculate the projection of $$$O(n)$$$ vectors for each possible angle (there are $$$O(n^2)$$$ of them) the complexity becomes $$$O(n^3)$$$.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ahhhh never mind I completely missed something. I thought the "no go" zones make a full range [theta1,theta2], and then you are left with only 2 angles to check. I understand now that there could be many options.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      By merging overlapping angle segments, it is possible to pass the time limit via this brute force method.

      88545255

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here I am generating a ton of primes and trying to do sliding window 3 sum with prefix sum to solve 2A and still couldn't. :(

RIP rating. I'm sad.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I also had a sad story but it turned out ok.
    At first I read the problem as "multiple" instead of "sum". I solved it though xD
    You just need the prime factorization and you need to pair up 3 pairs of different primes. (8 * 3 * 5 * 7 ==>> 2*3, 2*3, 2*5). (That made me 15 minutes behind :| )

    Edit: I need to start making it a priority to look at the god damn sample cases to verify I read the problem correctly.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My video solutions to problems A, B, C, D.

Enjoy watching.

https://youtu.be/0ExktAwScLc

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot!!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, that's weird, why your rating started from 0? (Normally it starts from 1500)

      Did I miss some updates?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Didn't got AC at C be cause I was using python. Rewrote it in C++ and got AC. Don't use python in recursion problems...

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    Look at my solution, I use this "boostrap" decorator that someone posted a while back (I use it all the time and it always works), that replaces the recursion.

    It looks like this:

    The bootstrap decorator
    My DFS

    Just notice —

    • To make the recursive call, you have to use yield.

    • When you call recursively, you can't do 'if yield dfs(..)' or stuff like that, you have to first save the value with 'x = yield dfs(...)'.

    • When you want to return something, you have to use yield (i.e., 'yield 5').

    • At the end of the function, if you return nothing, you have to use 'yield' with nothing after. THIS IS THE MOST IMPORTANT POINT. if you forget this you will spend eternity debugging.

    Thank me later.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Can we implement it in c++

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, you don't need it in c++... 10**5 recursion works fine for you.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          I just wanna try, how to replace the *args thing what is that??

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it -11 Vote: I do not like it

            Lol you will literally not be able to do that, You have to implement a generator and I have no idea how you could do that in cpp.

            There's a reason python exists. One of those reasons is that you can do stuff like this in less than 1000 lines of code.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find the missing case here in my submission of problem C? I am unable to find the corner case here:My Submission

Thanks in advance

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had the same idea as the tutorial for problem no C, don't know where I messed up. :(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My friend who got into coding tried CF for first time and he received RE on both of his solutions, while locally it worked. As I'm not familiar with python, can somebody explain what is wrong? Thanks

submissions: https://codeforces.net/contest/1388/submission/88484222, https://codeforces.net/contest/1388/submission/88506487

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    'input' doesn't work like that. First of all, input is a function, so it should be 'input()'.
    Second of all, it only reads one line.
    To get a line with an int you do int(input()).
    To get a list you do [int(x) for x in input().strip().split()] or list(map(int,input().strip().split())) or some other way.

»
4 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Can anybody please tell me where am I going wrong. Thanks in advance here B, G is no.of people in a bad and good mood respectively

Code

Update : I am dumb

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem c, i checked if(abs(h[i])>count[i] || count[i]%2 != abs(h[i])%2 ) then its not possible where count[i] = number of people visiting that node and h[i] = happiness value of i node.the second condition ensures that for a node with count = 5,the possible hvalues are -5,-3,-1,1,3,5 only.can anyone tell me why is it wrong? https://codeforces.net/contest/1388/submission/88539137

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have only checked the upper limit i.e. abs(h[i])>count[i]. There will be a lower limit as well. suppose there are 2 cities i and j with i being the parent of j. now, let count be the number of people visiting j. Then let x be the the number of people with good mood and y be people with bad mood. Clearly , x+y=count and x-y = h[i].From here you can get x and y. Now , for the city i, the range would be [x-y,x+y].Because, There must be atleast x people with good mood. If you want the sol , refer to — 88508137

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone please explain why in Problem D we reverse the second array ( the array with -ve elements ).

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

For problem E, the leftmost/rightmost segments can be handled in a similar manner as the "feasible angles" approach, by sequentially "trimming" the ranges where each of the $$$n$$$ segments is the leftmost/rightmost one.

Code (sorry for too few newlines)

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone please tell me? In solution of C, how g[v]=(a[v]+h[v])/2 ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    g[v](which is total good mood persons passes through vertex v)...................... calculate it through this given happiness index and no. of people passes. now the happiness index will be (acc. to question) (g[v]-(a[v]-g[v])),where (a[v]-g[v]) is sad people passes. hope u got it

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    let $$$b_v$$$ be the number of people who visited city $$$v$$$ in a bad mood then $$$h_v = g_v - b_v,\,a_v = g_v + b_v$$$, and $$$\frac{a_v + h_v}{2} = \frac{g_v + b_v + g_v - b_v}{2} = g_v$$$

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried C with a little different approach. I calculated the number of people who travelled through a particular node with dfs and then applied bfs to check if the sum of unhappy people in children should be more than or equal to the number of unhappy people who travelled through the ancestor. I cannot figure out my error. A little help will go a long way. Code

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    It is not not necessary that sum of unhappy people in children should be more than or equal to the number of unhappy people who travelled through the ancestor because some of the unhappy people might live in the ancestor city.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the tutorial. I really need this to improve myself.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ok, during contest my solution for B was correct but now its showing TLE but if i submit it again it got accepted what is happening, here are both submissions TLE submission AC submission

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I am not sure but it has something to do with dynamic strings you are using, in first submission you code might have encounter memory issues. like you are making a string of size (maxN). when ever you push a char into it. string needs a contiguous free space to instert if it is not there then string will move the whole string to a place where memory is available. and this operation takes O(n) time to execute.

    that means complexity of your code could have crossed $$$N^2$$$ in this way on multiple occassions.

    look at this submission : https://codeforces.net/contest/1388/submission/88556412

    code

    in this code i reserved a contiguous memory space of N for my string at very first. and look it only took 30ms to execute while your code did same in ~1000ms.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah but time limit was 2 sec. i get the point that it is O(N*N) because i am coping the string every time like s=s+'9' every time s is copied here in right side of operator. and also after the contest same code at test case 7 run in around 600ms and the other TLE solution(same code during contest) run for >2000ms thats what i am asking i mean why is this happening just to be safe from next time. and btw thanks for reply.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        so s = s + '9'; this statement can run in either $$$O(1)$$$ time or $$$O(n)$$$ time. if memory is available it will run $$$O(1)$$$ time, but if mmemory not available in contiguous manner in memory this statement will take $$$O(n)$$$ as i said it will copy the whole string to a place in memory where is avalable.

        so it is not truly $$$O(n^2)$$$.

        it depends on the collsions (when contiguous memory is not available and compiler will perform $$$O(n)$$$ operation.) and your code at the time of contest got more collisions than when you ran it after contest.

        it might have something to do with may be that memory is under more demand during a contest in comparison to after contest.

        if your code's string get assigned a memory place from which a contiguous space which required is available in that your code will run in 30ms.

        If you want to be safe from next time then becareful while using dynamic memory allocations. and reserver memory before hand as much required in one statement. like most common mistakes like these are using unordered_map. link. https://www.geeksforgeeks.org/unordered_map-reserve-in-c-stl/

        i have a friend who uses char arrays instead of string to be extra safe.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice problems.. Short solutions... quick editorial.. :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This link is my submission to question C of yesterday's contest. Could someone please help by pointing out where am I going wrong?

Thanks in advance

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In Problem C, you guys gave the necessary conditions with simple proofs, but what is the proof that these conditions are sufficient??

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C i checked for each node whether the number of happy people in that city is less than or equal to its parent node.Can someone tell why this approach is giving wrong answer?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    You should check sum of happy people in all children of a parent is less than or equal to happy people of parent as happy people cannot increase.

    But in your approach happy people can increase.

    Take example A is parent and B,C,D are children. Happy at A=6, Happy at B=5, Happy at C=5, Happy at D=5. In this case your all conditions are satisfied and answer should be yes according to you but answer is no.

    In this situation you see that happy people at parent is 6. But moving ahead happy people increases it becomes 5*3=15 at children. It means bad mood people are decreasing that is not the answer to this question.

    That is why your answer is giving wrong answer.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Got it.Thank you for helping.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah its fine bro. I also did similar mistake hence i thought to reply as its a learning platform and we can learn only by helping others and taking help from others.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1388/submission/88555647

can anyone help me with this solution for problem D?

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

C question was awesome, it helped me revise all concepts of dfs.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For question D, the dfs solution given in the editorial doesn't always work, since the starting point is random with straightforward dfs.

It seems to fail for —

3
1 -5 6
-1 3 2

expected — 9 given — 8

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    no it is not.

    we are only starting from the leaves. and that is the logic.

    Explain how is your expected result is 9?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The editorial solution (dfs) doesn't seem to enforce the condition that we should start from leaves. Like in the example that I have given, I ran it and the output was 8. But if we enforce the condition, it would have been 9.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i don't see how you are getting 9..?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        because your test case is too small here are possible answers to you test case

        1 2 3 = -3

        1 3 2 = 8

        2 1 3 = -3

        2 3 1 = -3

        3 1 2 = 8

        3 2 1 = 8

        there is no 9.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It seems that test

    test

    is incorrect because we have cycle $$$2, 3,2$$$ and the addition constraint says that the graph doesn't contain any cycle.

    In my solutition starting point can be any vertex, but I create graph with different from the editorial edges: from $$$b_i$$$ to $$$i$$$. The solution of Karavaiev is written in the same way as editorial.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      In Karavaiev solution you should change (int sum) to (ll sum) and (int a[N]) to (ll a[N]) and it will pass all the tests.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Actually, there is #define int long long in his code :)

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Yeah, sorry, didn't notice that)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have joke for question C but I am not in good mood to tell. :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, the number we are expected to find should be as small as possible, and r, as big as possible. So if the input is say 11, should the answer not be 99999999800 instead of 99999999888?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    by adding 0's at last you are not agreeing with the maximum possible value for r , You can do better with adding 8 instead !Try it out on paper

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Remember that each digit will be converted to binary first and only then we remove N binary digits from the resulting string.

    So the idea is to maximize the number of binary digits, that's why we only use number 8 and 9 in our answer, because they are the only decimal digits that, when converted to binary, have 4 digits (1000 and 1001, respectively).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me out with the Problem C, here is my solution, I used the similar idea as described in the tutorial, but used a different approach for implementaion.

My approach

I dont know where I messed up. Can someone please help. My submission

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

So many contests in the contest list but no div3 :(

I am eagerly waiting for a div3 after so many difficult contests. Just to gain some confidence :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone suggest a test case where my solution fails 88565587

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In problem C, if I am not incorrect, $$$to_1, to_2, …, to_k$$$ for city $$$v$$$ are the cities belonging to the subtree of the node which city $$$v$$$ belongs to. So, the third condition states that among such cities, sum of number of happy people entering each city must be less than or equal to the number of happy people entering the city $$$v$$$. Can someone please explain this condition? What I think is that for the happy people getting off at some city $$$to_i$$$, they will be counted every time they visit a city which is on their way home. So how is this repetition avoided?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Well, I have another approach if anyone is interested.

    we will have two arrays one of positive count(person who ended up happy in subtree) and one of a negative_count(person who ended up sad in subtree)

    apply dfs

    condition
    adjust

    When You are at a node then sum the number of positive_count and negative_count in the subtree. check the condition (it is possible to get the required happiness at this node) and if it is possible then adjust the value and update the positive and negative count at that node.

    code 88577713

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly, it didn't make sense to me,too

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's only for immediate children. They are not considering all the children in the subtree.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nobody cares what a pupil thinks, but i'll drop it anyway. I say you are correct, we are counting duplicates as well, but here's my thinking. Consider a number of happy people in node i. Now from node i, consider we can move down to three nodes, i+1,i+2,i+3. Now, the child nodes will have a "subtree sum" of their own. now assume this to be some s1,s2,s3. Now, how did we get these many people in those subtrees? It is only because they travelled through the parents node, i. So now we can see that when you add the sum of good people from all three subtrees, to the parent node, It should be strictly greater than the sum of the individual subtree sum of their chidlren. (since that node must have 0 or more happy people) so s>=s1+s2+s3.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone please help why am I getting a WA on problem D on test-7. Link to my submission Thanks in advance :)

UPD- I got the mistake.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone need Detail Explanation(not a video tutorial) of C Here

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the solution of E in tutorial? I see most of the solution use trisection search. Is the tutorial also use the trisection search? Forgive my terrible understanding of the code in tutorial.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem A: It is said to print "4 different positive integers", but why one of those 4 positive integers can not be zero ('0')? Where is the range is mentioned? Please help me to understand the constraint. Thank you.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Karavaiev (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C was such a good problem even though I participated virtually and solved it 10 minutes after the contest. I did not read the question properly and missed the point that once the person becomes sad cannot become happy again.

It would have been better (easier) C if this was not the condition.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WHAT SHOULD I DO NOT TO GET RATING IN CONTEST?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hello, in problem B if I have n = 5 then the number must be 9 9 9 9 9

  • in binary : 1001 1001 1001 1001 1001

  • but after removing last 5 digits then it become

  • 1001 1001 1001 100- ----

  • which makes it a 4 digit number, so making that 5 digit number I need to make it all 0s :

  • 1001 1001 1001 1000 0000

  • but this doesn't the case.

  • Can anyone help me with that ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How will the last digit be Zero. zero has a single digit representation in Binary.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay but why should be 8 ?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        could you elaborate a bit .

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          because we want a number with 4 bit binary representation. That way, our number will be maximum. We have only two options for this. 8 or 9.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            why not nine ? I got that 0 cannot be the answer but not getting that how 8 (1000) fixes in the answer ? can you please explain the above example n = 5?

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Why not nine? because 99...8 is smaller than 99...9 Read the problem again, They both give same answer unless n%4=0 for n=5
              1001 1001 1001 1001 1001
              Why not your logic?
              1001 1001 1001 100,1 1001
              You're gonna remove everything after the comma. So if you're gonna remove it anyway, you might as well make it as small as possible.
              1001 1001 1001 100,0 1000
              Notice that in this way, all digits are still 4 bit and it is also smaller than all 9's

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I have an alternate solution for problem D . First transform the array b into a forest of directed trees with all edges away from the root by drawing edges from vertex x to b[x] when b[x]!=-1 (the nodes with b[x]= -1 will be the roots of the respective trees of the forest). Now, run a dfs from the root of each tree and for every node x, calculate a value say sum[x] such that sum[x] is equal to (sum of max(sum[z],0) for all children z of x) plus a[x]. The sum of sum[x] for all nodes of the forest is the required answer.

Also construct an auxiliary graph such that if sum[x]>0 draw a directed edge from x to b[x], otherwise draw an edge from b[x] to x(provided b[x]!=-1) . Sort the vertices in this graph topologically to get the permutation. 88585416

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I solved C a bit differently. I used the name $$$liv$$$ instead of $$$p$$$ to indicate resident number of a node. For every node $$$v$$$, I maintained a range $$$[L_v, R_v]$$$ in which it's happiness index must lie. Thus, $$$L_v\leq h_v\leq R_v$$$ For a leaf, the range is $$$[-liv_v, liv_v]$$$.

Now, a node $$$v$$$ returns a different range for the residents of $$$v$$$ who started the journey from $$$par_v$$$. Notice that this range will be $$$[h_v, R_v]$$$, because if happiness in $$$v$$$ is $$$h_v$$$, then it was at least $$$h_v$$$ on its parent, with the possibility that it might be as high as $$$R_v$$$ ( Mind that one's mood gets bad only on the road AND the unhappy people never improve their mood ). Also, $$$R_v-h_v$$$ has to be even, by the definition of happiness index.

For an intermediate node $$$u$$$ and $$$v$$$ $$$\epsilon$$$ $$$children(u)$$$, $$$[L_u, R_u] = [-liv_u+\sum_{}L_v, liv_u+\sum_{}R_v]$$$. Because the lower limit for $$$u$$$ can be as low as "everyone's" lower limit, including itself. Same goes for the upper limit. Return the range $$$[h_u, R_u]$$$ with appropriate checking as mentioned above. if you get a valid range at the root, it's ok. Otherwise the machine has error and print NO.

My submission 88504884

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem C, can someone provide a test case where my solution fails.

I have added appropriate comments to my code for better readability.

Please help!

Spoiler
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think your definition of $$$a$$$ and $$$b$$$ in $$$dfs2$$$ function is wrong. In $$$pto_v$$$, you have basically the number of people that have ever passed node $$$v$$$, right? Then what does pto[p]+hp[p] even mean?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      pto[p] is what you have said. hp[p] is the given happiness of the city (i.e given as input).

      Even the tutorial has this formula. I cannot understand what is wrong with pto[p]+hp[p].

      Can you please elucidate a bit more?

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        I see. Your code comment was misleading. $$$a$$$ and $$$b$$$ were $$$2$$$ times of happy and sad people respectively, though it will eventually be true a little later. Anyways, in that case, I'd want to ask you, what does your dfs2 actually do? What I think is that it returns how many happy people have reached some node. In that case, you should return $$$a$$$, not $$$a+sum$$$ ! The $$$sum$$$ is needed to check any discrepancy at the children, but it shouldn't be added. In fact, I just submitted your code with return a; in dfs2 and got AC. Maybe you were "too lucky" to get past this many testcases.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, I forgot to mention that a and b are twice of happy and sad people respectively (usual stupidity that I do, sorry)

          I was not able to enforce the necessary conditions in dfs1, so I wrote dfs2 to declutter my code.

          Extremely grateful to you for going through my code and pointing the error. Now, I understand what was wrong with my code.

          Thanks a lot again.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help please Problem D https://codeforces.net/contest/1388/submission/88590473 checkler log is showing sequence have duplicates.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the 'else' in the 'while', you need to lower the indegree of brr[ind] (not only inside the if, but also in the else).

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank You very much. You have saved me a lot of time. Thanks again

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain me if there were cycles in D, how to calculate the maximum value in the cycle after removing all non cyclic elements? (in O(n))

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Congratulations to adedalic for amazing coordination of this round!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me clarify my doubt:

In the second question (B) since we are asked to output the smallest value of x such that r is maximized after removing last n digits, so why the answer is not like this if n = 5 then x minimum x can be 99980 but the correct output is 99988 the value of k will be the same in both cases k = 100110011001100 and 99980 less than 99988 then why the answer is 99988. please explain to me if I am wrong or the question is cause i was stuck on second problem and then i lost hope and stopped attempting further.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What makes you think 0 can be represented as '0000' instead of straightforwardly as '0' !

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but if we cannot use zero still then our answer can end with one like for n = 5, k is same for 99981 and 99988

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, if you use any other digit that 8 or 9 the resulting binary string will be shorter.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Dude, binary of 1 to 7 is three digits, its that straightforward, it can't be greater than 8 or 9.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, Would anybody help me with Question C?

This is my submission. https://codeforces.net/contest/1388/submission/88520244

My way of approaching the problem is the same as the editorial except I calculate number of bad people instead of the number of good people.

My submission is wrong at the 27th input of the 3rd Test Case.

Thanks for the help.

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Try this test case 1

    3 14 
    2 4 8 
    14 4 8 
    1 2 
    1 3
    

    The answer is "NO" Because the total sum of good people cities 2 and 3 is 12.

    amount of good people in city 1 is 8.

    the statement says that we can't increase the number of good people.

    (srry if my english is not so good)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      My submission is "YES". But I think the answer is "YES" also

      Because happiness in city 1 is 14 and there is 14 people visit city 1. so number of good people = (14+14)/2 = 14 people. The number of good people leaving city 1 is 12 (14 — 2(people staying in city 1)). The total sum of good people in cities 2 and 3 is 12 which is (=) the number of good people leaving city 1. So the number of good people did not increase.

      Do I have any misunderstanding on the problem? Thanks for your reply and kindness.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Try this test

        2 5
        2 3
        -1 3
        1 2
        

        Answer must be no. 3 bad and 2 good people at vertex 1. h[1] = -1, OK. 3 bad people will visit vertex 2. h[2] must be -3. Therefor answer is NO

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ok Yes, that's it. I am wrong because I ignore all the vertex that has 1 connected vertex when I consider the 3rd Criteria. (All the leaf of the tree are of the size 1) But I forget that vertex 1 can be size of 1 too.

          Thanks a lot for your help and kindness.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

88635193 Can you explain why my code fails? my contest submission was -- 88482149, I know in the contest submission I did a calc error but the idea of my solution was the same, but after rectifying the calc error it's still showing wrong answer. Though it's written if there are multiple answers we can print any of them.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for condition a==44 you have used 13 as one of the number which is incorrect because 13 is itself a prime number.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I thought about it but in the question says

      Captain Flint guessed an integer n and asked you: can you represent it as the sum of 4 different positive integers where at least 3 of them should be nearly prime.

      where they said 3 of them should be nearly prime rest can be a distinct integer apart from these 3. Maybe I got the question wrong but the above lines I directly copied from the question.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It literally tells you "wrong answer Sum of numbers is not equal to n (test case 4)". Test case 4 is n=36.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      88635193 my solution was 15 10 6 5. where 3 of them are nearly prime 15,10 and 6

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Do you know what "Sum of numbers is not equal to n" means?

        Edit: now I see that n=36 is fixed in that code; you should actually submit it to the correct problem.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        first of all this is your code for 1st task and submission on 2nd task. you are seeing jury's answer as your answer.Your answer is the participant's output

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hello, i am a newbie in coding and I didn't understand how problem D is connected to graphs. Can anyone tell me what's the idea/algorithm behind this question. Should I be knowing something before trying this question??

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    the values of b array were forming a chain(that is b was connected to the index in a and further the value of b in the new index was connected to some other index of a) and to solve such chaining question we can use graphs.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could someone explain why does the following code for problem C gives WA ? I am not able to find any substantial difference between this code and the official solution's code.. In particular, it will be nice to have someone give me a test-case where my code fails. Also please do let me know if anything is unclear in my code; I will explain what I intend to do using that particular instruction.

Code
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Can someone explain me what's the difference in the logic of my submission please? I have been trying to figure it out for a while but am not able to find any difference, so could someone tell me please ? In particular, my code seems to fail on the 27th test case of the 3rd test, but I am unable to view this, so could someone at least tell me what this test case is ?

    Thanks in advance!

    UPD: I found the mistake — a really stupid one. Instead of keeping sum <= good[v], I kept sum<= peo[v], a big overlook!

    Sorry for pestering anyone who intended to help me.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how can i find answers of all the proplems ?(sorry if my English is bad)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    if the editorial is not good enough you can check submissions by other competitors

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think in the editorial for problem B it should read "at most 4*p-3" instead of "at least 4*p-3"

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, shouldn't this give a wrong answer?? I didn't check if number of people in good mood in a city are non-negative.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's wrong with my solution? I used BFS two times.

1) Operate on the nodes that are +ve or become +ve while traversal, from top to bottom. Mark them.

2) Operate on the remaining negative nodes. From bottom to top

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

can anyone check and help me understand why memory limit is exceeded in my solution for problem C 89311627

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 1388C — Uncle Bogdan and Country Happiness, consider the 3rd condition:

gto1+gto2+…+gtok ≤ gv, where to1, to2, …, tok are the cities where the resident can move out of the city v on the way home.

Shouldn't we compare gto1+gto2+…+gtok with number of happy (in good mood) people leaving the city v instead of comparing gto1+gto2+…+gtok with gv (number of people in a good mood who visit the city v = number of people in good mood passing through city v + number of people in a good mood who live in city v), to ensure no one becomes happy during the journey.

»
4 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Nice problems except for the long essays here

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have solved problem D using the concept of topological sort order in DAG. You may have a look at the tutorial that I have written for this problem in my blog, Link.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D: 279808093 — is causing a WA7 due to wrong output format Unexpected end of file — int32 expected.

It worked fine for larger inputs in Tests 4, 5 and 6. But for some reason fails on 7, could someone help me debug the code?