Greedy is Tricky : 914B - Conan and Agasa

Editorial : http://codeforces.com/blog/entry/57250

Ref : http://codeforces.com/problemset/problem/914/B

#from editorial.....

Let A = max (a1, a2, ..., an). Observe that if A occurs an odd number of times, Conan can simply begin by removing one instance of A. If there are any cards left, they all have the same number A on them. Now each player can only remove one card in their turn, and they take turns doing so. Since there were an odd number of cards having A on them initially, this keeps continuing until finally, in one of Agasa's turns, there are no cards left.

However, if A occurs an even number of times, Conan cannot choose a card having A on it because it will leave Agasa with an odd number of cards having A. This will result in both players picking cards one by one, ending with Agasa picking the last card, and thus winning. In such a case, Conan can consider picking the next distinct largest number in the array, say B. If B occurs an odd number of times, then after Conan's turn there will be an even number of cards having B and an even number of cards having A. If Agasa takes a card having A then it becomes the same as the previous case and Conan wins. Otherwise, they take turns choosing a card having B until finally, on one of Agasa's turns, there are no cards having B and Agasa is forced to pick a card having A. Now it is Conan's turn and there are an odd number of cards having A, so it is again the same as the first case and Conan wins.

By a similar argument, we can show that if Conan plays optimally, he starts by picking a card having the greatest number that occurs an odd number of times. Conan loses if and only if there is no such number, i.e., Conan loses if and only if every number occurs an even number of times

Code :

int main()
{
 int n,i,j,a[100005],k=0,count[100005];
  scanf("%d",&n);
 for(i=0;i<n;i++)
 {scanf("%d",&a[i]);count[a[i]]++;}
 for(i=0;i<n;i++)
 { if(count[a[i]]%2==1)
        { printf("Conan");return 0;}}
        printf("Agasa");    
        return 0;
}

AtCoder contest by tourist

link : https://agc020.contest.atcoder.jp/

EDITORIAL FOR ROUND #2

EDITORIAL FOR ROUND #2

ref : http://codeforces.com/blog/entry/107
(not that good)  : http://codeforces.com/blog/entry/109

Best part is it has a DP problem.(the least round way) its just awesome.
http://codeforces.com/problemset/problem/2/C

I cant solve it coz geometry is involved 

1A-THEATRE SQUARE by Petr

1A-THEATRE  SQUARE

ref : http://codeforces.com/problemset/problem/1/A

My approach got "TLE" coz i used two loops which ranges upto 10^9.(But i donno how many test cases will it pass if i wont get "TLE" :p

Then after having a glance at Petr's code(just saw he used a formula - donno what at that time ;) ),

So i too tried to solve/to find a formula.

I came up with this : 

ceil(n/a)*ceil(m/a)

which is not true - it failed in a test case

but finally solved it using the same formula and it turns out that i failed coz of precision 

Test: #16, time: 15 ms., memory: 1812 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER

Input

1000000000 1000000000 999999999

Output

1

Answer

4

Checker Log

wrong answer 1st numbers differ - expected: '4', found: '1'

But Petr solved this in constant time by using simple formula :

                  ((n + a - 1) / a) * ((m + a - 1) / a)

I missed a-1 in both numerators :(

2A-WINNER

2A-WINNER

Looks so innocent but quality problem, im holding it for a while coz i need to learn more about collections/templates.

ref : http://codeforces.com/problemset/problem/2/A

The problem here is to keep track of names and their corresponding scores in chronological order.

915B-BROWSER

915B - BROWSER

ref : http://codeforces.com/problemset/problem/915/B

My Approach : 

I considered all the positions of "pos"  but we need not do that coz the solution only depends on the position of a and b.

MY APPROACH

I focused on the position of "pos".So, we should still check for extreme(border) cases and I still cant guarantee that this works coz ive not implemented it :P

SOLVED :

This can simply be done by considering only the positions of a and b coz we can take abs value of distance irrespective of the position of c
and we have no need to check any border cases !!! (cool :p)

CODE : 

#define MIN(a, b) (a<b? a: b)

#define ABS(a) (a<0? -(a): a)

int main(){

int n, pos, l, r;

scanf("%d %d %d %d", &n, &pos, &l, &r);

int sec = 0;

if (l > 1 && r == n){

sec = ABS(pos - l) + 1;

}

else if (l == 1 && r < n){

sec = ABS(r - pos) + 1;

}

else if (l > 1 && r < n){

sec = MIN(ABS(pos-l), ABS(r-pos)) + 1;

sec += r - l + 1;

}

printf("%d\n", sec);

return 0;

}

The POWER sum by Kevinsogo & Anno

THE POWER SUM

ref : https://www.hackerrank.com/challenges/the-power-sum/problem

Approach :

editorial : https://www.hackerrank.com/challenges/the-power-sum/editorial

1.

Kevin has cleverly solved this problem without sweating..... (NO surprise).

int count(int x,int n,int s,int v){

   

    if(s == x)  return 1;

    else{

       v++;

       int res = 0;

           while(s+pow(v,n) <= x){

                 res += count(x,n,s+pow(v,n),v);

                 v++;} //while loop

       return res;

       }

TREE DIAGRAM FOR RECURSION

That's it !!!! :o

2.

int count(int x, int n, int i) {
      x = x - (int) Math.pow(i, n);
      if (x == 0) return 1;
         if (x > 0) {
            int sum = 0;
            for (int j = i + 1; Math.pow(j, n) <= x; j++)
                sum += fn(x, n, j);
            return sum;
                    } 

     else return 0;
    }

TREE DIAGRAM FOR RECURSION

Interesting !!!

CIRCULAR ARRAY ROTATION - (RIGHT)

ref : https://www.hackerrank.com/challenges/circular-array-rotation

Approach :  We have no need to do any shifts here,just an index arithmetic is enough i.e., 

for (int i = 0; i < n; i++) {

scanf("%d",&a[(i+k)%n]);   }

while reading the values itself !!!!

ARRAY LEFT ROTATION

ref : https://www.hackerrank.com/challenges/array-left-rotation/problem

Approach :  Same here, just an index arithmetic and it can be done in 2 ways :

1.with additional array : 

 for(int i=0;i<n;i++){

scanf("%d",&a[i]);

b[(n-d+i)%n] = a[i];

}

2.with no additional array : (cool :p)

where d = # of left rotations

 int l = n-d;

 for(int i=0;i<n;i++){

if(l == n)  

l = 0;

scanf("%d",&a[l++]);}

********************************BOMB OF THE DAY*******************************

ARRAY MANIPULATION

ref : https://www.hackerrank.com/challenges/crush/problem

Approach : If we follow naive approach or any most efficient sorting algorithm you will still get  TLE. So, I discovered something called a "prefix sum" (in the editorial of course :p)

Here, instead of updating m (queries) times, we update the l(add) and r+1(subtract) indices only and while finding the max. value in array, we keep on adding the values in the array [?]till we encounter 

-ve value[?] 

NAIVE - FAILED - TLE

for(long a0 = 0; a0 < m; a0++){

long a,b,k;

scanf("%ld %ld %ld", &a, &b, &k);

a--;

b--;

for(int i=a;i<=b;i++)

ar[i] = ar[i] + k;}

//used even merge sort

//still failed

WORKING - (PREFIX  SUM)

editorial link : https://www.hackerrank.com/challenges/crush/editorial  (but still didn't understood :p) 

for(i=0;i<k;i++){

long long int l,r,k;

scanf("%lld %lld %lld",&l,&r,&k);

a[l] = a[l] + k;

if(r+1<=n){

a[r+1] = a[r+1] - k;}

}

for(i=1;i<=n;i++){

x = x + a[i];

if(max<x){

max=x;   }

}

printf("%lld",max);

That's it !!!!! Need to get my head around it.