Ostrich888's blog

By Ostrich888, history, 4 years ago, In English

Hello Everyone!!

Problem link

I have got the basic idea of how to approach this problem.

My doubt:-

In the solution given by editorial, when we are moving left end and right end then how are we maintaining the current maximum as we also need to erase some elements from the Tries then how are we maintaining maximum. Are they not deleting elements? I couldn't understand it properly. Can you please explain what exactly are they doing to find the maximum from tries.

Thank You

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it

By Ostrich888, history, 4 years ago, In English

Hello Everyone!

Link to the Question

https://codeforces.net/blog/entry/63533

I am having doubt in 1st question of this blog.

In exchange argument we try to find a comparator that will decide our order. For this we try to solve question for N=2 case to determine what can be the possible comparator.

Now when we take N=2 we make some conditions.Let's take two elements are A and B. In question 1st we are getting condition by saying A must come before B(Only possible ordering) . But in question 2 and 3 of the same blog we are getting conditions by saying when will it be better to put A before B. I think these two are quite different.

I am quite confused regarding this like what how to make conditions for N=2 case. I think I have interpreted it in wrong way and there must exist a better explanation.

It would be very helpful if somebody can explain where I am interpreting wrong.

Thank you

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it

By Ostrich888, history, 4 years ago, In English

Hello Everyone!

The link to the question

https://atcoder.jp/contests/abc172/tasks/abc172_f

The approach I am unable to understand.

https://codeforces.net/blog/entry/79438

I am finding it difficult to how is the author deciding what bits to set in x on basis of S. Mainly the 3rd and 4th paragraph of the solution, I am unable to grasp.

It would be really helpful if someone who was able to understand the approach can describe in his own words.

Thank you

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

By Ostrich888, history, 4 years ago, In English

Hello Everyone!

https://codeforces.net/contest/845/problem/G

The problem says that we are given a weighted connected graph in which path length is defined as xor of all weights on the path. We are given two vertices and need to find shortest path length.

In the solution, we are calculating cycle basis of graph. For this we first make a spanning tree of the graph. Let's assume we have an empty set S. Then we take all the non-spanning edges of the graph one by one and find the cycle which this edge is making with only the spanning edges and include this cycle in our set S . The claim is that every set of cycles in the graph is a subset of this set S (We can also reduce S to its basis). I am unable to get this claim.[It is wrong claim as stated in the comments.] Can somebody give me a proof of this of how is it including every cycle that exists in the graph

Can we also represent every closed walk in the graph using the subset of set S?

Thank You

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By Ostrich888, history, 4 years ago, In English

Hello Everyone!

I am currently using Windows 10. I run my C++ code in Sublime Text 3 which take around more than 2 sec to run a code which is too slow (I am just printing a variable). I have also tried to include precomplied header for stdc++.h but still running time is same. Can somebody please help me with this issue ?

Thank You

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it

By Ostrich888, history, 4 years ago, In English

Hello everyone! I want to ask about why is it the case that when our solution is correct we usually get verdict within a few seconds but when it is WA or Runtime error then it takes so much time (sometimes more than 15 sec). It does not happen in live contests but happens when I upsolve(practice) the problems. Thank you.

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it