Karavaev1101's blog

By Karavaev1101, history, 11 days ago, In English,

1388A - Captain Flint and Crew Recruitment

Idea: Denisov

Tutorial
Solution (Karavaev1101)

1388B - Captain Flint and a Long Voyage

Idea: Karavaev1101

Tutorial
Solution (Karavaev1101)

1388C - Uncle Bogdan and Country Happiness

Idea: Karavaev1101

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
  • +252
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +60 Vote: I do not like it

Thanks for the quick editorial!

»
11 days 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.

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days 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."

      • »
        »
        »
        »
        11 days 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.

  • »
    »
    11 days 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

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

    Lengthy background but interesting problems.

  • »
    »
    11 days 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.

    • »
      »
      »
      8 days 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.

»
11 days 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

»
11 days 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.

  • »
    »
    11 days 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}$$$

»
11 days 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.

  • »
    »
    11 days 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.

»
11 days ago, # |
  Vote: I like it -42 Vote: I do not like it

Video solution of the whole problemset

»
11 days ago, # |
  Vote: I like it -42 Vote: I do not like it

[unbalanced]

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

Why don`t topological sort works in D?88526038

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

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

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

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

    • »
      »
      »
      11 days 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.

  • »
    »
    11 days 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

  • »
    »
    11 days 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.

»
11 days 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?

»
11 days ago, # |
Rev. 2   Vote: I like it -52 Vote: I do not like it

I am sorry but Problem B was just Horrible. Why the fuck am I sorry, It was fucking' horrible. Yuck.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe you could have put your opinion in a constructive manner

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 3   Vote: I like it -44 Vote: I do not like it

      not really in the mood man... somedays you just wanna let out...but I mean no hate...

»
11 days 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.

  • »
    »
    11 days 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;
    	}
    }
    

    ``

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah isn't B also a relatively basic observation.

      • »
        »
        »
        »
        11 days 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.

        • »
          »
          »
          »
          »
          11 days 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 ?

          • »
            »
            »
            »
            »
            »
            11 days 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.

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

            Hey,

            The number must be 99988 for n=5 because you have to select the minimum possible number. It's binary form is

            1001 1001 1001 1000 1000

            Now, you might select 99980 as minimum but I made the same mistake for the first time and then I read the note given in the Que saying that 1000 is greater than 0000 so you have to select the greater bit possessing but lower value having number so 99988 is correct.

            Now removing the last 5 bits, we get 1001 1001 1001 0100 which makes it 9994 which is the maximum number possible. Got my point?

»
11 days ago, # |
  Vote: I like it +55 Vote: I do not like it

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

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

»
11 days 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

  • »
    »
    11 days 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.

»
11 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Great round, guys!

»
11 days 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?

  • »
    »
    11 days 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.

  • »
    »
    11 days 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.

  • »
    »
    11 days 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

»
11 days ago, # |
  Vote: I like it -7 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1388/submission/88534351 What is wrong in this submission of C? I think I have considered all the cases but still, it is failing test 4. Great Contest, thanks!

»
11 days 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?

  • »
    »
    11 days 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

  • »
    »
    11 days 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)$$$.

    • »
      »
      »
      11 days 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.

    • »
      »
      »
      11 days 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

»
11 days 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.

  • »
    »
    11 days 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.

»
11 days 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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot!!

    • »
      »
      »
      11 days 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?

»
11 days 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...

  • »
    »
    11 days 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.

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

      Can we implement it in c++

      • »
        »
        »
        »
        11 days 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.

        • »
          »
          »
          »
          »
          11 days 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??

          • »
            »
            »
            »
            »
            »
            11 days 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.

»
11 days 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

»
11 days 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. :(

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same happended with me i just missed an edge case ..it feels bad

»
11 days 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.com/contest/1388/submission/88484222, https://codeforces.com/contest/1388/submission/88506487

  • »
    »
    11 days 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.

»
11 days 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

»
11 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Check out the video editorial of Problem D

»
11 days 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.com/contest/1388/submission/88539137

  • »
    »
    11 days 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

»
11 days 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 ).

»
11 days 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)

»
11 days 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 ?

  • »
    »
    11 days 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

  • »
    »
    11 days 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$$$

»
11 days 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

  • »
    »
    11 days 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.

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

Can someone plz give me an example in problem c where 3rd condition is not satisfied and other 2 condition are satisfied.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do i see variables written twice in B ?

»
11 days 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

  • »
    »
    11 days 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.com/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.

    • »
      »
      »
      10 days 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.

      • »
        »
        »
        »
        7 days 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.

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
11 days 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

»
11 days 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??

»
11 days 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?

  • »
    »
    11 days 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.

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

      Got it.Thank you for helping.

      • »
        »
        »
        »
        11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

can anyone help me with this solution for problem D?

»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
11 days 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

  • »
    »
    11 days 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?

    • »
      »
      »
      11 days 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.

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        11 days 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.

  • »
    »
    11 days 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 Karavaev1101 is written in the same way as editorial.

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

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

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

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

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

          Yeah, sorry, didn't notice that)

»
11 days 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. :)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Contest Great Editorial! thanks, everyone!

»
11 days 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?

  • »
    »
    11 days 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

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The zeros are not included in r, those bits are only considered in the number k. If we had to maximise k, I understand, and would have made all the 0's as 8 in my number x. But if we are able to achieve a smaller value of the number x, with the same number of digits as expected, while keeping r maximum, then it does not make sense to make 99999999800 as 99999999888, right?

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This would work if we wrote a 0 in decimal as "0000" when making k. But, in the problem statement it is given that there should be no leading zeros while appending the binary of a number in k. For eg: Consider n=2: if x =98, k = 10011000 if x = 90, k = 10010 Adding zero will result in addition of a single digit in k. But if you add 8, you will add 4 digits and therefore r will be bigger. Hope this helps :)

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          "This would work if we wrote a 0 in decimal as "0000" when making k"

          Understood where I was wrong right after I read that line, thank you @AbishekSeshen .

  • »
    »
    11 days 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).

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i am not able to understand if "4p-3" digits are removed what does this mean?

»
11 days 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

»
11 days 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 :)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone suggest a test case where my solution fails 88565587

»
11 days 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?

  • »
    »
    11 days 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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 days 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.

»
11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how max can be max achieved by removing 4.p — 3 digit from the end acc to tutorial can some one please explain

»
11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i didnt understand the solution for D. i am fairly new to STL, could anyone help?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please provide an edge test case for problem C. My code is failing test case 3, at only one place.

Here is the link to the code : https://codeforces.com/contest/1388/submission/88578851

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

WHAT SHOULD I DO NOT TO GET RATING IN CONTEST?

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

    Solve it virtually.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but what if i realise during contest that my rating will go down ,then what should i do not to get rating?

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Until you submit the solution for any of the problems the contest will not be rated.

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you hit a single submission the round will become rated for u.So, before submitting decide if you want to take the shot.

»
11 days 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 ?

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay but why should be 8 ?

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        could you elaborate a bit .

        • »
          »
          »
          »
          »
          11 days 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.

          • »
            »
            »
            »
            »
            »
            11 days 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?

            • »
              »
              »
              »
              »
              »
              »
              11 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Because if we have 9 then the number won't be minimum anymore. we want the smallest number which can achieve the highest value after the erase.and if the number is going to be erase then why not let it be 8 rather than 9.

            • »
              »
              »
              »
              »
              »
              »
              11 days 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

              • »
                »
                »
                »
                »
                »
                »
                »
                11 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                great explained thank u

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain to me why I am getting the wrong answer on test case 3? Here's my code. Please note that n1 is for good people and n2 is for bad people. For every city, I am checking whether the number of good and bad people are greater than 0. Can anyone give to me a counterexample? Thanks in advance.

»
11 days 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

»
11 days 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

»
11 days 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
  • »
    »
    11 days 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?

    • »
      »
      »
      11 days 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?

      • »
        »
        »
        »
        10 days 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.

        • »
          »
          »
          »
          »
          10 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 days 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).

    • »
      »
      »
      10 days 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

»
11 days 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))

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain me when will to== ancestor??

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got my ans. I misunderstood.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I too have this doubt,what's the use of ancestor,I made a directed graph from u->v whenever u<v but it was not passing on test 4.Surprisingly on making the graph undirected and adding ancestor condition gives an AC.Somebody Please explain.

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

      to== ancestor satisfies when we find the parent node As child, in that case we just need to skip that node and continue with next node. Ex. 1 -> 2,3,4 and 2 -> 1,5 When we check for 2 then the child of 2 is 1 which is also parent so we need to skip. For directed graph please show me your code.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got it.Thanks,for the explanantion.for directed graph just realised u->v will not work as root might be connected to a node with greater value which in turn can be connected to a smaller value node like 1->5->2.I was presuming it to be connected in increasing order and then forming a graph.

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

comment deleted by the user

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Not able to figure out why my C submission for test case 4 is giving wrong answer. code. Can someone please help in this.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the editorial for problem C ?

»
10 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Congratulations to adedalic for amazing coordination of this round!

»
10 days 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.

  • »
    »
    10 days 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' !

    • »
      »
      »
      10 days 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

      • »
        »
        »
        »
        10 days 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.

      • »
        »
        »
        »
        10 days 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.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, only the numbers from 4 to 7 have 3 digits in binary.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            My bad. The point was though that as we have to maximize 'r' we have to take digits with longest binary and 1 to 7 are only upto 3 digits in long binary, so we choose 8 and 9.

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

            Anyway, could you please explain the editorial for problem C ? I am having difficulty in following it.

»
10 days 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.com/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.

  • »
    »
    10 days 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)

    • »
      »
      »
      10 days 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.

      • »
        »
        »
        »
        10 days 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

        • »
          »
          »
          »
          »
          10 days 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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain, what's wrong with my submission if I use number of unhappy people instead of happy people for the problem C. Here is my code https://ideone.com/x1fXgM

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi tried 4th problem with topological sort, WA on 7th test case. couldn't figure out. Can somebody help Your text to link here...

»
10 days 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.

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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.

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You submitted code of A in instead of B

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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

      • »
        »
        »
        »
        10 days 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.

      • »
        »
        »
        »
        10 days 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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel problem C was easy ,but it's framing was not proper.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried Problem 3 but even with the help of the tutorial I can't get it. Can someone help me? Submission: 88639704.

Also I am just learning so any tips in optimizations / better practices / faster ways to write are all appreciated! Thanks!

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

.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The difficulty of problem C was just higher than expected as in normal div2 rounds bcoz of the question framing

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was not the usual Div. 2 problem. How many of you support this!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C. Let x be the total number of people crossing a city v. Answer is yes if:

  1. Parity of x == parity of abs(h[v])
  2. abs(h[v]) <= x

Otherwise no. Why doesn't this work?

»
10 days 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??

  • »
    »
    10 days 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.

»
9 days 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
  • »
    »
    7 days 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.

»
7 days 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)

  • »
    »
    6 days 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

»
6 days 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"

»
6 days 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.

»
5 days 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

»
3 days 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