Sachverhalt:
A.
A.a. Die 1960 geborene A._ meldete sich im April 2004 wegen "massiven Depressionen und Somatisierung" bei der Invalidenversicherung zum Leistungsbezug an. Die IV-Stelle Bern führte verschiedene erwerbliche und medizinische Abklärungen durch, namentlich veranlasste sie eine bidisziplinäre Begutachtung bei den Dres. med. B._, FMH Neurochirurgie, und med. C._, FMH Psychiatrie und Psychotherapie (Teilgutachten vom 25. August 2005 und vom 6. September 2005), sowie eine Haushaltabklärung (Abklärungsbericht vom 11. November 2005). Mit Verfügung vom 16. März 2006 sprach sie A._ eine Viertelsrente der Invalidenversicherung ab Juli 2003 zu (Invaliditätsgrad 40 %). Nach erfolgter Härtefallprüfung wurde diese Rente - bei gleich bleibendem Invaliditätsgrad - vorerst auf eine halbe (Verfügung vom 2. Juni 2006), schliesslich nach dem Tod ihres Ehemannes auf eine ganze Rente erhöht (Verfügung vom 9. Oktober 2007).
A.b. Im Rahmen einer im Jahr 2007 eingeleiteten Rentenüberprüfung veranlasste die IV-Stelle eine psychiatrische Verlaufsbegutachtung bei Dr. med. C._ (Gutachten vom 12. September 2008) sowie eine neuerliche Haushaltabklärung (Abklärungsbericht Haushalt vom 25. Mai 2009) und hob die bisher ausgerichtete Rente auf Ende des der Zustellung der Verfügung folgenden Monats auf (Verfügung vom 26. August 2009).
A.c. Im November 2011 ersuchte A._ erneut um Leistungen bei der Invalidenversicherung. Die IV-Stelle veranlasste wiederum Abklärungen, insbesondere eine psychiatrische Begutachtung bei Dr. med. D._, Facharzt für Psychiatrie und Psychotherapie (Gutachten vom 31. Januar 2014) sowie eine zusätzliche Stellungnahme vom 19. Mai 2014. Mit Vorbescheid vom 21. August 2014 stellte die Verwaltung die Abweisung des Leistungsbegehrens in Aussicht. Nachdem A._ dagegen hatte Einwände vorbringen lassen, verfügte die IV-Stelle am 3. Dezember 2014 wie vorbeschieden.
B.
Das Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, hiess die dagegen erhobene Beschwerde mit Entscheid vom 30. Oktober 2015 gut, hob die angefochtene Verfügung vom 3. Dezember 2014 auf und sprach A._ ab Mai 2012 eine ganze Rente der Invalidenversicherung zu.
C.
Die IV-Stelle Bern führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt die Aufhebung des kantonalen Entscheids vom 30. Oktober 2015 und die Bestätigung der Verfügung der IV-Stelle Bern vom 3. Dezember 2014. In prozessualer Hinsicht sei der Beschwerde die aufschiebende Wirkung zu erteilen.
A._ schliesst auf Abweisung der Beschwerde sowie des Gesuchs um Erteilung der aufschiebenden Wirkung. Ferner sei ihr die unentgeltliche Rechtspflege zu gewähren. Das Bundesamt für Sozialversicherungen (BSV) beantragt Gutheissung der Beschwerde.

Erwägungen:
1.
1.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>).
1.2. Bei den gerichtlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit bzw. deren Veränderung in einem bestimmten Zeitraum handelt es sich grundsätzlich um Tatfragen (<ref-ruling> E. 3.2 S. 397 ff.). Gleiches gilt für die konkrete Beweiswürdigung (Urteil 9C_204/2009 vom 6. Juli 2009 E. 4.1, nicht publ. in <ref-ruling>, aber in: SVR 2009 IV Nr. 53 S. 164). Dagegen ist die Beachtung des Untersuchungsgrundsatzes und der Beweiswürdigungsregeln nach <ref-law> Rechtsfrage (<ref-ruling> E. 3.2 und 4 S. 397 ff.; Urteil I 865/06 vom 12. Oktober 2007 E. 4 mit Hinweisen), die das Bundesgericht im Rahmen der den Parteien obliegenden Begründungs- bzw. Rügepflicht (<ref-law> und <ref-law>; <ref-ruling> E. 1.1 S. 137 f.; <ref-ruling> E. 1.4.1 und 1.4.2 S. 254) frei überprüfen kann (<ref-law>).
2.
Die Vorinstanz hat die gesetzlichen Bestimmungen und die von der Rechtsprechung entwickelten Grundsätze zur Invalidität (<ref-law> in Verbindung mit <ref-law>), zur Erwerbsunfähigkeit (<ref-law>), zum Umfang des Rentenanspruchs (<ref-law>), zur Bemessung des Invaliditätsgrades bei teilerwerbstätigen Versicherten nach der gemischten Methode (Art. 28a Abs. 3 in Verbindung mit Abs. 2 IVG sowie <ref-law>; <ref-ruling> E. 3.1.3 S. 338), zum Beweiswert und zur Beweiswürdigung ärztlicher Berichte und Gutachten (<ref-ruling> E. 5.1 S. 232; <ref-ruling> E. 3a S. 352) zutreffend dargelegt. Gleiches gilt in Bezug auf die Beurteilung der Invalidität bei pathogenetisch-ätiologisch unklaren syndromalen Beschwerdebildern ohne nachweisbare organische Grundlage (<ref-ruling>) sowie die bei der Rentenrevision geltenden Grundsätze, welche bei Neuanmeldungen analog Anwendung finden (<ref-law>; Art. 87 Abs. 2 und 3 IVV; <ref-ruling> E. 3.2.3 S. 77). Darauf wird verwiesen.
3.
Prozessthema bildet die Frage, ob und inwieweit sich der Invaliditätsgrad der Versicherten seit der rechtskräftigen Rentenaufhebung (Verfügung vom 26. August 2009) bis zur verfügungsweisen Neuprüfung vom 3. Dezember 2014 in - analog - revisionsrechtlich erheblicher Weise verändert hat (<ref-law>). Dabei ist zu beachten, dass Anlass zur Rentenrevision jede wesentliche Änderung in den tatsächlichen Verhältnissen gibt, die geeignet ist, den Invaliditätsgrad und damit den Rentenanspruch zu beeinflussen. Allerdings stellt eine bloss unterschiedliche Beurteilung eines im Wesentlichen gleich gebliebenen Sachverhalts keine revisionsbegründende Tatsachenänderung dar (<ref-ruling> E. 2b S. 372).
4.
In formeller Hinsicht rügt die Beschwerdeführerin, die Vorinstanz habe die revisionserhebliche Veränderung in den tatsächlichen Verhältnissen nur oberflächlich und in Missachtung der Ausführungen der IV-Stelle in ihren Rechtsschriften vom 18. Februar, vom 22. April und vom 16. Juli 2015 begründet und demnach den Sachverhalt offensichtlich unrichtig festgestellt. Entgegen ihrer Auffassung, beschlägt dieser Einwand nicht den als verletzt gerügten Untersuchungsgrundsatz oder die Beweiswürdigungsregeln, sondern den Gehörsanspruch (<ref-law>) und die gerichtliche Begründungspflicht (<ref-law>). Eine diesbezügliche Verletzung macht die Beschwerdeführerin zu Recht nicht geltend: Massgeblich ist, dass das Gericht in seiner Begründung die Überlegungen nennt, von denen es sich hat leiten lassen, damit der Entscheid sachgerecht angefochten werden kann (vgl. <ref-ruling> E. 2.2 S. 84; <ref-ruling> E. 5.2 S. 236 mit Hinweisen). Die Vorinstanz hat diese Grundsätze eingehalten. Sie hat den medizinischen Sachverhalt in den beiden massgebenden Vergleichszeitpunkten (vgl. <ref-ruling> E. 5 S. 110 ff.) wiedergegeben und in E. 3.5.3 - wenn auch äusserst kurz und im Ergebnis unhaltbar (vgl. E. 5 nachfolgend) - dargelegt, weshalb ihrer Ansicht nach eine wesentliche Veränderung des Gesundheitszustands vorliegt. Die Beschwerdeführerin hat den Entscheid denn auch sachgerecht anfechten können. Ungenügend begründet ist vielmehr der Einwand der Beschwerdeführerin: Sowohl Rüge als auch Begründung müssen in der Beschwerdeschrift selber enthalten sein. Der blosse Verweis auf gemachte Ausführungen in anderen Rechtsschriften, worauf sich die IV-Stelle beschränkt hat, genügt nicht (<ref-ruling> E. 4).
5.
Eine in rechtlicher und tatsächlicher Hinsicht umfassende Prüfung des Rentenanspruchs ohne Bindung an frühere Beurteilungen setzt einen Revisionsgrund im Sinne von <ref-law> voraus (<ref-ruling> E. 2.3 S. 11). Es fällt auf, dass die Vorinstanz die invalidenversicherungsrechtliche Relevanz der somatoformen Schmerzstörung, wie sie im unbestritten beweistauglichen Gutachten des Dr. med. D._ diagnostiziert wurde, vorab prüfte und zwar anhand der Rechtsprechung gemäss <ref-ruling>. Mit dem Vorliegen eines Revisionsgrundes und damit der Zulässigkeit der (vorweggenommenen) freien Prüfung des Rentenanspruchs setzte sie sich vorgängig nicht auseinander. Erst im Anschluss daran fügte das kantonale Gericht in Erwägung 3.5.3 auf wenigen Zeilen an, es sei zudemeine wesentliche Verschlechterung des Gesundheitszustands seit der rentenabweisenden Verfügung vom 26. August 2009 erstellt. Zur Begründung führte die Vorinstanz lediglich aus, Dr. med. D._ habe - im Gegensatz zu Dr. med. C._ - neben einer anhaltend mittelgradigen depressiven Episode neu auch eine anhaltend somatoforme Schmerzstörung diagnostiziert und die Arbeitsunfähigkeit aufgrund des Chronifizierungsgrades, der Komorbiditäten sowie der geringen Copingstrategien der Beschwerdegegnerin höher eingeschätzt.
5.1. In Bezug auf das Vorliegen eines Revisionsgrundes wendet die Beschwerdeführerin zu Recht ein, dass weder eine hinzugetretene Diagnose (<ref-ruling> E. 5.2 S. 12; Urteil 9C_754/2014 E. 4.2) noch die höhere Einschätzung der Arbeitsfähigkeit (Urteil 9C_955/2012 E. 3.3.4) per se einen Revisionsgrund darstellen. Richtig ist auch der Einwand, dass - wenn überhaupt (vgl. Urteil 9C_125/2015 vom 18. November 2015 E. 7.2.1 mit Hinweisen) - mit Blick auf die Schmerzstörung nicht mehrere, sondern bloss eine einzige Komorbidität vorliegt, nämlich eine mittelgradige depressive Episode. Bei der daneben von Dr. med. D._ diagnostizierten akzentuierten (ängstlich-vermeidenden, selbstunsicheren und dependenten) Persönlichkeit (ICD-10 Ziff. Z73.1), handelt es sich um eine Diagnose aus der Z-Kategorie (Kapitel XXI) des ICD-10 Systems. Diese ist für Fälle vorgesehen, in denen Sachverhalte als "Diagnosen" oder "Probleme" angegeben sind, die nicht als Krankheit, Verletzung oder äussere Ursache unter den Kategorien A00-Y89 klassifizierbar sind. Diese Belastungen fallen als solche nicht unter den Begriff des rechtserheblichen Gesundheitsschadens (SVR 2012 IV Nr. 52 S. 188 E. 3.1 [9C_537/2011]) und stellen somit - entgegen den gutachterlichen Ausführungen in der ergänzenden Stellungnahme vom 19. Mai 2014 - von vornherein keine Komorbidität dar.
5.2. Soweit die Vorinstanz die veränderten Umstände mit dem Chronifizierungsgrad und der geringen Copingstrategien der Beschwerdegegnerin begründet, übersieht sie, dass einzig der Umstand fehlender Schmerzbewältigungsstrategien nichts darüber aussagt, ob und inwieweit sich der Gesundheitszustand als solcher verändert hat. Ebenso wenig lässt sich vom Chronifizierungsgrad - sofern sich denn eine Chronifizierung überhaupt graduell unterscheiden lässt - darauf schliessen, ob sich das gesundheitliche Bild oder dessen erwerbliche Auswirkungen verändert haben. Einzig darauf kommt es bei der Frage nach dem Vorliegen eines Revisionsgrundes aber an (Urteil 9C_288/2008 vom 16. Mai 2008 E. 5).
5.3. Die vom kantonalen Gericht festgestellte Verschlechterung des Gesundheitszustandes ist somit unhaltbar. Auf eine Rückweisung der Sache an die Vorinstanz zur Prüfung dieses Streitpunktes kann indessen abgesehen werden, weil der Sachverhalt hinreichend liquid (vgl. <ref-ruling> E. 4.1 S. 366) und vom Bundesgericht im Rahmen von <ref-law> von Amtes wegen festzustellen ist.
6.
6.1. Der Rentenaufhebung vom August 2009 lagen namentlich das Gutachten des Dr. med. C._ vom 12. September 2008 sowie der Abklärungsbericht Haushalt vom 25. Mai 2009 zugrunde. Der Psychiater diagnostizierte eine (knapp) mittelgradige depressive Episode mit somatischem Syndrom (ICD-10 Ziff. F32.11), Schwierigkeiten bei der kulturellen Eingewöhnung (ICD-10 Ziff. Z60.3) sowie Probleme in der primären Bezugsgruppe, insbesondere eine Familienzerrüttung (ICD-10 Ziff. Z63.5). Der Anamnese der damaligen Expertise lässt sich entnehmen, dass die Beschwerdegegnerin über Schmerzen am ganzen Körper, vor allem am Kopf und im Nacken, klagte. Sie verrichtete keine Arbeiten im Haushalt, war - abgesehen von der Familie - sozial isoliert und zog sich bei Krisen tagelang ins Bett zurück. Diese Angaben stehen in Einklang mit jenen im Abklärungsbericht Haushalt vom 25. Mai 2009, worin zusätzlich darauf hingewiesen wurde, die Beschwerdegegnerin unternehme Spaziergänge mit ihrer Tochter, wozu sie jedoch täglich angehalten werden müsse.
6.2. Gemäss der Expertise des Dr. med. D._, Facharzt für Psychiatrie und Psychotherapie, vom 31. Januar 2014 leidet die Beschwerdegegnerin nach wie vor an einer mittelgradigen depressiven Episode mit somatischem Syndrom - nun diagnostiziert im Rahmen einer rezidivierend-depressiven Störung, im Verlauf unterschiedlichen Schweregrades (ICD-10 Ziff. F33.11) - sowie an einer anhaltenden somatoformen Schmerzstörung (ICD-10 F45.40) vor dem Hintergrund einer akzentuierten (ängstlich-vermeidenden, selbstunsicheren und dependenten) Persönlichkeit (ICD-10 Ziff. Z73.1). Gemäss zusätzlicher Stellungnahme des Dr. med. D._ vom 19. Mai 2014 ist die Beschwerdegegnerin inzwischen auf ihre Schmerzen fixiert, was im Rahmen der Begutachtung bei Dr. med. C._ noch nicht der Fall gewesen sei. Nach wie vor verbringt sie viel Zeit im Bett, macht Ausflüge mit ihrer Tochter, hat - ausserhalb der Familie - keine sozialen Kontakte und beteiligt sich nicht an den Hausarbeiten. Sie leidet auch weiterhin primär an starken Kopf- und Nackenschmerzen, ist müde und kraftlos und hat keine Motivation.
6.3. Ein Vergleich der beiden Sachverhalte zeigt, dass in Bezug auf den Tagesablauf seit jeher ein - von den beiden Gutachtern fast identisch beschriebenes (vgl. zuvor E. 6.1 und 6.2) - tiefes Aktivitätsniveau mit Rückzug und Schonverhalten gegeben ist. Ebenfalls prägen unverändert medizinisch nicht angehbare krankheitsfremde Faktoren (namentlich genannt unter anderem die geringe kulturelle und sprachliche Integration, ein sekundärer Krankheitsgewinn sowie die subjektive Krankheitsüberzeugung) das Bild, weshalb sich sowohl Dr. med. C._ wie auch Dr. med. D._ gegen weitere medizinische Massnahmen ausgesprochen haben und lediglich eine unklare bzw. ungünstige Prognose zu stellen vermochten. In Bezug auf die - invalidenversicherungsrechtlich ohnehin nicht relevanten - akzentuierten Persönlichkeitsanteile wies Dr. med. D._ explizit darauf hin, diese hätten bereits im Zeitpunkt der Begutachtung bei Dr. med. C._ bestanden, seien von diesem aber nicht festgehalten worden. Ebenso sei damals dem Chronifizierungsgrad nicht Rechnung getragen worden. Als neu gegenüber dem Gutachten C._ beschrieb Dr. med. D._ einzig eine Fixierung auf die Schmerzen. Eine Verschlechterung ist in dieser Schmerzfixierung nicht zu erblicken, nachdem die Beschwerdegegnerin seit jeher Schmerzen am ganzen Körper beklagt, primär bezogen auf Nacken und Kopf. Dass es früher zu schmerzfreien Phasen gekommen wäre, geht aus den Akten nicht hervor. Nichts anderes hat in Bezug auf das depressive Geschehen zu gelten: Beide Gutachter beschreiben lediglich graduell unterschiedliche Schweregrade im Verlaufe der Zeit, ohne dass es dabei je zu einer (zwischenzeitlichen) Remission gekommen wäre. Im jeweiligen Gutachtenszeitpunkt gehen beide Experten von einem (knapp) mittelschweren Geschehen aus.
6.4. Im Ergebnis beschränkt sich die Expertise des Dr. med. D._ darauf, trotz im Wesentlichen unverändert gebliebenem Gesundheitszustand eine somatoforme Schmerzstörung zu diagnostizieren und die Arbeitsfähigkeit anders einzuschätzen. Eine relevante Gesundheitsverschlechterung, d.h. eine solche, die den Rentenanspruch berührt (vgl. <ref-ruling> E. 5.2; Urteil 9C_754/2014 vom 11. Juni 2015 E. 4.2), ist darin nicht zu erblicken. Weil es damit an einem Revisionsgrund fehlt, bleibt kein Raum für eine in rechtlicher und tatsächlicher Hinsicht umfassende Prüfung des Rentenanspruchs.
7.
Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung der Beschwerde gegenstandslos.
8.
Dem Ausgang des Verfahrens entsprechend hat die Beschwerdegegnerin grundsätzlich die Gerichtskosten zu tragen (<ref-law>). Ihrem Gesuch um unentgeltliche Rechtspflege kann - im Sinne der Kostenbefreiung - jedoch entsprochen werden (<ref-law>). Eine unentgeltliche Verbeiständung entfällt indessen, da ihre Vertretung durch eine Institution der öffentlichen Sozialhilfe erfolgt (Urteil 9C_30/2014 vom 6. Mai 2014 E. 3.2 mit Hinweis auf <ref-ruling> E. 5 S. 13). Die Beschwerdegegnerin hat der Bundesgerichtskasse Ersatz zu leisten, wenn sie später dazu in der Lage ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Verwaltungsgerichts des Kantons Bern, Sozialversicherungsrechtliche Abteilung, vom 30. Oktober 2015 wird aufgehoben und die Verfügung der IV-Stelle des Kantons Bern vom 3. Dezember 2014 bestätigt.
2.
Der Beschwerdegegnerin wird die unentgeltliche Rechtspflege im Sinne der Befreiung von den Gerichtskosten gewährt.
3.
Die Gerichtskosten von Fr. 800.- werden der Beschwerdegegnerin auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, zurückgewiesen.
5.
Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 25. April 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Der Gerichtsschreiber: Williner