Solving An Interactive Problem CF Round 700 Div2 C

First of all, what is an interactive problem?

read it from here

The blog says all about it, still i am showing it roughly and practically.

In interactive problem we have to grab input data from the problem on our demand. we have to make queries and if our query stand valid then the problem (interactor) give us some input and based on these inputs of some limited number of query we have to answer a valid result of this problem.

Lets see a problem,

problem link  

Problem statement:

 

 

Okay, Our hero Homer has an array which is a permutation, but hidden. We have to find any local minimum of the array in at most 100 queries. Wants to know more about local minimum click here

In each query we can get a value of any index we asks for. For finding local minimum we will run a binary search.

For every printf() function or cout << we have to flush

in C++, we can use cout.flush() or fflush(stdout)

Here is the official Editorial of this problem.

Code:

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int arr[maxn];
int n;
///solution
void take(int w){
    if(1<=w && w<=n){
        printf("? %d\n",w);
        fflush(stdout);
        scanf("%d",&arr[w]);
    }
}
void solution(){

   //cin>>n;
    scanf("%d",&n);
    int ans;
    arr[0]=n+1;
    arr[n+1]=n+1;
    int left=1, right=n;
    while(left<right){
        int mid=(left+right)/2;
        take(mid);
        take(mid+1);
        if(arr[mid+1]>arr[mid]){
            right=mid;
        }
        else left=mid+1;
    }
    printf("! %d\n",left);
    fflush(stdout);
}
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
    #endif
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah

 

Shortest Path? Toph Criterion 2021 Round 9 Explanation with code

Problem link

First of all we need to find the shortest paths from a source node S to destination node T of the given graph.

And secondly a node will be given say X and we need to find the minimum distance from node X to any node of the shortest paths.

For find that a node belongs to the shortest path or not? here is the observations,

we will run a bfs from source node and find the distances of all node from source. And again we will run another bfs from destination node and find the distance of all node from destination. If you have any doubt on bfs check the link

A node will be belong to any shortest path of the graph if distance from source + distance from destination of the node equal to the shortest path distance, in another word,

source_distance[i]+destination_distance[i] == source_distance[destination]

Now we had to find distance from any shortest path to the asking node. We can precalculate all the distances by running a bfs one more time. In this case we will push the nodes into the queue which are belong to the shortest paths and initialize the distance of these nodes as 0. This is also called Multisource bfs .

Code:

C - Digital Graffiti Atcoder Beginner Contest 191 Code with Explanation

Problem Link

Explanation: We need to find number of sides, if  all '#' creates a polygon itself. For this purpose we need to find number of sides of this shape. Lets find if a cell is a side or not.

    1    2    3    4
1    .    .    .    .

2    .    #    #    .

3    .    #    #    .

4    .    .    .    .

Observations: If 4 adjacent cells has odd number of '#' it will contain a side of polygon. If a cell is (i,j) we will count '#' in cells (i,j),(i+1,j),(i+1,j+1),(i,j+1) for cell i,j.

for (1,1) >> Number of #  is 1 at(2,2)

for(1,2)>> Number of # is 2 at(2,2 and 2,3)

for(1,3)>> Number of # is 1 at(2,3)

...

...

...

In this way we will get the number of sides of the polygon.

Code

void solution(){
    int h,w;
    cin>>h>>w;
    string s[h];
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    int ans=0;
    for(int i=0;i<h-1;i++){
        for(int j=0;j<w-1;j++){
            int cnt=0;
            if(s[i][j]=='#')cnt++;
            if(s[i+1][j]=='#')cnt++;
            if(s[i+1][j+1]=='#')cnt++;
            if(s[i][j+1]=='#')cnt++;
            if(cnt%2!=0)ans++;
        }
    }
    cout << ans << endl;
}