Women Who Reign: Marianne Linhares

:D!

ReigningIt

“It takes a great deal of courage to stand up to your enemies, but even more to stand up to your friends.” — J.K. Rowling
~~~~

Tell us about yourself along with a fun fact!
Hey everyone, my name is Marianne Linhares, I’m from Brazil and I’m a Computer Science undergraduate student at the Universidade Federal de Campina Grande and currently a fellow coach at the Paraíba State Olympiad in Informatics.

Things I’m passionate about: my friends and family, education, math, music, code, pizza, video games, this video, and helping people (in no particular order, but pizza first haha).
Things I just don’t tolerate: prejudice, ignorance, a closed mind and a closed heart.

Fun fact about me: I’ve played the electric guitar since I was 11 years old. At that time I specifically wanted to learn to play the electric guitar instead of acoustic guitar because I was really into…

View original post 299 more words

Women Who Reign: Marianne Linhares

URI – Warm up Contest to OBI 2016 -second phase

Hey there,

Not so recently happened the Warm up Contest to OBI 2016 and I was one of the authors again (I was one of the authors in the first phase as well)!

I wrote 1 problem: Rio 2016
I’ll make a fast editorial of this problem and, hopefully, this will help someone :)!

Rio 2016

By: Marianne Linhares

This problem is very up forward, reading the problem carefully is easy to see that we should calculate the distance between the points and then compare it with the time that the match will begin.

Buuuut, be careful with the use of integers, the multiplication may not fit in an integer, so you should use long long int (C++) for the position variables.

A C++ solution can be seen here.

  • Complexity: O(n).
URI – Warm up Contest to OBI 2016 -second phase

My first Chrome Extension – SpotifYoutube

Hello,

Stop the world, there’s something very weeeird happening… after a couple of very busy months I’ve got the time to start (and finish, I know I’m as shocked as you guys) my first chrome extension.

It’s a simple extension that adds a button to YouTube to search the youtube video title you’re watching in Spotify. I’m very proud of this, it’s working properly and youtube is love, spotify is love, this extension could not be different!

button.png

Hope you guys enjoy it!

Source code, Chrome Web Store!

Demo:

My first Chrome Extension – SpotifYoutube

URI – Warm up Contest to OBI 2016 – first phase

Hey there,

Recently happened the Warm up Contest to OBI 2016 and I was one of the authors, it was a nice experience!

I wrote 3 problems: Prant and the Indecision, Odd, Even or Cheating e Setting up a Date.

The portuguese editorial is in this link. Soon may be an english editorial :)!

Since an english editorial is not available, I’ll make a fast editorial of my problems, hope this helps!

Odd, Even or Cheating

By: Marianne Linhares

In this problem the rules of the game must be well understood and correctly implemented.
There are only 2 possibilities of result, player 1 wins or player 2 wins, a draw is not possible.
The possible cases of player 1 to win are:

  • The numbers chosen doesn’t matter, player 1 cheats and player 2 doesn’t accuse player 1
  • The numbers chosen doesn’t matter, player 1 doesn’t cheat and player 2 accuses player 1
  • Player 1 chooses even, player 1 doesn’t cheat, player 2 doesn’t accuse player 1 and the sum of the chosen numbers is even
  • Player 1 chooses odd, player 1 doesn’t cheat, player 2 doesn’t accuse player 1 and the sum of the chosen numbers is odd

If none of these cases happen then player 2 wins.

  • Complexity: constant.

Setting up a Date

By: Marianne Linhares

This problem can be solved using Geometric Probability. We can define the possible arrival times of Mel and Tob as points in the cartesian coordinate system, each possible time is a (x, y) inside the square determined by (0, 0) and (t2-t1, t2-t1) that represents the possible meeting interval.
We also have the maximum wait time N as a constant that will determine the possible area of meeting. This whole situation can be represented bellow.

l.png

 

So, the probability of happening a meet is defined by A1/AT.
To get the irreductible fraction just divide each term by gcd(A1, AT).

  • Complexity: basically constant.

Prant and the Indecision

By: Marianne Linhares

The problem can be easily understood through the sample. But summarizing the problem situation: given a string of size m and n changing letters operations (1 ≤ m, n ≤ 100 000), such that a change letter operation consists of changing all letters a to b and all letters b to a in the current word, you should make a program that determines which word contains more favorite letters. Then, the difficulty of the problem is how to obtain such word in an efficient way, because a solution that simulates the changes directly would be O(m * n) and would not be fast enough.

A possible solution is instead of update the entire word at each change just update the letters involved in the change. This can be done through an array that relates each letter to some other (in other words, it holds the current status of the changes), besides another array that holds how many times each letter appears in the word. Bellow there is an example of how a change could be simulated following the described implementation, where ch is the array that holds the “relations” and value holds the number of occurrences of each letter in the current word:

scanf(" %c %c", &c1, &c2);

int , ;
for(int j = 0; j < 26; j++) {
    if(ch[j] == c1) pos_c1 = j;
    if(ch[j] == c2) pos_c2 = j;
}

aux = ch[pos_c1]; ch[pos_c1] = ch[pos_c2]; ch[pos_c2] = aux;
aux = value[c1 - 'a']; value[c1 - 'a'] = value[c2 - 'a']; value[c2 - 'a'] = aux;

So, after update these arrays you should verify if the sum of the occurrences of the favorite letters (you can get this information trough the value array in O(26) is the greatest until now, if this happens just copy the ch array into another so in the end you can print the word.

PS: Another way to implement this is using a map. The solution will be more intuitive but a little less efficient(a constant irrelevant will be added).

  • Complexity: O(26 * n)
  • Complexity using a map: O(26 * n * log(26)
URI – Warm up Contest to OBI 2016 – first phase

2016 – is it to late now to say sorry?

First of all, happy new year!!!! This is the first post of 2016 :D! (Yeah, I know, it’s almost 2017).

But anyway, I Just want to apologize for not updating the blog, and still didn’t translate some posts, I’ll do it till the end of the year, I swear haha.

And I also want to say what I have planned to do this year. Check it out:

  • I plan to put my personal website on github, but still keep using wordpress for blogging.
  • Keep a median of 4 posts a month 1 post a month (life is hard people), of course starting now haha
  • Write about some stuff I did last year that is not available in here

So, awesome, right? Hope everything works out :)!

Have a good day!

2016 – is it to late now to say sorry?