Ahmed_Hosssam's blog

By Ahmed_Hosssam, history, 2 months ago, In English

Here is the editorial. Please provide your feedback on each problem so that we can improve upon them the next time.

1670A - Prof. Slim

Tutorial
Solution

1670B - Dorms War

Tutorial
Solution

1670C - Where is the Pizza?

Tutorial
Solution

1670D - Very Suspicious

Tutorial
Solution

1670E - Hemose on the Tree

Tutorial
Solution

1670F - Jee, You See?

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +74
  • Vote: I do not like it

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

Feed back for C: While giving problems which require answer modulo p. Its good to provide 1 sample test where answer is greater than p so that we can understand that mod was wrong.

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

    In this particular problem the size of the array should have been at least 30 in order to have an answer that exceeds 1e9 + 7, this seems too large for samples.

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

can you provide c++ solutions?

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

My solution for Problem C shouldn't this give TLE because of memset, if t = 1e5?

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

Please provide your feedback on each problem so that we can improve upon them the next time.

My feedback on each problem

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

Apart from my stupidity on getting unnecessary wrong answers. The contest was interesting :).

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

A simple solution for D problem without binary search, exploiting the fact that for 3 types of lines the numbers should be as close as possible (+-1 difference)

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

Can someone please explain to me that why my solution is getting "time limit exceeded"? 156095877

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

    i think you can do something faster by doing bool isspecial[27] and check for them in O(1) instead of this "if s[i] in a:"

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

    I was facing the exact same issue. TLE on pretest 3. In fact, changing lookup to O(1) didn't fix it either.

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

    This problem has quite a huge input (3e5 lines) and output (1e5 lines) and output (1e5 lines)

    It seems it won't pass without optimizing on this level

    Lookup fast io in python or pypy

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

For D somehow this works

ans=ceil(sqrt(n/6.0)*3);
  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I was lucky to have found a similar formula and submit during contest.

    I am surprised this is not the solution used in the editorial.

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

Video Solutions for C,D,E

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

A great contest, thanks to the writers :)

I was really close to solving problem E during the contest. At first, I tried several approaches to choosing the root node, for instance, I have considered the node which is on the diameter of the tree, or the one which has the largest degree. But neither of them work.

I completely fell into the trap of this problem, since it asks to select one node as the root, and I believe that the root node must have some special properties, which should be the "key" to the final solution.

It is like 10 minutes before the end, I realized that we could always construct the tree to obtain "n" as the answer. I noticed that, except for "100..00", the other values could be divided into (n-1) pairs, (1xxx,0xxx), (1yyy,0yyy), and so on. We could always make the prefix XOR be less than or equal to "10000".

It is a pity that I didn't finish the codes before the end, but this problem is really exciting, especially that "trap". Hope that next time I could do better.

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

In editorial of D: In second para "Number of intersections" should be "number of intersections at center of some hexagon" as intersection on some vertex won't create any triangle

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

Can someone pls explain F a bit more (last line of third para "we only have to know the difference between the previous bits of X (add 1 if the current bit is on) and the sum of the generated bits.") I am unable to get it from the editorial.

thanks in advance.

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

I don't like the editorial for A

First it gives a claim without proof Then it has a solution that doesn't directly use this claim at all

"So let's say the number of negative elements is k. Then we must check that the first k elements are non-increasing and the remaining elements are non-decreasing." Why is it true? How does the solution use this fact?

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

    Notice that applying the operations doesn't change number of negative elements. When sorted all the negative elements should be before all the positive elements. So if there are k negatives then we need to make the first k elements negative. For negative numbers to be sorted the absolute values must be non increasing. For positive numbers it should be non decreasing.

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

can anyone explain why the code for the C question is getting WA on test case 8?

https://codeforces.com/contest/1670/submission/156185766

approach: if c[i] != 0 then c[i] = a[i] or b[i], but in front, we should not count a cycle that has a[i] or b[i], because we don't have any option, for this I am storing the values that cannot count in cycles in a set container.if(a[i] == b[i]) then also I inserted a[i] in the set. and while checking for no. of connected components I am checking whether the parent of i from 1 to n does not belong in the set.

Yes I know, I made my approach messy using a set, I can use a visited array instead, but in the contest, this approach got stuck in my mind, and cannot able to change it...but I wanted to know the reason why my approach is wrong...

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

    You're only checking the root is not in s. You need to make sure none of the children are in s as well.

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

      ya, you are correct, thank u !!

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

what's wrong with my solution for (B). It says time limit exceeded on test 35.

include <bits/stdc++.h>

using namespace std; int main() { long long t; cin>>t; while(t--) { char ch; long long arr[26]={0},n,val,max=0,ind,k,i,flg=0; cin>>n; string s; cin>>s>>k; while(k--){ cin>>ch; arr[ch-'a']=1; } for(i=0;i<n;i++) { if(arr[s[i]-'a']==1) { if(flg==0) {max=i;flg=1;} else if(i-ind>max) max=(i-ind); ind=i; } } cout<<max<<"\n"; } }

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

Can someone explain how https://codeforces.com/contest/1670/submission/156198034 this solution can not pass ?

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

To get the sum of the first X groups it will be 3X^2.

Again, such claims have to be proven

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

NVM. Figured it out

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

    You can’t use the parent array directly, use the find function instead.

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

      Yeah, just figured it out. Thanks :)

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

Nice round brothers, you are a source of pride <3

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

Can someone help me to figure out the what mistake I have done https://codeforces.com/contest/1670/submission/156213481

My logic First I clearify the string i.e if the special characters occurs more then 1 time adjacently I remove the it like "kmjjjffj" if j is special characters then my function clearify the string as kmjffj. After that I find out the max distance between the special characters.

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

1670B — Dorms War I still didn't understand this problem editorial. (can't understand the solution as I don't know java) can somebody please explain that in detail.

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

can u please provide more explanation about (rem and nextRem) in dp function i can't see what is benefit, and thank u for the great contest Ahmed_Hosssam

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

    problem F ,,, the real magic happens here,

    [

    Your code here...
    

    int currentBitSum = (val & 1L << idx) == 0 ? 0 : 1;

    int nextRem = 2 * (rem + currentBitSum — i);

    Your code here...
    

    ]

    can any one explain it Ahmed_Hosssam

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

can any one explain solution of problem d ?? i didn't understand the editorial!

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

    Which part you did not understand?

    Instead of using pen and paper, You can download a hexagonal graph paper and use sketch.io for better clarity

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

can someone check my solution for problem B? Im getting a TLE at 35th test case.

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

    here is your accepted code just add this line ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); it make your io operations fast as in this problem t<=10**5 which is large.

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

can someone help me with my solution to problem C, I'm getting TLE 156607712

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

    here is your accepted code the modifications are the following:

    1. max size of arrays vis and adj should be 10**5+1 not 10**5 only since you use 1-based index

    2. don't print pow(2,k) without modulus ,instead do this

    Spoiler

    3.the cause of TLE is that you clear adj at every test case which is very time consuming so clear only n size portion from adj

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

In question 2 TLE is coming on 35th testcase. However, I have done this question in O(n).

https://codeforces.com/contest/1670/submission/157649894 is the link for the submission.

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

Thankyou! The first editorial in my life I have seen written in JAVA. Its helping alot.

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

//for problem c i am using dfs.. but i am getting wrong answer verdict but my solution passes //given test cases //plz help

#include <bits/stdc++.h>  
#include <cmath>
using namespace std;
using ll = long long;
using ld=long double;
typedef pair<int, int> pii;




 void dfs_helper(ll src,vector<ll>graph[],ll visited[]){
     visited[src]=1;
     for(auto nbr:graph[src]){
        if(!visited[nbr]){ 
         dfs_helper(nbr,graph,visited);
        }
     }
 }
 ll dfs(vector<ll>v1,vector<ll>graph[],ll visited[]){
    ll ans=1;
    for(ll i=0;i<v1.size();i++){
         if(!visited[v1[i]]){
            //  cout<<v1[i]<<" ";
             dfs_helper(v1[i],graph,visited);
             ans=((ans%1000000007)*2)%1000000007;

         }
    }
    return ans;
}


int main() {

        ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

      ll t;
     cin>>t;
   while(t--){

       ll n;
       cin>>n;
       ll a[n];
       ll b[n];
       ll c[n];
       for(ll i=0;i<n;i++)cin>>a[i];
       for(ll i=0;i<n;i++)cin>>b[i];
       for(ll i=0;i<n;i++)cin>>c[i];

       vector<ll>v(n+1,0);

       for(ll i=0;i<n;i++){
           if(c[i]!=0){
               v[b[i]]=1;
               v[a[i]]=1;

           }
       }
     for(ll i=0;i<n;i++){
          if((v[a[i]]==0&&v[b[i]]!=0)||((v[a[i]]!=0&&v[b[i]]==0))||(a[i]==b[i])){
               v[a[i]]=1;
               v[b[i]]=1;
           }
       }

       vector<ll>graph[n+1];
       ll src=0;
       vector<ll>v1;
       ll visited[100001]={0};
        // cout<<size<<'\n';

        // ll size=1;
        // for(ll i=0;i<n;i++){
        //     if(v[a[i]]==1||v[b[i]]==1){size++;}
        // }
        // cout<<size<<" ";
        for(ll i=0;i<n;i++){
           if(v[a[i]]==0&&v[b[i]]==0){
               src=a[i];
              graph[a[i]].push_back(b[i]);
              graph[b[i]].push_back(a[i]);
              v1.push_back(a[i]);
              v1.push_back(b[i]);

           }
       }
           sort( v.begin(), v.end() );
           v.erase( unique( v.begin(), v.end() ), v.end() );
    //   for(ll i=0;i<v1.size();i++)cout<<v1[i]<<'\n';
       if(src==0){
         cout<<1<<'\n';
       }else{
         cout<<dfs(v1,graph,visited)<<'\n';
       }




   }
return 0;
}

// 199927 199924

//pre-order:- root,left,right
//in-order:- left,root,right
//post-order:- left,right,root
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, the triangle counts when more lines are added optimally result in the series $$$0+0+2+4+4+6+8+8+10+12+12+14+...$$$ Which includes all non-negative even numbers, where every other even number appears twice.

With $$$n-1$$$ as the number of lines and $$$k = \lfloor{\frac{n}{3}}\rfloor$$$, the triangle count from optimal placements can be represented using the formula:

$$$\frac{k\times (2 + 4k - 2)}{2} + 4k(1 + k) - 4k(2-n\% 3)$$$

Which can be simplified into:

$$$6k^2 + 4k(n\% 3 - 1)$$$

This expression can then be binary searched to find the first evaluation greater than the input.

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

For problem F, there is a slightly different way to implement that I think is conceptually easier and less error prone.

If $$$r$$$ was smaller, then we could always have a $$$dp[bit][x]$$$, where $$$dp[bit][x]$$$ represents the number of ways to ensure the bitwise xor is the first $$$bit$$$ bits of $$$z$$$ and our sum is $$$\le x$$$. As for transitions,

for (int cnt = b; cnt <= n; cnt += 2) {
     dp[x][y] += dp[x - 1][y - (1 << x) * cnt] * cnt * combo[n][cnt];
 }

where $$$b$$$ is our bit in the $$$bit$$$ th position.

Now the problem is that $$$r$$$ states is just way too much. So what we can do is notice that $$$x > 2^{bit + 1} \cdot n$$$, then we set it to be $$$2^{bit + 1} \cdot n$$$.