fares's blog

Can't debugg this !
By fares, history, 11 years ago, In English

Hi: I was solving this problem http://codeforces.me/problemset/problem/451/B

my idea in brief is to sort the input and repeatedly check if an entry has been moved(call it a[i]) in the sort ,where it is know and which entry it was exchanged with(call it a[j] )and check every entry between a[i] and a[j] to double sure that if it is a segment that was reversed , lastly check the number of the reversed segments to print the answer.

Here is the code:


 import java.util.*;
public class Main
{
	public static void main (String args[]){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int unsort[]=new int[n];
		int sort[]=new int[n];
		for(int i=0;i<unsort.length;i++){
			unsort[i]=sc.nextInt();
			sort[i]=unsort[i];
		}
      Arrays.sort(sort);
	  int co=0;int counter=0,id=0,id2=1;
	  for(int i=0;i<unsort.length;i++){
		  if(unsort[i]!=sort[i]){
			  co++;
			  int in=Arrays.binarySearch(sort,unsort[i]);
			  if(sort[i]==unsort[in]&&sort[i+1]==unsort[in-1]){
				  int i2=i;int in2=in;boolean b=false;
				  while(i2++<=in2--){
					  if(sort[i2]!=unsort[in2]){b=true;break;}
				  
				  }
				  if(b==false){
				  ++counter;id=i;id2=in;
				  i=in;}
			  }
		  }
	  }
	  ++id;++id2;
	  if(co==0){id=1;id2=1;}
	  System.out.println((counter==1||co==0)?"yes\n"+id+" "+id2:"no");
	}
	
}

Edit:changed the blog as you said :)
  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I would recommend providing a link to submission or link to ideone.com/pastebin.com instead of messy code in the post's body (former is preferable).

By the way, there is code formatting in blog posts, just remember to add an extra empty line before first ~~~~~ to make it work (unfortunately, it silently messes up otherwise). So, this does not work: ~~~~~ int main() ~~~~~

But this does:

int main()

Also, it's better if you describe main idea of your solution and reasoning/proofs behind that instead of translating C++ to English. So, instead of "If equal increment some variable" you'd better write something like "I calculate number of indices i such that ai = bi, let's call that number X in further description" (have no idea if that relates to your solution in the first pplace).

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    pardon me, as i am not used to posting in codeforces and proving my idea to others . here is a link to the submission :http://codeforces.me/contest/451/submission/15689720

    my idea in brief is to sort the input and repeatedly check if an entry has been moved(call it a[i]) in the sort ,where it is know and which entry it was exchanged with(call it a[j] )and check every entry between a[i] and a[j] to double sure that if it is a segment that was reversed , lastly check the number of the reversed segments to print the answer.

    that is the best i can do, sorry for the inconvenience :).

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Thank you. It makes more sense now. I would recommend editing original post accordingly. Note that you can insert link to submission with special CF tag (hidden under CF icon in the editor), like this: 15689720 ([ submission:15689720 ] without spaces). Btw, I would also recommend formatting your source code and make indentation consistent across the source code. Any modern IDE can do that automatically (it's usually called "Format code") or you can google for "Java source formatter". It'll be much easier to read if code is formatted to common conventions.

      When your solutions finds a subsegment in the original array which can be reversed to match itself in the sorted array, it does not check that everything outside the segment matches already. Note that it's not guaranteed that if answer is "yes", then the original array was a result of reversing some non-overlapping segments, it can be much more complicated. Say, no sub-segment in 2 3 1 can be reversed to match itself in sorted 1 2 3.

      It can turn out that there is only one segment which matches itself when reversed, but its outsides are completely messed up. There is a corresponding test with n = 5 which fails your solution.

      → Reply