Endagorion's blog

By Endagorion, history, 2 months ago, In English,

Thank you for waiting! I hope you've enjoyed the problems. Let me know what you think in the comments!

UPD: I almost forgot but here are some notes, as well as challenges for all problems. For a lot of them I don't have a solution and would be happy to hear your ideas.

Tutorial is loading...
Challenge (awful)
Tutorial is loading...
Challenge (?)
Notes
Tutorial is loading...
Challenge (probably doable)
Tutorial is loading...
Challenge (?)
Tutorial is loading...
Challenge (???)
Notes
Tutorial is loading...
Challenge (probably doable)
Tutorial is loading...
Challenge (?)
Notes
Tutorial is loading...
Challenge (running out of ideas)
 
 
 
 
  • Vote: I like it
  • +335
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

In 1368A;C+= a=5, b=4,n=100 why the output is 7??

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it
    0 a=5 b=4
    1 a=5 b=9
    2 a=14 b=9
    3 a=14 b=23
    4 a=37 b=23
    5 a=37 b=60
    6 a=97 b=60
    7 a=97 b=157
    Hope that helped.
    
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -27 Vote: I do not like it
    [problem:1368A]
    so here a = 5, b = 4 and n = 100
    STEP 1: b < a, therefore, a remains 5, b becomes b+a which is 9
    STEP 2: a < b, therefore, b remains 9, a becomes a+b which is 14 
    and so-on
    **1**
    **5 4 100**
    - a=5,b=9   ------> 1
    - a=14,b=9  ------> 2
    - a=14,b=23 ------> 3
    - a=37,b=23 ------> 4
    - a=37,b=60 ------> 5
    - a=97,b=60 ------> 6
    - a=97,b=157 -----> 7  (here b became greater than n which is 100, so we break )
    **7**
    
    
    #include<bits/stdc++.h>
    using namespace std;
    
    int main() {
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	int t;
    	cin >> t;
    	while(t--) {
    		long long a,b,n;
    		cin >> a >> b >> n;
    		int cnt = 0;
    		while(max(a,b) <= n)  {
    			if(a < b) a += b;
    			else b += a;
    			cnt += 1;
    		}
    		cout << cnt << endl;
    	}
    	
    	return 0;
    }
    
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

      Can you explain me the algorithm for codeforces sequences?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -22 Vote: I do not like it
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Please give feedback on my video.

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +15 Vote: I do not like it

      The explanation is awesome. I don't know why so much negative review on it .

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

Can someone please explain the problem B solution ? I am not able to get from editorial.

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

    For simplicity, consider 'abc' subsequences. An optimal string would look like aa...abb...bcc...c. The number of 'abc' subsequences in this string is = count('a') * count('b') * count('c').

    We need to find these counts such that their product >= k while also minimizing the string length. This can be achieved if the counts are as equal as possible (this is just greedy, you can try out some examples). So we can initialize the counts to 0 and increment the counts by 1 in cyclic order until product becomes >= k.

    For example, if k = 18, a possible solution could be 3, 3, 2 and the string would be 'aaabbbcc'.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same thing i tried it contest as well but I could implement this well. Mean my approach was right in contest :) Thanks man. cheers

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I couldn't solve it during contest either, even my approach was wrong. We all have bad days.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks coderfool for the clear explanation. Could you please explain the case when the string has duplicates?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ask with a testcase. That will be helpful to understand your question. If you are asking for case like: "aaabcdef" solution will be the same. Whenever you are appending some character you have to append it continuously.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's easy! Consider duplicate letters seperate and go as u did in the non duplicate string. I guess it would be the approach

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro check if this helps,

      For each addition of a char this is the max subsequecnes you can get ,

      inc -- 0 — 1

      1 — pow(1,9) * pow(2,1) ( this means 1 character have freq = 2, 9 charcter has freq 1)

      2 — pow(1,8) * pow(2,2) ( this means 2 character have freq = 2, 8 charcter has freq 1)

      3 — pow(1,7) * pow(2,3) ( this means 3 character have freq = 2, 7 charcter has freq 1) ...

      10 — pow(2,10) — 1024

      11 — pow(2,9) * pow(3,1) = 1536 ( this means 9 character have freq = 2, 1 charcter has freq 3)

      12 — pow(2,8) * pow(3,2) = — ( this means 8 character have freq = 2, 2 charcter has freq 3) ....

      20 — pow(2,0) * pow(3,10) . . . . do this till you get pow(40,10) = 1.04 * pow(40,10)...

      now store these values in an array.
      this describes the distribution of charcters in your answer.

      once you get k, find smallest value >= k,

      print according to its distribution.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had the same approach. I am hoping 84242551 will help.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        https://codeforces.com/contest/1368/submission/84326989 can you look at this code? I wrote it after understanding your approach, yet it is failing on test case 3. I think it is because of the way i am calculating product. Can you please check this?

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You need to account for previous value of a[count] which was included in the product. For example, suppose value of a[0] was 2. And now you increment it to 3. While calculating new product,you'll first divide product by previous value of a[0],i.e, 2 and then multiply it by 3.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It is because you need to find the product everytime you increment a[count%10]. Why? Let's take an example. Suppose your array looks like this: {2,2,2,2,2,2,2,2,2,2}.

          Current prod = 2^10.

          Now in the next step, you change array[0] to 3. The array now looks like this: {3,2,2,2,2,2,2,2,2,2} According to your code, the new prod is 2^10 * 3. But actually, it should be 2^9 * 3.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try This video Solution: — https://youtu.be/xpFsAU4wTLg

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

Great contest! Though, I had a doubt regarding a different version of B, which I initially misunderstood the question for. What will we do when we will want exactly k subsequences? (Assuming that an O(N^(1/2)) solution is good enough) Can we simply keep on multiplying the count of a letter by the smallest prime factor of the remaining k(dividing k at each step) and then move on to the next letter(of the cycle) and keep on doing so until k=1?

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

    I misunderstood the question during my first try. I thought that we have to find exactly K subsequences. So I calculate all the prime factors of the given number, multiplying the count of a character by the prime factor in a circular manner. I think this will be the optimal answer. You can check my wrong submission if you want to have a look.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, but my question’s if your method is right for the question you miasassumed at first!

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

      Circular manner won't work. If the count of all the prime factors (multiset) is greater than 10 then we must keep multiplying the smallest two numbers and replace them with the product, untill the size of our multiset is exactly 10. And in case if the size was less than 10, then add the required number of 1s in it.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It makes much sense now thanks

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Are you sure about this or we have to apply some sort of dp to calculate the minimum sum of number, multiplication of those lead to k?

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think so, this should work. Take an example:

          k = 2*2*3*5*7 String = abc

          So, we want 3 integers, such that their product is k and their sum is minimum possible.

          Multiplying 2 and 2 gives us k = 3*4*5*7 Multiplying 3 and 4 gives us k = 5*7*12

          Length of the string = (5+7+12) = 24. This is the best answer we can achieve.

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            In k = 2 * 2 * 3 * 5 * 7 we can multiply 5 * 2 = 10 and 3 * 2 = 6 so our final result is 6 * 7 * 10 = 23 is the minimum answer

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh then my approach is wrong . We'll have to find another way to minimise the sum

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I think the only way is now using dynamic programming. I will try to find the solution using dp.

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

    O(N^(1/2)) solution does not exist let alone good enough. If I give you a prime number K > 1e9 then you would have no choice but to print exactly K of any letter in "codeforces". The only prime factor of K is itself. Other than that I think Akshay has a correct solution.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Right, thanks!

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

      It is wrong. You have to take a min heap and multiply the two smallest element until the size of heap is greater than 10.

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

Btw, there is an extra challenge for problem B. (I wrote about it as my puzzle.)

As mentioned in the editorial, the approach may not work well for subsequence other than "ABCDE" and "CODEFORCES". Could you find such string?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Take str as “well” and k=3. “welll” should suffice here, but according the aforementioned algorithm, we have to use “wellll” which isn’t optimal

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep, that will do (tho the original algorithm will have "wweell" instead).

      Any idea if two adjacent letter must be different? :)

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

        Take the string as "abcbc" and k=5. Now, according to the algorithm we have "aabbccbc". But, due to the repeated sequence of "bc", we can take the string as "abcbcbc"(which has just two characters extra). This will give us exactly 5 subsequences of "abcbc".

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In your example,There are 5 subsequences instead of 6

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

            You're right. I'll correct it at once. Taking k=5, the counter example still holds!

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

        On the string "codeforces" the algorithm will work but what should be done if we had a same question with any string in general?

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I made a video explaining problem D because I really liked the problem — https://www.youtube.com/watch?v=oHgcHjk2fIM

There are many people with these videos, so let me know if it's worth doing more, thanks!

(Well, I liked problem E too, but I didn't solve it during the contest!)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    here, when you got the final 0, 0, 6, 7, 7 what was the original input array for this, please.

    LarryNY

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

The 'smaller value of k' leads one to think, the question requires the minimum value of k in Problem C. Otherwise a good problem set!

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

Are the rating changes adjusted for the fact that this was open for both div. 1 and div. 2? Personally it felt a bit unfair as difference between d and e was huge and i saw many expert coders who got under 2000 but still had negative rating change. Doesn't it discourage div. 2 coders not to participate in combined rounds?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Cause they are very close to Div1((1880-1899) what I found in rate changes). They are in top 2000, but for them, it is not good enough.

»
2 months ago, # |
Rev. 2   Vote: I like it -47 Vote: I do not like it

fast

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

"We divide them into three sets $$$V_0$$$, $$$V_1$$$, $$$V_2$$$."

How?

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

    Look at tourist's solution : 84233462, if path[u] is 0, u is in V0, if path[u] is 1, u is in V1, if path[u] is 2(later -1, for generalizing max operation), it is in V2.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Among other things, he sorts the the vertex by label. Why? What is the meaning (in words) of path[]? More formally, what have the labels of the vertex to do with the solution? Or more common, what is the idea of this solution?

      I completly do not get it.

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

        He sorted the adjacency list g, but did not use it(he used gr instead). So, My guess would be that it was contained in his previous solution, and hence has no use. Also, note that he uses reversed graph to like relax every node on the basis of incoming paths(and not outgoing paths).

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The idea part:

        1. After relaxing every vertex u, path[u] can only contain one of {-1, 0, 1}(Already denoting three sets {V2, V0, V1} respectively).

        2. Notice that he is using reversed graph(for incoming edges).

        3. He is relaxing in topological order(from 0 to n-1) in gr(and not g).

        4. For a vertex 'v' if all the vertices 'u', which have a an outgoing edge to 'v'(i.e 'u' ---> 'v'), are deleted(i.e they are in V2 or their path[u] is equal to -1). In this case, maximum incoming path length to 'v' is 0, hence it should be in V0.

        5. For a vertex 'v' if it has an edge incoming from a vertex in V0 and no incoming edge from vertices V1, it means that the maximum length path to 'v' is 1, and hence should be in V1.

        6. For a vertex 'v' if it has an incoming edge from any vertex from V1, then max path length upto 'v' is 2, and hence should be in V2(deleted).

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

    You can traverse them in topological order and assign each vertex distance mod 3. let say dist[i] represents distance of ith vertex mod 3,

    for all adjacent vertices j, dist[j] = max(dist[j],(dist[i] + 1)%3)

    V2 is the set of vertices with dist[i] = 2,

    My submission

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

what is contribution in profiles?

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

For B: We need to minimise the length of string or sum of count of individual characters considering characters at different positions as different.

length of codeforces = 10;

for k upto 1024 we can have count of individual occurrences of letters as no more than 2. After 1024, It should be pow(3,x)*pow(2,10-x) where x is the first x letters of string codeforces.

Or In genereal It will always be like pow(n,x)*pow(n-1,10-x) should be just greater than or equal to k.

for k = 1 print("codeforces").

Hence step 1 : figure out smallest n such that pow(n,10) is just greater or equal to k.

step 2 : figure out smallest x;such that pow(n,x)*pow(n-1,10-x) just greater or equal to k.

Implementaion

I really hope It helps :),Good Day!

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

problem D was beautiful.And the part which i liked about the contest is you have to come up with a solution after that coding part is really easy and short.

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

In problem 5 what does "in topological order" means and in which set a vertex with no incoming edge belong to ?

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

Can Someone please explain E in a simpler fashion?

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

    In E, we can make a directed graph with given nodes and edges. Here I will call a closed node as deactivated and an open node as activated.

    So, a node 'x' will be activated if none of its activated parent nodes are having any activated parent , otherwise it will be deactivated. (Greedily)

    Now suppose there are y activated nodes whose parents are also activated. No. of distinct parents they have must be greater than (y/2) (As each node has atmost 2 children).

    Now no. of distinct child they can have is 2*y.

    So for y + (y/2) = (3*y/2) activated nodes we can have at max 2*y (All childs) deactivated nodes.

    So for total (3*y/2) + 2*y = (7*y/2) nodes we can have at max 2*y deactivated nodes. Hence For n nodes we can have at max 2*(2/7)*n = (4*n/7) deactivated nodes

»
2 months ago, # |
  Vote: I like it -27 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand the meaning of the line "At that point, all numbers should be submasks of each other." (question D). An implementation of the solution will also be appreciated. Thanks.

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it
Your code here...
#include<bits/stdc++.h>
using namespace std;
 
int ADD(int a,int b,int c,int n)
{
    if(a>n||b>n)
    return c;
    if(a>b)
    return (a,a+b,c+1,n);
    if(b>a)
    return (a+b,b,c+1,n);
}
int main()
{
    int T,a,b,n,c;
    cin>>T;
    while(T--)
    {
        c=0;
        cin>>a>>b>>n;
        cout<<ADD(a,b,c,n)<<"\n";
    }
}

pls can anyone tell me whats wrong with my code?

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

Great editorial for problem F, Thanks!

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

I need help in understanding, why my E approach does not work. I kinda proved it should work under constraints (If it does what I want it to do).

Algorithm as follows : First you check for all nodes without incoming edges ($$$V_0$$$). Then you make a set of nodes that these nodes touch ($$$V_1$$$). Then make ($$$V_2$$$) out of those accordingly. ($$$V_0$$$) Will never be spoiled, because no edges enter them. But ($$$V_1$$$) might point to another ($$$V_1$$$), making it ($$$V_2$$$) maybe.

So I keep track of votes for being ($$$V_2$$$). votes = how many edges from ($$$V_1$$$) enter this node. Nodes with nonzero votes are the ones we remove. Now go from top to bottom, and if we meet some node that used to be ($$$V_1$$$) but got voted by someone else, I put it in ($$$V_2$$$) and undo its votes, since it does not count as good any more. Since I do this from top to bottom, I only take necessary nodes in greedy way.

The answer should give different combinations of binary trees that are less than 3 in depth, and all of them have number of bad nodes $$$\leq$$$ $$$\frac{4}{7}$$$, and each node can be associated with one such binary tree, so the answer must be also less than constraint.

After the cycle, we remove $$$V_0$$$ $$$V_1$$$ and $$$V_2$$$, also changing incoming nodes from $$$V_2$$$ since they touch the rest of the graph and continue till we have $$$V_0$$$ empty

Sumbission : 84272118

»
2 months ago, # |
  Vote: I like it -77 Vote: I do not like it

How is making a pattern a CP question?

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

https://codeforces.com/contest/1368/submission/84295929

I am not sure why this approach fails. i.e. — can't find a failing test case. The key idea is, anything with in degree > 0 cannot have an out degree > 0. And popping from a heap with decrease key, where the key is in-degree * out-degree

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

I had a doubt in Problem E. I tried solving it like this: Form the graph and remove only those vertices which have both incoming and outgoing edges. As I remove a vertex, I also update the graph accordingly. I tried to analyze the number of vertices that I will be required to remove in the worst case. For that, we can consider the whole graph as a binary tree and what my approach is doing is that it is removing all the vertices at even levels (considering 1 based indexing of levels). In this case, the maximum vertices that will be removed will be n/2 which is less than 4n/7. However, I am getting the wrong answer on Test Case 7. Can somebody give me a counter-example or tell me if I am making a mistake somewhere. Thank you. Here is my submission link: https://codeforces.com/contest/1368/submission/84306393

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

    But the whole graph is not a binary tree.

    The verdict of your submission is clear. You deleted 6 nodes in Case 137 of Test 7, while there are 10 nodes, so you can delete no more than 5.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the reply. Yeah, that is the issue, I am not able to understand how come the answer is exceeding n/2. I think I will have to work out some test cases to check that. I have not been able to find any test case that fails until now. If you have a test case that you can suggest, it would really help.

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

    1 — 5 1 — 6 2 — 7 2 — 8 3 — 10 3 — 9 5 — 11 6 — 11 7 — 11 8 — 11 9 — 11 10 — 11

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

    i also tried the same thing ....but later understood that in this case no. of deleted nodes is
    2*(n-1)/3 .. so it fails for n=10.

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

Thumps up for high quality descriptive editorial. By the way, in number c "The sample picture was a red herring". I stepped into that trap.

»
2 months ago, # |
  Vote: I like it +174 Vote: I do not like it

That feel when you AC C with an ugly solution...

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

can any one explain the question part in D??? it says:

 If before the operation ai=x, aj=y, then after the operation ai=x AND y, aj=x OR y, where AND and OR are bitwise AND and OR respectively
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    void operation(int& x, int& y) {
      int aux=x&y;
      y=x|y;
      x=aux;
    }
    ...
    operation(a[i],a[j]);
    ...
    
»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Beautiful solution for E.

Anyone know any algorithms for minimizing k, or interesting bounds on k for different constraints on the graph? Does this problem have an existing name in the literature?

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

What if in Problem C we have to print the smallest k satisfying the conditions? Any Ideas

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

"The same solution can be simply rephrased as: go from left to right, and remove current vertex if it is at the end of a two-edge path"

I am writing an explanation vis-a-vis the correlation of the sets $$$V_0, V_1, V_2$$$ to the above algorithm,

Let, $$$V_2$$$ represent the set of all the removed vertices.

Now, the vertices that only have incoming edges from $$$V_2$$$ are the "roots" of a sub-graph that has been disconnected from the initial graph, let they be represented by the set $$$V_0$$$, the vertices in $$$V_0$$$ no longer have any incoming edges, therefore, they can't possibly be the endpoints of a path of length 2 or more, so according to the algorithm they don't have to be removed.

Similarly, all the "neighbours" of the vertices in $$$V_0$$$ need not be removed (they are the endpoints of paths of length 1), these "neighbours" form the set $$$V_1$$$.

P.S after reading this you can refer to the editorial for the upper-bound on the number of elements in set $$$V_2$$$, it's exactly $$$4n/7$$$.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Now, the vertices that only have incoming edges from V2 are the "roots" of a sub-graph that has been disconnected from the initial graph, let they be represented by the set V0, the vertices in V0 no longer have any incoming edges, therefore, they can't possibly be the endpoints of a path of length 2 or more, so according to the algorithm they don't have to be removed.

    How can you guarantee that the vertices in V0 do not have tracks to each other?

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

An Interesting Problem:

In problem B Consider exactly k instead of at least k. I think it would be problem of finding number of factors <= 10 such that their sum is minimum. Prime value of k would be nightmare.

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

i'm a little confused about E, is it saying to just remove the node if it looks like this?

0 — 0 — 0

then remove middle to

0 — X — 0

cuz i think a lot of solutions failed that when trying to greedy like that

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

Hello. I need help in problem E. My submissions: this close more than 4/7 n vertices and this may leave tracks with a length of 2 or more . I found counter test where this submissions don't work. Is this possible in this task? Why my solutions work? This test  20 19

1 2

2 4

2 5

1 3

3 6

3 7

7 8

8 9

9 11

9 12

8 10

10 13

10 14

15 17

17 8

17 20

15 16

16 19

16 18

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

A simpler solution for E problem:

Let's invert all edges in the graph, then for each vertex in graph no more than two incoming edges. Also for each edge u -> v, u > v. We will iterate over the vertexes in ascending order and for each vertex we will check whether there is a path of length 2 from it through not deleted vertexes, if there is then we will delete this vertex.

Note that for each deleted vertex there is an edge to not deleted vertex, from which also exists edge to not deleted vertex. Since after we inverted the graph, each vertex contains no more than two incoming edges. Then each not deleted vertex contains a maximum two incoming edges from the deleted vertices, but at the same time for such vertex with incoming edges from deleted vertices there is an edge to not deleted vertex, which means that the number of deleted vertices <= 1/2(for 2 deleted vertices which have an edge to same not deleted vertex, exists 2 not deleted vertices)

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

    Here is the counterexample to your upper_bound = 1/2n.

    1
    7 6
    1 2
    1 5
    2 3
    2 4
    5 6
    5 7
    

    Your algorithm removes 4 vertices = 4*n/7.

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

In problem E: sample test case 1: if we close both 3 & 4 ,how will we reach 4 from 2 since 4 is closed so there should be no incoming edge on 4? Kindly explain sample test cases of Problem E ?

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

In E question : Can someone please explain how paths and tracks are different from each other and if suppose this is our graph:

1 2

1 3

2 4

does it mean that 1, 2 ,3, 4 are on the same line?

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

https://codeforces.com/contest/1368/submission/84323789 can anyone tell me why is TLE coming in testcase 2

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

    I had the same issue, you are initializing an array of size = 1e5, for every testcase, which is not necessary. Try using atmost linear space.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't find the editorial useful.

»
7 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Can anyone explain me the solution of Problem D elaborately. what's happening there ? I am unable to visualize it .

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can try

    For D we have to play with bits, That is when you and a ,b and simultaneously or a,b Total bits of a and b are preserved in the ored number that is a|b Thus when we have an array of numbers Out first priority is to set all the bits in some number because consecutive sum of squares of (2^n-1)^2+(2^n)^2. << (2^(n+1)-1)^2 By this observation I tried to accumulate available bits in only some of the numbers Not distribute it in all the numbers

    So we will accumulate the bits in only some numbers . rest all numbers can be 0 . Lets say we have 4 bits of 0th place , 4 bits at 1st place and 2 bits at 3rd place then in total we will try making 4 different numbers which are 11 11 3 3.

    And then finally we will find the square of these values. Carefully observe that by oring the bits and its frequencies are preserved. and by and the bits which are 1 in both the numbers stay preserved

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

      I appreciate your efforts but still i can't understand it ..

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Are you able to understand each of the following observations?

        1. Suppose w = x & y, z = x | y (where & is bitwise and, | is bitwise or). Then x + y = w + z
        2. w^2 + z^2 >= x^2 + y^2
        3. The sum a_1 + a_2 + ... a_n is unchanged by any operation

        If so, try to think about maximizing the sum of squares while maintaining the invariant from #3

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    total number of set bits in a particluar column will be same so in a number try to set all numbers in binary as 1,from the top; like this :- 1-001 3-011 5-101 in 1st column 1 bit set 2 unset , 2nd me 1set 2 unset in 3rd me all 3 are set thus rearrange it 111 001 001 total set bits will just be same in each column 001000011111 111100000000 000011111111 changes to 111111111111 000100011111 000000000000 total set bits in a column is to be conserved

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

It's a bit off topic but is there anyone solving problems using Node.js? For the problem number 2, i got wrong answer because of javascript's limitation of large numbers. How you guys handled this? Do anyone know why codeforces doesn't support BigInt of javascript?

Here is my js_solution

I've submitted the code using c++ and that got AC.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Why in E removing middle vertex in 2-edge path will not work?

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

    All of the middle vertices could have tracks to the same end vertices.

    Say you have this input

    1
    10 12
    1 4
    1 5
    2 6
    2 7
    3 8
    3 9
    4 10
    5 10
    6 10
    7 10
    8 10
    9 10
    

    Removing the middle vertices would remove 4, 5, 6, 7, 8, and 9. This would be 6/10 vertices removed, and 6/10 > 4/7.

    Worst case on that strategy approaches 2/3 with more nodes (need 1 first node for 2 middle nodes, only need 1 final node total)

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

In problem 5, Ski Accidents, What would the answer for this test case: 3 3
1 2
1 3
3 2
According to me, (4*3)/7 = 1, and by deleting any one node would satisfy conditions. That is, the answer should be 1 1, 1 2, or 1 3. But in most of the accepted solutions, it is showing 0 as the output answer. Am I right?
Even my accepted solution is also printing 0 as the answer.

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

    Sorry, my bad, x < y in every test case but test case I have given has x > y

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I spent two hours trying to solve B, for exactly k subsequences, before i realized i miss read the problem. Anybody has an idea on how to solve this variation of the problem ?

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

My Doubt is for Problem C. Can Anyone Explain the Meaning of this line in Problem Statement of C:

"There are exactly n gray cells with all gray neighbours. The number of other gray cells can be arbitrary (but reasonable, so that they can all be listed)."

What i Understood with this line is :

if n=1 then a grid of four cells Can be the Answer(because it is satisfying all three conditions)

I Know i am wrong somewhere,Can Anybody Point out the Catch i am losing!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, if $$$N = 1$$$, then the grid looks something like this:
    011
    111
    110
    where 1 represents gray cells. Here, only the middlemost cell $$$(2,2)$$$ [1-based indexing] has all gray neighbours. And notice all other gray cells have even neighbours. For extending to any arbitrary $$$N$$$, you can follow the pattern of editorial.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      According to your example ,

      The (1,1)Gray cell [1-Based indexing] is also surrounded by all gray neighbours and the number of neighbours are even too.Right?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, notice that grid is actually infinite, so a gray cell needs to be surrounded by gray cells in all 4 directions (sharing an edge).

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh! But According to this line in the problem statement,

          "assume that the sheet is provided with a Cartesian coordinate system such that one of the cells is chosen to be the origin (0,0), axes 0x and 0y are orthogonal and parallel to grid lines, and a unit step along any axis in any direction takes you to a neighbouring cell."

          I thought first cell would start from (0,0).

          This is a bit conflicting right? blitzitout

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Actually that thought never crossed my mind. The author mentioned that fact only when outputting the gray cells. But yes, you can clarify with the authors during the contest.

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

      Thanks for making this grid for N=1, this observation made me change what was wrong in my approach, and then it got accepted.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For the solution to D, it's written that x^y+xANDy=x+y. But when you set x = 3 and y = 5 for example, the equation becomes 6+1=8 which is incorrect. Can someone help me understand this claim? Thanks.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

guys could anyone explain problem e I still couldn't understand the tutorial

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I did problem A simply taking it as fibonacci style. As like in fibonacci 011235... I did it but first time i swapped a,b if a>b then did linear fibonacci since A is always easy ;)

a =5 b = 4 I made a=4 b=5, then it goes like fibonacci style,!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Though, I could clearly form an idea on C, I chose not to implement it. I hate those kind of problems.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me out why my approach for problem C is incorrect even if it is correct according to the first image of the editorial and gives answer with the minimum value of k.

https://codeforces.com/contest/1368/submission/84524694

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

Hi all, 1368D — AND, OR and square sum

Why?
2d(d+y−x), which is positive when d>0.

Thank you very much.

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

For the solution to F, I think $$$x + k + \dfrac{x + k}{k - 1} \leq n$$$ transforms into $$$x \leq n - k - \dfrac{n}{k}$$$, not $$$x \leq n - k - \dfrac{n}{k} + 1$$$?

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

    Endagorion Could you please answer this?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, you're right, I was off by one. The answer still stays the same since $$$x \leq n - k - \frac{n}{k}$$$ is applied immediately before $$$x$$$ can be increased, so it can be one larger in the very end.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

//problem b;

include

include

include

using namespace std;

int main()
{
   int k;
   cin>>k;
   string str;
   str="codeforces";
   int r=k%10;
   r=10-r+1;
   while(r<10)
   {
       str=str+ str[r];
       r++;
   }
  // r=k%10;
   int  n_10=k/10;
  
   while(n_10--){
       str=str+str;
   }
   
   
   r=k%10;
   
   if(r)
   {
        cout<<str<<endl;
   }
   else if(r==0)
   {
       
       str.erase(str.size()-1);
       cout<<str<<endl;
   }
  
   return 0;
}

**why this code give me MLE _**

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

Can anyone explain the side note for the editorial of problem D?

Side note: an easier (?) way to spot the same thing is to remember that f(x)=x2 is convex, thus moving two points on the parabola away from each other by the same amount increases the sum of values.

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

Where is the "Contest materials" in the contest page? There must be something wrong.